Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
add comment

5 Answers

up vote 8 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

TO address the criticism of David Carraher

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

yields:

{0.003, 0.035}

as desired

share|improve this answer
    
Does not give the desired results. –  David Carraher 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 –  David Carraher Sep 13 '13 at 4:40
    
It is now correct. –  David Carraher Sep 13 '13 at 4:55
    
@DavidCarraher thank you for corrections: conceptual and typographic –  ubpdqn Sep 13 '13 at 5:00
add comment

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

share|improve this answer
    
I knew my computer was slow but the differences between our results are staggering. Nice idea to use packed arrays. –  David Carraher Sep 13 '13 at 13:44
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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