# Fast value search and replacement in a matrix with expansion for multiple values

I am working on some rather large matrices (15-50M+ rows by 5-5000 columns), and I would like your help with some performance knowhow. To save your time typing up trivial solutions, I know how to get this done, but what I am doing is far from fast. I am not looking for just an answer, but a memory/speed high-performance solution.

Let's say I have a dictionary, where each row is a conversion from ID in system 1 to ID in system 2, and one-to-many relationship is possible:

dict={
{1,11},
{1,12},
{2,13},
{3,14}
}; (* 1, 2, 3 are the old IDs *)


and I have a matrix with a mixture of old IDs and new IDs in some column (#3 here):

data={
{1,0,2,0,0},
{2,0,1,0,0},
{3,0,3,0,0},
{4,0,11,0,0},
{5,0,2,0,0},
{6,0,14,0,0},
{7,0,1,0,0}
}


My goal is to replace all 1,2,3 values with their new mappings. And in the case of a multiple mapping, I need to expand my matrix:

(* After replacement *)
{
{1,0,13,0,0},
{2,0,{11,12},0,0},
{3,0,14,0,0},
{4,0,11,0,0},
{5,0,13,0,0},
{6,0,14,0,0},
{7,0,{11,12},0,0}
}

(* Expanding second element to become two identical elements, each with different Id, but same other elements *)
{
{1,0,13,0,0},
{2,0,11,0,0},
{2,0,12,0,0},
{3,0,14,0,0},
{4,0,11,0,0},
{5,0,13,0,0},
{6,0,14,0,0},
{7,0,11,0,0},
{7,0,12,0,0}
}


What would you recommend I do to perform these operations in an efficient way in Mathematica 11.1?

Realistic size data can be generated this way:

dict = Transpose[{ToString /@ RandomInteger[100, 10000],
ToString /@ RandomInteger[{101, 200}, 10000]}];
len = 10^6;
test = Transpose[{Range@len, ConstantArray[0, len],
ToString /@ RandomInteger[200, len],
ConstantArray[0, len], ConstantArray[0, len]}];


UPDATE:

So far, as per answer from C.E., plus a bit of additional optimization, this is the fastest version (net AbsoluteTiming[] of search/replace commands is approx. 31 seconds on my machine):

rules = Dispatch[
{a:Repeated[_,{2}], #, b:Repeated[_,{2}]}:>{a,#2,b}& @@@ dict
];
patt = {_, _, Alternatives@@Union[First/@dict], _,_};

(pos = Position[data, patt, {1}, Heads -> False];) //AbsoluteTiming
(* {1.41256, Null} *)

(res = Join[Flatten[
ReplaceList[#, rules, 1]&/@ Extract[data,pos], 1],
data[[Range@Length@data~Complement~Flatten@pos]]
];) //AbsoluteTiming
(* {29.8576, Null} *)


Side note: ReplaceList[] is internally parallelized, plus the cost of moving data between kernels for such small operations, ParallelMap[] is only going to make things worse.

UPDATE 2:

Using an Association instead of Replace for dictionary lookup, plus manually reconstructing ReplaceList provides additional 55% speed boost, because the structure of what's being replaced is known.

hash = Association[#[[1,1]]->#[[All,2]]&/@GatherBy[dict[[All,;;2]],First]];
patt = {_, _, Alternatives@@Union[First/@dict], _,_};
pos = Position[data, patt, {1}, Heads -> False];

(res = Join[
Flatten[Block[{m=ConstantArray[{##},Length@hash[#3]]},
m[[All,3]]=hash[#3];m]& @@@ Extract[data,pos], 1],
data[[Range@Length@test~Complement~Flatten@pos]]
];) // AbsoluteTiming

(* {16.4524, Null} *)


Down from several minutes to a hair over 18 seconds - great stuff! Anything else I'm missing?

Thank you!

• You could try if the performance of this is any good: rules = Dispatch[{a : Repeated[_, {2}], #, b : Repeated[_, {2}]} :> {a, #2, b} & @@@ dict]; Flatten[ReplaceList[#, rules] & /@ data, 1]. Apr 27, 2017 at 11:50
• That's a great approach. In fact, I didn't even know about Dispatch[]. Thank you for that! But your code drops elements 4 and 6, which had values in the new ID system, and not the old ID, thus they didn't exist in the dictionary. If I add the step of deleting all elements which match rules and Joining the two lists, would that kill the performance gain? Can this be done in the same step where values, not found in the lookup, are retained? Apr 27, 2017 at 17:43
• I didn't notice that there are such cases, I've added an answer that shows how I would modify it to work also for such lists. It would be a good idea to use AbsolutTiming to figure out if it affects the timing. Apr 27, 2017 at 18:06

I propose the following:

update[rules_][list_] := With[{res = ReplaceList[list, rules]},
If[res == {}, {list}, res]
]

rules = Dispatch[{a : Repeated[_, {2}], #,
b : Repeated[_, {2}]} :> {a, #2, b} & @@@ dict];

Flatten[update[rules] /@ data, 1]

• This is getting close. However... run time is still VERY slow on the full set (over 10000 dictionary pairs, 15Mil records in data). I've added code to create sample data to the question. Apr 27, 2017 at 19:32
• ReplaceList is running unnecessarily over elements which are known to have a new ID already. This seems to help: patt={_,_,Alternatives@@Union[First/@dict],__}; pos=Position[data,patt,{1},Heads->False]; res=Join[ Flatten[ReplaceList[#,rules,1]&/@Extract[data,pos],1], data[[Range@Length@test~Complement~Flatten@pos]] ]; This takes ~30seconds on my machine, whereas the original code takes several minutes on same data. Apr 27, 2017 at 19:35
• @GregoryKlopper Right now, I can't come up with anything better than what you've done. I'll tell if I do. Apr 28, 2017 at 2:41
• Thank you very much. I've just added one more improvement (using an Association and manually replacing part 3 of the list) - half the execution time. Your answer was the inspiration. If you can think of anything please let me know. Apr 28, 2017 at 3:11