# faster way to merge data

for example I have a data

Clear[data];
data[n_] :=
Join[RandomInteger[{1, 10}, {n, 2}], RandomReal[1., {n, 1}], 2];


then data gives

{{4, 8, 0.264842}, {9, 5, 0.539251}, {3, 1, 0.884612}}


in each sublist, first two value is matrix index, the last is matrix element which have to be added together for same matrix index.

I want to transform the data into matrix. Usually I do it like

Clear[toSparse]
toSparse[data_] :=
SparseArray@
Normal@Merge[Thread[data[[;; , 1 ;; 2]] -> data[[;; , -1]]], Total]


In:= toSparse[data]; // AbsoluteTiming

Out= {0.00836793, Null}

In:= toSparse[data]; // AbsoluteTiming

Out= {0.0644464, Null}

In:= toSparse[data]; // AbsoluteTiming

Out= {1.35507, Null}

In:= toSparse[data]; // AbsoluteTiming

Out= {200.862, Null}


Any faster way to do this?

• @Mr.Wizard The question itself, that I read as "I want to transform the data into matrix. (...). Any faster way to do this?" doesn't really have anything to do with SparseArrays, right? So the duplicate only explains the answers given so far, that use SparseArrays. The reason I point out this is that there are even faster ways than the ones presented here. Jun 10, 2017 at 10:14
• @Marius I somehow read "I want to transform the data into matrix" as I want to transform the data into a sparse array probably because it was followed by toSparse[data_] := . . .. I'll reopen. I look forward to your answer with a faster method than "TreatRepeatedEntries"! Jun 10, 2017 at 10:20
• Related: (37566) Jun 10, 2017 at 10:21
• @Mr.Wizard Thank you so much for the link : ) Jun 13, 2017 at 6:51

You can change the SparseArray system options to total repeated entries instead of taking the first. Here is a function that does this:

carl[data_] := InternalWithLocalSettings[
old=SystemOptions["SparseArrayOptions" -> "TreatRepeatedEntries"];
SetSystemOptions["SparseArrayOptions" -> "TreatRepeatedEntries" -> Total],

SetSystemOptions[old]
]


Compare this with @edmund's solution:

edmund[data_] := SparseArray @ Normal @ GroupBy[data, Most->Last, Total]


For example:

data[n_] := Join[RandomInteger[{1,10}, {n,2}], RandomReal[1., {n,1}], 2]

d6 = data[10^6];
r1 = carl[d6]; //AbsoluteTiming
r2 = edmund[d6]; //AbsoluteTiming
MinMax[r1-r2]


{0.852608, Null}

{1.26883, Null}

{-1.00044*10^-11, 8.18545*10^-12}

The difference is due to the order in which the repeated entries are totaled in the two methods.

• Great! I am curious, how do you know this? Jun 10, 2017 at 2:18
• @matheorem ExperimentalSystemOptionsEditor[] is a nice way to view all of the available system options. Jun 10, 2017 at 2:23
• Wow, this is really amazing! Thank you so much! Jun 10, 2017 at 3:01
• @matheorem you should read (807) :-) Jun 10, 2017 at 8:48

You may use GroupBy.

Clear[toSparse]
toSparse[data_] := SparseArray@Normal@GroupBy[data, Most -> Last, Total]


Then

toSparse[data]; // AbsoluteTiming

{0.0019702, Null}

toSparse[data]; // AbsoluteTiming

{0.0155542, Null}

toSparse[data]; // AbsoluteTiming

{0.181737, Null}

toSparse[data]; // AbsoluteTiming

{2.0271, Null}


Hope this helps.

• Hi, @Edmund. Thank you so much for the solution. I am shocked that GroupBy can be so much faster than Merge, it seems that they perform very similar operation. What cause such a big difference? Jun 10, 2017 at 2:29

I can't see any sparsity at all in this problem, given that we are adding values to n random elements of a 10x10 matrix, and n is up to $10^6$. So, given that we keep data as-is, the algorithm to fill the matrix is so straight-forward that it's a good candidate for compiling. I propose

makeMatrix = Compile[{{inds, _Integer, 2}, {vals, _Real, 1}},
Block[{mat = Table[0., {10}, {10}]},
Do[
mat[[inds[[i, 1]], inds[[i, 2]]]] += vals[[i]]
, {i, Length[vals]}
];
mat
]
, CompilationTarget -> "C"
, RuntimeOptions -> "Speed"
]


and a wrapper

marius[data_] := makeMatrix[data[[All, 1 ;; 2]], data[[All, 3]]]


Then, on my machine,

d6 = data[10^6];
r1 = carl[d6]; //AbsoluteTiming
r2 = edmund[d6]; //AbsoluteTiming
r3 = marius[d6]; //AbsoluteTiming
Max[Abs[r3 - r1]]


gives

{0.967007, Null}

{1.571291, Null}

{0.305536, Null}

3.63798*10^-11

• Thank you for the fast compile solution Jun 13, 2017 at 6:53