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

Question

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!

Answer 1

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]