Combining the second elements of a set of ordered pairs based on their first element [duplicate]

Question

I have a large set of ordered pairs and I am trying to add the second elements together for any group of pairs that has the same first element.

For example my data looks like:

data={{1,2},{1,3},{2,3},{3,2},{3,6}}

and I want to return something like:

newdata={{1,5},{2,3},{3,8}}

I figured out how to group the data based on their first element using GatherBy[data,{First}], but I'm not sure where to go from there.

I feel like there is probably a much easier way than that, but it is evading me.

Answer 1

data = {{1, 2}, {1, 3}, {2, 3}, {3, 2}, {3, 6}}
{#[[1, 1]], Total[#[[All, 2]]]} & /@ GatherBy[data, First]

{{1, 5}, {2, 3}, {3, 8}}

But it isn't very sophisticated.

Answer 2

newData = Map[{#[[1, 1]], Total[#[[;; , 2]]]} &, GatherBy[data, First[#] &]];

Explaination: GatherBy[data, First[#] &] makes a list of all the elements in data, that have the same first element. Now, we apply the function {#[[1, 1]], Total[#[[;; , 2]]]} & by using Map to to take the first part of the first element of each list and then the sum of all the second parts.

EDIT

It seems that the reapand sow approach from above is much slower:

n = 1000000;
data = RandomInteger[{1, 100}, {n, 2}];
Map[{#[[1, 1]], Total[#[[;; , 2]]]} &, GatherBy[data, First[#] &]]; // AbsoluteTiming
Reap[Sow[#2, #1] & @@@ data, _, {#1, Total[#2]} &][[2]]; // AbsoluteTiming

{0.180010, Null}

{1.375079, Null}

Answer 3

This is easy to do with Reap and Sow,

Reap[Sow[#2, #1] & @@@ data, _, {#1, Total[#2]} &][[2]]

Sow tags the second element of the each datum with the first element, and Reap gathers them up, and using the last parameter, they're recombined.

For the curious, the function {#1, Total[#2]} & is passed the tag as the first parameter - in this case, the common first element of each datum, and a list of all the elements with that tag as the second parameter.

---

As Frederik points out, this solutions is not the fastest, so here is a timing comparison. To get the timings, I used the following function:

ClearAll[timingF];
SetAttributes[timingF, HoldAll];
timingF[expr_, threshold_: 1] := 
 Block[{time = 0, it = 0},
  While[ time <= threshold, 
   ++it;
   time += AbsoluteTiming[expr][[1]]
   ];
  time/it
  ]

which runs any expr that takes less time than some threshold multiple times until that threshold is reached. Then, by taking the average, the inherent jitter in small timings is reduced.

Based on the data, I added one additional example:

Reap[Sow[#[[2]], #[[1]]] & /@ data, _, {#1, Total[#2]} &][[2]]

which I will explain why in a moment. I ran the three functions with data sets as large as $10^7$ elements, and here are their timings:

In casual use, below $10^5$ elements the difference between the functions won't be noticeable, and at 100 elements and below my original function competes favorably with Frederik's. But, above 100 elements, Frederik's function becomes much faster. 100 elements is the default length for auto-compilation to kick-in, so it is the inspiration for the Map form of Reap. But, Sow is not compilable, so it is slower than using Apply (@@@), in this case. An interesting thing to note, though, is all three functions scale almost linearly with input size above $10^4$ elements.

Answer 4

I believe this is quite fast, but not as fast as Frederik's:

s[p_] := Module[{ f},
  f[_] = 0;
  Scan[f@#[[1]] += #[[2]] &, p];
  f
  ]
k = s[points];
ListLinePlot[{#, k@#} & /@ points[[All, 1]]]