# Reshaping list of 2D points by first coordinate

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.

• Also I wasn't sure how to title this question, if anyone has a better idea then feel free to suggest/change it. Jun 17, 2015 at 15:45
• 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? Jun 17, 2015 at 16:55
• @MarcoB My data is unsorted, have added that into the question, but sorting is quick. Jun 17, 2015 at 18:21

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

• Apparently the OP wants a sorted list as output. Gather[ ] doesn't sort Jun 17, 2015 at 15:53
• 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. Jun 17, 2015 at 15:58
• 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). Jun 17, 2015 at 18:43
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.

• 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. Jun 17, 2015 at 16:53
• 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. Jun 17, 2015 at 18:45

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)

• 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. Jun 19, 2015 at 8:14
• @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 ;) Jun 19, 2015 at 9:57

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]]])

• 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. Jun 17, 2015 at 16:20