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