8
$\begingroup$

I have two lists, one containing values, the other indices. Now I want to accumulate the values that have the same corresponding index. So for example:

values  = {2, 6, 3, 8, 3, 1, 3, 7, 1, 3, 5}

indices = {1, 3, 1, 2, 3, 1, 1, 2, 3, 2, 1}

should give

result = {2 + 3 + 1 + 3 + 5, 8 + 7 + 3, 6 + 3 + 1}

I need to do this for very large lists, so it should be efficient.

Any ideas?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ GatherBy[Transpose[{values, indices}], Last][[All, All, 1]] $\endgroup$
    – user1066
    Commented Feb 20, 2017 at 14:11
  • 2
    $\begingroup$ What's "very large lists"? Thousands of elements? Millions of elements? Billions? And how many distinct indices would be expected? 50% of elements? 10%? 1%? There will be very different ways of doing this depending on such things. $\endgroup$
    – ciao
    Commented Feb 20, 2017 at 14:20

7 Answers 7

Reset to default
7
$\begingroup$

Pick is usually fast, and parallel processing may help, depending on your computer.

ParallelTable[Total[Pick[values, indices, k]], {k, Union[indices]}]
Improve this answer
$\endgroup$
6
$\begingroup$

Another possibility which is certainly quick for large sets:

GroupBy[Transpose[{values, indices}], Last -> First, Total]

This returns an association which can be converted back to a list ordered by index for no overhead with the frustratingly verbose

Normal@*SparseArray@*Normal@GroupBy[...]
Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ +1 Values@GroupBy[...] will also do the trick. $\endgroup$
    – WReach
    Commented Feb 20, 2017 at 16:57
  • $\begingroup$ It will, but it won't guarantee that the values will be in the order dictated by indices. SparseArray is useful as it takes care of that. $\endgroup$
    – Quantum_Oli
    Commented Feb 20, 2017 at 17:06
  • $\begingroup$ Yes, you are right... the implicit ordering of various association-related operations is unreliable as it has changed over the past few releases. Values@KeySort@GroupBy[...] is another possibility. $\endgroup$
    – WReach
    Commented Feb 20, 2017 at 17:15
5
$\begingroup$

Possible duplicate of How to efficiently find positions of duplicates? or Gather list elements by labels

e.g.

positionDuplicates[list_] := GatherBy[Range@Length[list], list[[#]] &]

values[[#]] & /@ positionDuplicates[indices]

Total[%, {2}]

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

{14, 10, 18}
Improve this answer
$\endgroup$
3
$\begingroup$

A Reap/Sow variant:

Reap[MapThread[Sow[#1, #2] &, {values, indices}], _, {#2, Total@#2} &][[-1]]

yields:

{{{2, 3, 1, 3, 5}, 14}, {{6, 3, 1}, 10}, {{8, 7, 3}, 18}}
Improve this answer
$\endgroup$
2
$\begingroup$ 
values = {2, 6, 3, 8, 3, 1, 3, 7, 1, 3, 5};

indices = {1, 3, 1, 2, 3, 1, 1, 2, 3, 2, 1};

Requested result

result = {2 + 3 + 1 + 3 + 5, 8 + 7 + 3, 6 + 3 + 1}

{14, 18, 10}

Using Merge

KeySort @ Merge[Total] @ Thread[indices -> values]

<|1 -> 14, 2 -> 18, 3 -> 10|>

Values[%]

{14, 18, 10}

Improve this answer
$\endgroup$
2
$\begingroup$ 
groupMap = Extract[#, Map[List]@Values@PositionIndex@#2, #3] &;

Examples:

values = {2, 6, 3, 8, 3, 1, 3, 7, 1, 3, 5};

indices = {1, 3, 1, 2, 3, 1, 1, 2, 3, 2, 1};

groupMap[values, indices, Total]

{14, 10, 18}

groupMap[Array[x, Length@indices], indices, Apply[Times]]

enter image description here

Improve this answer
$\endgroup$
1
$\begingroup$

Using SplitBy:

values = {2, 6, 3, 8, 3, 1, 3, 7, 1, 3, 5};
indices = {1, 3, 1, 2, 3, 1, 1, 2, 3, 2, 1};

Total /@ Values@SplitBy[Sort@Thread[indices -> values], First]

(*{14, 18, 10}*)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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