19
$\begingroup$

I have an extremely large CSV file that contains only entries like the following:

Nil,+1
int,+1
int,-1
int,-1
Nil,+1
Nil,-1
Dictionary,+1
Dictionary,-1
Array,+1
Nil,+1
String,+1

I have parsed the file in Wolfram via

ds = Import["/path/to/large/file.txt", {"CSV", "Dataset"}, HeaderLines -> 0];
listOfAssoc = (Association[Rule @@ #1]) & /@ (ds // Normal);
Merge[listOfAssoc, Total]

which yields

<|"int" -> -6159, "Nil" -> 72282, "Array" -> -9, 
 "Dictionary" -> -15, "String" -> -371, "bool" -> -266, 
 "float" -> 15857, "RID" -> 0, "Rect2" -> 0, "Color" -> -23, 
 "PoolVector2Array" -> 0, "PoolRealArray" -> 0, "PoolIntArray" -> 0, 
 "Vector2" -> -10, "PoolStringArray" -> 0, "Transform" -> -2, 
 "Transform2D" -> 0, "Object" -> 1042, "Vector3" -> 612, 
 "PoolVector3Array" -> 0, "PoolColorArray" -> 0, "Plane" -> -4, 
 "Quat" -> 0, "AABB" -> 0, "Basis" -> 0, "NodePath" -> 0, 
 "PoolByteArray" -> 0|>

This looks about correct to me as far as the actual computation goes (i.e. I'm just trying to add up a bunch of 1's and -1's from log data to see if certain types in another computer program are leaking memory, and this computation was very helpful for that).

Problem.

The last line of this computation (Merge[listOfASsoc, Total]) takes several minutes (like 10 minutes). Am I doing something wrong?

$\endgroup$
  • $\begingroup$ Merge[list, Total] seems to have roughly $O(n^2)$ time complexity for large number of non-empty associations in list. Maybe this is the source of trouble? In this case you could possibly perform the operation more efficiently in some sort of divide and conquer method thanks to properties of Total... $\endgroup$ – kirma Dec 24 '19 at 20:29
  • 1
    $\begingroup$ You might consider replacing Merge[listOfAssoc, Total] with First@NestWhile[Merge[Total] /@ Partition[#, UpTo@64] &, listOfAssoc, Length[#] > 1 &]. This changes the order of summation which may or may not be relevant in your application, but at least yields much more linear time complexity. $\endgroup$ – kirma Dec 24 '19 at 20:47
  • 1
    $\begingroup$ kirma: The operation is now immediate. That fixed the issue. $\endgroup$ – George Dec 24 '19 at 21:05
  • $\begingroup$ Converted my comments to an answer. $\endgroup$ – kirma Dec 24 '19 at 21:20
15
$\begingroup$

This would seem to really be a question on runtime complexity of Merge, or more specifically in this case Merge[Total]. It seems to have roughly $O(n^2)$, instead of expected mostly-linear complexity.

In the case of Total as the merging operator this problem can be solved by a divide-and-conquer approach working around the quadratic growth of running time:

First@NestWhile[
 Merge[Total] /@ Partition[#, UpTo@64] &,
 listOfAssoc,
 Length[#] > 1 &]

This splits the input to sublists of at most 64 items and performs the merge operator on all of these sublists individually, repeating until only one list item is left (which is the result). This is identical to the original Merge[Total] operation apart from the order of the summation, which is safe in most scenarios which are not sensitive to summation order (a well known floating point number problem).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Does it count as a bug that Merge[Total] performs worse performance than expected? $\endgroup$ – QuantumDot Dec 25 '19 at 4:43
  • $\begingroup$ @QuantumDot I think it shouldn't be this bad. (It isn't obvious without thousands of associations, anyway!) Maybe the assumption the implementor has had is that the amount of associations is low, and this makes it an "irrelevant" question. $\endgroup$ – kirma Dec 25 '19 at 5:01
  • $\begingroup$ I think this can be written Fold[Merge[fn]@*List, Partition[listOfAssoc, UpTo@64]] $\endgroup$ – Mr.Wizard Dec 26 '19 at 8:03
  • $\begingroup$ @Mr.Wizard That works too, but the logic of it is different from my solution. Also, efficiency on really large lists is probably lower(?). $\endgroup$ – kirma Dec 26 '19 at 12:09
  • 1
    $\begingroup$ I added a benchmark. If I didn't mess up your method it appears they perform similarly in version 10.1. $\endgroup$ – Mr.Wizard Dec 28 '19 at 9:45
18
$\begingroup$

It appears GroupBy does not suffer from this performance issue, so here is an alternative implementation using it, compared to Merge:

myMerge[list_, fn_] := GroupBy[Catenate @ Normal[list], Keys -> Values, fn]

SeedRandom[1]
ascList = Table[<|a -> Random[], b -> Random[]|>, {20000}];

Merge[ascList, Total]   // RepeatedTiming
myMerge[ascList, Total] // RepeatedTiming
{2.29, <|a -> 9944.07, b -> 9990.23|>}

{0.038, <|a -> 9944.07, b -> 9990.23|>}

Further benchmarking

Benchmarking of more methods including one using Carl Woll's GroupByList.

I don't have UpTo in version 10.1 so I wrote these without it.

Needs["GeneralUtilities`"]
GroupByList = ResourceFunction["GroupByList"];

kirmaMerge[fn_][list_] := 
 First@NestWhile[Merge[fn] /@ Partition[#, 64, 64, 1, {}] &, list, Length[#] > 1 &]

wizMerge1[fn_][list_] := GroupBy[Catenate@Normal[list], Keys -> Values, fn]
wizMerge2[fn_][list_] := 
  <| Reap[KeyValueMap[Sow[#2, #] &] /@ list;, _, # -> fn[#2] &][[2]] |>
wizMerge3[fn_][list_] := Fold[Merge[fn]@*List, {}, Partition[list, 64, 64, 1, {}]]
wizMerge4[fn_][list_] := GroupByList[Catenate@Values@list, Catenate@Keys@list, fn]

gen = Association /@ 
    Table[RandomChoice[{"a", "b", "c", "d"}] -> Random[], {#}, {2}] &;
fns = {Merge, kirmaMerge, wizMerge1, wizMerge2, wizMerge3, wizMerge4};

BenchmarkPlot[Through[fns[Total]], gen, 2]

enter image description here

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The method based PositionIndex seems to be still several times faster. And it saves the generation of the long list of associations in the first place (which definitely does not come for free). $\endgroup$ – Henrik Schumacher Dec 28 '19 at 15:56
  • $\begingroup$ @Henrik I chose only to seek a faster Merge alternative because it seems to have a significant performance issue. I did not try to include your method because it was a way to avoid the Association creation in the first place, rather than speeding processing of existing Association data. If you would like me to try to include your method I shall, but I will be starting with the same Association data because that is my interest in this question, even if yours is the better answer. $\endgroup$ – Mr.Wizard Dec 28 '19 at 20:27
9
$\begingroup$

If all the associations have same set of keys, then Tr and Total are faster than all the methods posted so far.

Wrapping the list of associations with Dataset and using Total is also quite fast.

Using Mr. Wizard's test setup,

SeedRandom[1]
ascList = Table[<|a -> Random[], b -> Random[]|>, {30000}];

Tr[ascList] // RepeatedTiming

{0.014, <|a -> 14984.3, b -> 15053.|>}

Total[ascList] // RepeatedTiming

{0.014, <|a -> 14984.3, b -> 15053.|>}

Dataset[ascList][Total] // Normal // RepeatedTiming

{0.041, <|a -> 14984.3, b -> 15053.|>}

compare to the methods form kirma's and Mr. Wizard's answers:

First @ NestWhile[Merge[Total] /@ Partition[#, UpTo @ 64] &, ascList, 
   Length[#] > 1 &] // RepeatedTiming

{0.054, <|a -> 14984.3, b -> 15053.|>}

myMerge[ascList, Total] // RepeatedTiming

{0.095, <|a -> 14984.3, b -> 15053.|>}

$Version

"11.3.0 for Microsoft Windows (64-bit) (March 7, 2018)"

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ +1 for including what I didn't, but I was considering the case where not all keys are common to all associations. A related question of mine for those interested by this: (63293) $\endgroup$ – Mr.Wizard Dec 25 '19 at 6:34
  • $\begingroup$ Thank you @Mr.Wizard. Very good point. I added the qualification to the post. $\endgroup$ – kglr Dec 25 '19 at 9:35
6
$\begingroup$

In some constellations, when many keys are duplicates, this can be faster by two orders of magnitude than Merge and still ten times faster than kirma's method. It keeps the keys and the values in separate lists. The latter one can be packed which is also helpul for indexing and summation operations.

words = RandomWord[100];
n = 1000000;
keys = RandomChoice[words, n];
values = RandomInteger[{-10, 10}, n];

listOfAssoc = Association /@ Rule @@@ Transpose[{keys, values}];

r1 = Merge[listOfAssoc, Total]; // AbsoluteTiming // First

r2 = First@ NestWhile[Merge[Total] /@ Partition[#, UpTo@64] &, listOfAssoc, Length[#] > 1 &]; // AbsoluteTiming // First   

r3 = Map[
      list \[Function] Total[values[[list]]], 
      PositionIndex[keys]
      ]; // AbsoluteTiming // First


r1 == r2 == r3

17.7318

2.37986

0.17167

True

| improve this answer | |
$\endgroup$

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.