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

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.

• Also see: (16507) Commented Mar 12, 2014 at 1:04

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.

• Doesn't it seem like there is a more sophisticated way somewhere? It was driving me nuts. But this method works like a charm thanks so much! Commented Jun 6, 2013 at 19:38
• @Kathryn Use Reap and Sow; they're built for this type of gather and transform problem. Commented Jun 6, 2013 at 19:52
• Equivalently: {1, Length[#]} Mean[#] & /@ GatherBy[data, First]. Commented Jun 7, 2013 at 1:29
• @0x4A4D But in this case it calculates Total and twice Length, not much but I think more. However, I like it.
– Kuba
Commented Jun 7, 2013 at 6:00
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}

• Thanks for your quick and helpful answer! My data is sorted as needed. Commented Jun 6, 2013 at 19:38
• On a small list, $10^6$ is not small, it doesn't matter. But, for quick solutions without much additional work, Reap and Sow are perfect for it. btw, +1. Commented Jun 6, 2013 at 20:25
• I added some timing data to my answer, alongside an explanation as to why it occurs that way. Commented Jun 7, 2013 at 13:02

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.

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.

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


• No, I was wrong; it works. I just read the code and evaluated in my head. I figured f would be cleared because it is Temporary, but forgot that only those module variables that are not returned are cleared. So this should work.
– rm -rf
Commented Mar 9, 2014 at 21:38
• @rm-rf Yours, it's a lazy evaluator. Commented Mar 9, 2014 at 21:40
• "I just read the code and evaluated in my head" @Mr.Wizard has to add it to his quotes set. :D
– Kuba
Commented Mar 9, 2014 at 21:44
• @Kuba Frogs have a strange anatomy configuration, you know. I've heard tadpoles eat Pi quadratures for breakfast Commented Mar 9, 2014 at 21:47
• @Kuba BTW, do you have anay relationship with this guy? en.wikipedia.org/wiki/Ryogo_Kubo Commented Mar 9, 2014 at 21:49