Services & ResourcesWolfram ForumsMathGroup Archive

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

Efficient Sorting Algorithm

• To: mathgroup at smc.vnet.net
• Subject: [mg38140] Efficient Sorting Algorithm
• From: bghiggins at ucdavis.edu (Brian Higgins)
• Date: Tue, 3 Dec 2002 04:35:13 -0500 (EST)
• Sender: owner-wri-mathgroup at wolfram.com

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

• Follow-Ups:
  • Re: Efficient Sorting Algorithm
    • From: Daniel Lichtblau <danl@wolfram.com>