RE: Efficient Sorting Algorithm
- To: mathgroup at smc.vnet.net
- Subject: [mg38170] RE: [mg38140] Efficient Sorting Algorithm
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Wed, 4 Dec 2002 03:24:55 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
>-----Original Message----- >From: bghiggins at ucdavis.edu [mailto:bghiggins at ucdavis.edu] To: mathgroup at smc.vnet.net >Sent: Tuesday, December 03, 2002 10:35 AM >To: mathgroup at smc.vnet.net >Subject: [mg38170] [mg38140] Efficient Sorting Algorithm > > >Hi, > >I have two lists (in general of different length) that have the >following structure > >s1 = Table[{FromCharacterCode[Table[Random[Integer, {65, 69}], {4}]], > Random[Integer, {1, 2000}]}, {100}]; >s2 = Table[{FromCharacterCode[Table[Random[Integer, {65, 69}], {4}]], > Random[Integer, {1, 2000}]}, {200}]; > >I am then interested in obtaining all the strings in s1 that match >with those in s2. At the present time I use the following agorithm to >find the matches > >myList = Flatten[Outer[List, s1, s2, 1], 1];Select[myList, >(First[First[#]] == First[Last[#]]) &] > >This works fine, but when s1 and s2 are large ( e.g. 3000 or more >elements) then Outer seems inefficient. My question: does anyone have >a suggestion that would be more efficient than my kludge approach. >Note I have tried Intersection, which finds all the matches, i.e. > >myList2 = Intersection[s1,s2, SameTest -> (#1[[1]] == #2[[1]] &)]; > >But I have not been successful in selecting all the matched pairs >using myList2 > >Thanks in advance for any suggestions. > >Brian > Brian, perhaps you might like to check out myMatch0[s1_, s2_] := Module[{ll = Flatten[Outer[List, s1, s2, 1], 1]}, Sort[Select[ll, (#[[1, 1]] === #[[2, 1]] &)]]] (* your solution sorted for comparison *) myMatch[s1_, s2_] := With[{tst = (#1[[1]] === #2[[1]] &)}, Module[{l1 = Split[Intersection[s1, s2, SameTest -> tst], tst], l2 = Split[Intersection[s2, s1, SameTest -> tst], tst]}, Flatten[MapThread[Outer[List, #1, #2, 1] &, {l1, l2}], 2]]] In[30]:= myMatch0[s1, s2] == myMatch[s1, s2] Out[30]= True In[34]:= myMatch[{{AAAA, 1}, {AAAA, 1}}, {{AAAA, 2000}, {AAAA, 2000}}] Out[34]= {{{AAAA, 1}, {AAAA, 2000}}, {{AAAA, 1}, {AAAA, 2000}}, {{AAAA, 1}, {AAAA, 2000}}, {{AAAA, 1}, {AAAA, 2000}}} -- Hartmut Wolf