6
$\begingroup$

I have a list of coordinate pairs, take for example the following list of three pairs:

exampleList = {
  {{151.335, 245.102}, {151.332, 245.187}}, 
  {{41.435, 245.021}, {41.3617, 244.986}},
  {{131.048, 243.364}, {131.046, 243.321}}
}

Assuming the list is very large, what is a fast one-liner to calculate the median difference between elements in each pair?

The output should be the same as:

Median[exampleList[[All, 1]] - exampleList[[All, 2]]]

Is this the fastest way to proceed?

$\endgroup$
8
$\begingroup$

Assuming the goal is to take the difference between each pair, and then take the median of all the differences:

Median[Flatten@Map[Differences, exampleList, {2}]]

112.296

To match the revised version of the OPs question:

-Median[Differences /@ exampleList]

{{0.003, 0.035}}

(or maybe Flatten this to get rid of the extra parentheses). The minus sign is there because Differences does the "second-first", whereas the OP wishes to have "first-second".

$\endgroup$
  • $\begingroup$ Oh, I meant that the pairs should be the coordinate, so a difference would be: {151.335, 245.102} - {151.332, 245.187} for the first element pair and so forth. The answer should be a 2D coordinate. Sorry, I was being unclear in my question. $\endgroup$ – HStoley Sep 13 '13 at 3:02
  • $\begingroup$ I modified my question with a command that should give the right output. I suspect this is a slower-than-optimal way to do things for large lists? $\endgroup$ – HStoley Sep 13 '13 at 3:05
  • $\begingroup$ I think the modified version matches your description. I can't see why one would be much faster than the other, but you could do a test with Timing and a large input. $\endgroup$ – bill s Sep 13 '13 at 3:20
8
$\begingroup$

Here's still another way.

-Median /@ Transpose@Flatten[Differences /@ exampleList, 1] 

{0.003, 0.035}


Speed Comparison Using the Same Data Set (10^7 pairs of points)

First, some data...

r := {RandomInteger[{130, 160}] + RandomReal[{0, 2}], RandomInteger[{230, 245}] 
     + RandomReal[{0, 2}]}
data = Table[{r, r}, {10^7}];

When I ran tests with 10^6 point pairs, no method consistently came out on top. This changed dramatically, however, when 10^7 point pairs were used.

The OP's method: Timing (in sec), followed by output.

Median[data[[All, 1]] - data[[All, 2]]] // AbsoluteTiming

{89.881627, {0.00444683, 0.000841006}}


The method of @ubpdqn:

({x, y} = Transpose[data]; Median[x - y]) // AbsoluteTiming

{84.078609, {0.00444683, 0.000841006}}


David Carraher's Method:

Median /@ Transpose@Flatten[-Differences /@ data, 1] // AbsoluteTiming

{31.198662, {0.00444683, 0.000841006}}


The method of @bill s:

-Median[Differences /@ data] // AbsoluteTiming

{28.992141, {{0.00444683, 0.000841006}}}

$\endgroup$
6
$\begingroup$

TO address the criticism of David Carraher

{x, y} = Transpose[exampleList]
Median[x-y]

yields:

{0.003, 0.035}

as desired

$\endgroup$
  • $\begingroup$ Does not give the desired results. $\endgroup$ – DavidC Sep 13 '13 at 4:14
  • $\begingroup$ @DavidCarraher thank you for pointing out my error which I hope I have corrected. $\endgroup$ – ubpdqn Sep 13 '13 at 4:35
  • $\begingroup$ Meadian should be Median $\endgroup$ – DavidC Sep 13 '13 at 4:40
  • $\begingroup$ It is now correct. $\endgroup$ – DavidC Sep 13 '13 at 4:55
  • $\begingroup$ @DavidCarraher thank you for corrections: conceptual and typographic $\endgroup$ – ubpdqn Sep 13 '13 at 5:00
5
$\begingroup$

I've run @David Carraher's speed comparison on MMA V9 on my machine, and strangely, I get very different results. In a nutshell: Using packed arrays, the OP's method is faster than all others, by far.

r := {RandomInteger[{130, 160}] + RandomReal[{0, 2}], 
  RandomInteger[{230, 245}] + RandomReal[{0, 2}]}
data = Table[{r, r}, {10^7}];

The method of @bill s:

-Median[Differences /@ data] // AbsoluteTiming

{8.066461, {{-0.00213092, 0.000470161}}}

The OP's method:

Median[data[[All, 1]] - data[[All, 2]]] // AbsoluteTiming

{8.398480, {-0.00213092, 0.000470161}}

The method of @ubpdqn:

({x, y} = Transpose[data]; Median[x - y]) // AbsoluteTiming

{12.829734, {-0.00213092, 0.000470161}}

David Carraher's Method:

Median /@ Transpose@Flatten[-Differences /@ data, 1] // AbsoluteTiming

{8.233471, {-0.00213092, 0.000470161}}

The same again using packed data

Needs["Developer`"]
data = ToPackedArray@data;

The method of @bill s:

-Median[Differences /@ data] // AbsoluteTiming

{7.373422, {{-0.00213092, 0.000470161}}}

The OP's method:

Median[data[[All, 1]] - data[[All, 2]]] // AbsoluteTiming

{4.800275, {-0.00213092, 0.000470161}}

The method of @ubpdqn:

({x, y} = Transpose[data]; Median[x - y]) // AbsoluteTiming

{10.422596, {-0.00213092, 0.000470161}}

-Median[Differences /@ data] // AbsoluteTiming

{7.960455, {-0.00213092, 0.000470161}}

$\endgroup$
  • $\begingroup$ I knew my computer was slow but the differences between our results are staggering. Nice idea to use packed arrays. $\endgroup$ – DavidC Sep 13 '13 at 13:44
2
$\begingroup$

This is slightly faster on packed arrays than the method adapted from @Nasser in the OP:

data = With[{n = 10^7}, 
  Transpose[{RandomInteger[{130, 160}, {2, 1 n}], 
     RandomInteger[{230, 245}, {2, n}]} + 
    RandomReal[{0, 2}, {2, 2, n}], {3, 2, 1}]]

-Median /@ Differences @ Transpose @ data // AbsoluteTiming
(* {5.429034, {{0.00338283, -0.000382357}}} *)

Compared with the OP:

Median[data[[All, 1]] - data[[All, 2]]] // AbsoluteTiming
(* {5.726198, {0.00338283, -0.000382357}} *)

If you compare it with @bill-s,

-Median[Differences /@ data] // AbsoluteTiming
(* {15.315464, {{0.00338283, -0.000382357}} *)

the upshot is that vectorized usually beats Map.

If you compare it with @ubpdqn, whose underlying idea is similar,

On["Packing"];
({x, y} = Transpose[data]; Median[x - y]) // AbsoluteTiming
(* messsages re unpacking *)
(* {29.155011, {0.00338283, -0.000382357}} *)

you see that unpacking can slow things down a lot.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.