Re: Efficient Sorting Algorithm
- To: mathgroup at smc.vnet.net
- Subject: [mg38258] Re: Efficient Sorting Algorithm
- From: "Allan Hayes" <hay at haystack.demon.co.uk>
- Date: Tue, 10 Dec 2002 04:10:34 -0500 (EST)
- References: <asn4ng$465$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
I give below some further speed-ups. The improvement, at least on the data I used, is due to using Split[Sort[_]] right at the start to parcel the data - it probably depends on there being a lot of repetition of the first term of the entries in the data. The code for Matchings6 below is faster than Daniel Lichblau's recently posted code - though he suggests that this might be speeded up by substituting numbers for strings and compiling. Data s1 = Table[{FromCharacterCode[Table[Random[Integer, {65, 69}], {4}]], Random[Integer, {1, 2000}]}, {6000}]; s2 = Table[{FromCharacterCode[Table[Random[Integer, {65, 69}], {4}]], Random[Integer, {1, 2000}]}, {12000}]; Get the members of s1 with the same first entry as some member of s2. Previous code (preserves order) Matched1[s1_,s2_]:= Cases[ s1,{Alternatives@@Union[s2[[All,1]]],_}] Matched1[s1,s2];//Timing {3.4 Second,Null} New code (does not preserve order) - note the use of s1[[Ordering[s1[[All, 1]]]]] to save on ordering with respect to the second entries Matched4[s1_,s2_]:= Cases[Split[s1[[Ordering[s1[[All,1]]]]], #1[[1]]===#2[[1]]&], {{Alternatives@@Union[s2[[All,1]]],_},___}] Matched4[s1,s2];//Timing {1.6 Second,Null} Get the full matchings (this code will work on {s1,s2 ,....,sn}, as well as just {s1, s2}) Matchings7[s_]:= Module[{st,pt,sp}, st = #[[Ordering[#[[All,1]]]]]&/@s; sp=Split[#,#1[[1]]===#2[[1]]&]&/@st; pt= (Alternatives@@(Intersection@@ st[[All,All,1]])); Transpose[Cases[#,{{pt,_},___}]&/@sp] ]; (ms7=Matchings7[{s1,s2}]);//Timing {3.46 Second,Null} Daniel Lichtblau (gives essentially the same information as Matchings7) myTest[l1_, l2_] := Module[{s1, s2, m = Length[l1], n = Length[l2], j, k, res = {}, ord }, s1 = Sort[l1]; s2 = Sort[l2]; For[j = 1; k = 1, j <= m && k <= n, Null, ord = Order[s1[[j,1]], s2[[k,1]]]; If[ord == 1, j++; Continue[]]; If[ord == -1, k++; Continue[]]; res = {res, {s1[[j]], s2[[k]]}}; j++; k++; ]; Partition[Partition[Flatten[res], 2], 2] ] myTest[s1,s2];//Timing {7.47 Second,Null} -- Allan --------------------- Allan Hayes Mathematica Training and Consulting Leicester UK www.haystack.demon.co.uk hay at haystack.demon.co.uk Voice: +44 (0)116 271 4198 Fax: +44 (0)870 164 0565