MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Re: 3D Animations are killing my system
  • Next by Date: Re: Efficient Sorting Algorithm
  • Previous by thread: Re: Efficient Sorting Algorithm
  • Next by thread: Re: Efficient Sorting Algorithm