# A fast way to calculate the median difference between pairs of elements

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?

-

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".

-
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. – HStoley Sep 13 '13 at 3:02
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? – HStoley Sep 13 '13 at 3:05
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. – bill s Sep 13 '13 at 3:20

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}}}

-

TO address the criticism of David Carraher

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


yields:

{0.003, 0.035}

as desired

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

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}}

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

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.

-