2
$\begingroup$

I have a list of (integer) 2d points, and I want to calculate the mean at each point in the first coordinate. So if my data is:

data = {{8,0},{7,0},{7,0},{6,0},{6,0},{6,0},{5,0},{5,0},{5,0},{5,0},{4,1},{4,0},{4,0},{4,0},{4,0},{3,1},{3,1},{3,0},{3,0},{3,0},{3,1},{2,1},{2,1},{2,1},{2,0},{2,0},{2,1},{2,1},{1,1},{1,1},{1,1},{1,1},{1,0},{1,1},{1,1},{1,1}};

then I want my output to be:

{{1, 7/8}, {2, 5/7}, {3, 1/2}, {4, 1/5}, {5, 0}, {6, 0}, {7, 0}, {8,0}}

My initial data will be unsorted, but that is quick to fix. I can do this with the following awkward looking construction:

meanByFirstComponent[data_] := Module[{dataUnion, reorderedData},
dataUnion = (Union@data[[All, 1]]);
reorderedData = Table[Select[data, #[[1]] == ii &], {ii, dataUnion}];
Mean /@ reorderedData]

but this is very slow for a large list:

data = With[{n = 400}, 
Transpose[{RandomInteger[n, n^2], RandomReal[{0, 1}, n^2]}]];
AbsoluteTiming[meanByFirstComponent[data];]

{53.963087, Null}

Essentially I want to partition a sorted list that looks like:

{{1,1},{1,2},{2,1},{2,2},{3,1}} 

into

{{{1,1},{1,2}},{{2,1},{2,2}},{{3,1}}}

and I can't work out how to do this efficiently.

$\endgroup$
  • $\begingroup$ Also I wasn't sure how to title this question, if anyone has a better idea then feel free to suggest/change it. $\endgroup$ – KraZug Jun 17 '15 at 15:45
  • $\begingroup$ Can we assume that your input data will always be sorted by its first element as you show in your example? If that is in fact the case, will the ordering always be descending by the value of the first element in each pair? $\endgroup$ – MarcoB Jun 17 '15 at 16:55
  • $\begingroup$ @MarcoB My data is unsorted, have added that into the question, but sorting is quick. $\endgroup$ – KraZug Jun 17 '15 at 18:21
5
$\begingroup$

I think the function you want is GatherBy:

GatherBy[data, First]

(* {{{8, 0}}, {{7, 0}, {7, 0}}, {{6, 0}, {6, 0}, {6, 0}}, {{5, 0}, {5, 0}, {5, 0}, {5, 0}}, ... *)

You can then apply Mean to each element in the list:

Mean /@ %
(* {{8, 0}, {7, 0}, {6, 0}, {5, 0}, {4, 1/5}, {3, 1/2}, {2, 5/7}, {1, 7/8}} *)

EDIT: Note that the use of GatherBy does not require a Sort; SplitBy only compares adjacent elements, so you'd need to sort the list by the first element before applying SplitBy. However, if the data is already sorted, then SplitBy might be a bit faster. If we apply the two procedures to an unsorted random data set of 400 points, as proposed in the OP, we get:

AbsoluteTiming[Mean /@ GatherBy[data, First];]
AbsoluteTiming[Mean /@ SplitBy[Sort[data], First];]

(* {0.108721, Null} *)
(* {0.620833, Null} *)

(For comparison, the OP's original code takes about 65 seconds on my machine.)

$\endgroup$
  • $\begingroup$ Apparently the OP wants a sorted list as output. Gather[ ] doesn't sort $\endgroup$ – Dr. belisarius Jun 17 '15 at 15:53
  • $\begingroup$ I wasn't clear from the OP whether the order of the output was important; but if it is, one could apply Sort to the final list. $\endgroup$ – Michael Seifert Jun 17 '15 at 15:58
  • $\begingroup$ Given I don't have a sorted list, GatherBy followed by sorting works faster for me than sorting then SplitBy (0.05 seconds vs 0.13 seconds on my list of 79800 elements). $\endgroup$ – KraZug Jun 17 '15 at 18:43
4
$\begingroup$
Mean /@ SplitBy[Sort[data], First]

If speed is paramount:

Sort[Mean /@ SplitBy[data, First]]

which is faster because one sorts a smaller number of elements.

$\endgroup$
  • 1
    $\begingroup$ One has to be careful though: SplitBy only compares adjacent pairs of elements, so if the data is not pre-sorted your second method won't work as intended. Conversely, if we can assume that the data is pre-sorted, then there is no need to sort it again: we can use the sorting information to return the list or its Reverse, which I'd expect to be faster than re-sorting. $\endgroup$ – MarcoB Jun 17 '15 at 16:53
  • $\begingroup$ I knew there would be a function to do this and I just couldn't figure out its name, then it turns out there are two. $\endgroup$ – KraZug Jun 17 '15 at 18:45
1
$\begingroup$

Also (> v.10 only) :

GroupBy[data, First -> Last, Mean]

<|8 -> 0, 7 -> 0, 6 -> 0, 5 -> 0, 4 -> 1/5, 3 -> 1/2, 2 -> 5/7, 1 -> 7/8|>

It seems a little bit faster than with the SplitBy approach (when testing the random 400 points data set)

$\endgroup$
  • $\begingroup$ GroupBy was introduced in version 10 and I'm still running v9 (as v10 refuses to install on my system for some reason), so I can't test this. $\endgroup$ – KraZug Jun 19 '15 at 8:14
  • $\begingroup$ @KraZug v10 introduces also Association and Dataset which should be efficient to handle large data sets (see doc here and here) and which "work" with GroupBy (as you can see the output here). It is worth to upgrade if you can. You should contact Wolfram support or maybe post your install problem here on MSE ;) $\endgroup$ – SquareOne Jun 19 '15 at 9:57
0
$\begingroup$

Not nearly as good as David G. Storks's (it'll be hard to beat), but here another way:

Mean /@ (Pick[data, data[[All, 1]], #] & /@ Union[data[[All, 1]]])
$\endgroup$
  • $\begingroup$ Actually, if speed is the goal, one can get a speedup by sorting after the mean computation: Sort[Mean /@ SplitBy[data, First]], which is an order of magnitude faster for one large data set I tried. $\endgroup$ – David G. Stork Jun 17 '15 at 16:20

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.