Re: Fast List Manipulation & more - some results
- To: mathgroup at smc.vnet.net
- Subject: [mg23052] Re: Fast List Manipulation & more - some results
- From: Mark Van De Vyver <mvdv at bigfoot.com>
- Date: Sat, 15 Apr 2000 03:00:17 -0400 (EDT)
- References: <8cme1k$1vb@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Further to my previous post and Hartmuts suggestions I've
a) clarified (I think) the problem desc,
b) provided some improved versions with timings
I make some some -*** observations ***- along the way in case anyone is
interested.. also if any of the gurus read this and think it's about
as fast as can be achieved, could they post a brief 'that's as good as
it will get' note it just to let me (and possibly others) know.
Note the example code I posted was incorrect in that the list structure
fed in was not as I'd thought it was. The following functions all do
the same thing, though output format may vary.
a) The Problem(s)
(some code to generate an example data set is at the end of this post)
Take a list, l, in the form {{i,x,y}}, and il in the form {i}
l={{1., 3.82217, 7.49982}, {5., 0.802604, 5.05635}, {3., 4.80672,
0.269348}, {5., 7.63638, 5.88913}, {2., 4.14006, 0.0792415}, {3.,
7.51374, 8.02024}, {4., 6.09094, 1.64494}, {5., 1.15211, 1.22434}, {3.,
0.173347, 2.83916}, {2., 4.7505, 5.24301}};
il={1., 2., 3., 4., 5.};
initially the problem was to generate two lists, rl1 and rl2.
rl1 is the max of ALL x's and y's for each i,
i.e. {i,Max[x's,y's],Min[x's,y's]}
rl2 is the cummulative list of x's and y's for each i,
i.e. {i,x's,y's}
A second version, which seemed too involved and which Hartmut
posted a partial solution for was to take the Max/Min of the x's and
the Max/Min of the y's seperately, which was easy when he pointed out
using MapThread.
i.e. {i,{Max[x's],Min[x's]},{Max[x's],Min[x's]}}
rl2 is the cummulative list of x's and y's for each i,
i.e. {i,{x's},{y's}}
For the moment we leave aside the issue of generating rl2.
*** It is generating rl1 for the last version of this problem that this
post relates to, since the first version, and rl2 should be simpler
cases (?) ***
So:
rl1={{1., {3.82217, 7.49982}, {3.82217, 7.49982}}, {2., {4.7505,
5.24301}, {4.14006, 0.0792415}}, {3., {7.51374, 8.02024}, {0.173347,
0.269348}}, {4., {6.09094, 1.64494}, {6.09094, 1.64494}}, {5.,
{7.63638, 5.88913}, {0.802604, 1.22434}}}}
My initial function was wrong and is very slow for larger problems
though it seems fastest for small versions where number Length[il]=5
and Length[l]=10
The timing table output in the code below shows (for different relative
list lengths):
Length[il] is approx quarter Length[l]
n m[2] m[3] m[4] m[5] m[6] m[7]
10 0.047 0.016 0.014 0. 0.016 0.016
50 0.047 0.061 0.063 0.061 0.063 0.061
100 0.108 0.110 0.108 0.110 0.125 0.125
1000 2.5 1.233 1.280 1.188 1.25 1.202
3000 16.625 3.280 3.327 3.235 3.264 3.438
10000 178.43 12.36 12.93 12.719 12.84 12.46
Length[il] is approx half Length[l]
n m[2] m[3] m[4] m[5] m[6] m[7]
10 0.015 0.014 0.016 0.014 0. 0.015
50 0.062 0.062 0.077 0.063 0.061 0.078
100 0.11 0.13 0.14 0.14 0.13 0.141
1000 4.233 1.344 1.375 1.265 1.343 1.327
3000 34.20 3.953 4.093 3.922 3.969 4.046
10000 389.63 15.76 16.18 15.48 15.57 15.93
Length[il] is approx Length[l]
n m[2] m[3] m[4] m[5] m[6] m[7]
10 0.047 0.016 0.014 0.016 0.016 0.014
50 0.077 0.079 0.077 0.077 0.094 0.077
100 0.172 0.186 0.202 0.172 0.202 0.188
1000 8.717 1.704 1.764 1.641 1.688 1.719
3000 73.93 5.905 6.016 5.858 5.719 6.061
10000 876.9 16.78 17.87 15.87 17. 17.87
I've some questions which I hope someone can answer..
1) For m[3],m[4] etc why does placing the definition of u2 inside the
module m[3], etc. speed things slightly? the code below has u1 ans u2
defined ourtside of m[*], but drop it inside and you'll see what I mean.
2) For m[6] vs m[7] and m[5] vs m[6] why does using Dispatch not make
much of a difference
3) Why does applying Compile not work, note you'll need to use the
Dispatch versions since Compile does not seem to like the /. x_?NumberQ
versions. However even then it still refuses to use the Compiled
version.
4) Any remarks on m[4] vs m[5] From what I've been reading in the
posts of this group I really expected m[5] using dispatch to be much
faster - (see [mg12872] Re:Re:Efficient way to merge lists--Programming
help)
5) Can anyone tweak these further? Since m[?] will be used many, many
times in an iteration slight improvements will be significant.
Now some remarks about each function. A requirement is that the
function m[*] should allow mi and ma to be initialised externally, i.e.
so we can loop over m[] passing different lists, l for the same il.
I've included initialisation inside m[*] inorder to facilitate building
the timing table...
m[1]:
This is Hartmuts earlier post altered to iterate over the whole of l,
and il. It's good for small il and l, and in it's original form.
m[2]:
Scan over with an update function that replaces an element of a list of
maximums and minimums.
m[3]:
Same as m[2] except the update function now sets the value of a
variable rather than replace part of a list. This seems to be the most
significant seed improvement.
-**** Defining u2 within the module for m[] speeds things slightly
again ****-
m[4] thru m[7]:
These are variations using Dispatch for one /. and /@ instead of Scan.
TIA
Mark
(********** START CUT and PASTE HERE **************)
(* Define a function to update the max and min values *)
u1[{x_, y_, z___}, il_List] := Module[{pos, vals = {y, z}},
pos = Position[il, x][[1, 1]];
allmin[[pos]] = MapThread[Min, {Part[allmin, pos], vals}];
allmax[[pos]] = MapThread[Max, {Part[allmax, pos], vals}];
(* End of Module *)];
u2[{x_, y_, z___}] := Module[{omi = mi[x], oma = ma[x], vals = {y, z}},
mi[x] = MapThread[Min, {omi, vals}];
ma[x] = MapThread[Max, {oma, vals}];
(* End of Module *)];
m[1][il_List, l_List] :=
Module[{tl = 1, ti = 0, lenil = Length[il], lenl = Length[l], min,
max,vals, rl},
Off[Part::"partw"];
rl = {};
While[++ti <= lenil,
tl = 1;
min = Infinity {1, 1};
max = -min;
While[l[[tl, 1]] != il[[ti]],
tl++;
(* EoWhile l[[tl, 1]] != *)];
While[l[[tl, 1]] === il[[ti]] && tl <= lenl,
min = MapThread[Min, {min, vals = Rest[l[[tl]]]}];
max = MapThread[Max, {max, vals}];
tl++;
While[l[[tl, 1]]1 != il[[ti]],
tl++;(* EoWhile l[[tl, 1]] != *)];
(* EoWhile l[[tl, 1]] == *)];
rl = {rl, {il[[ti]], max, min}};
(* EoWhile ++ti *)];
On[Part::"partw"];
Partition[Flatten[rl], 5]]
m[2][il_List, l_List] := Module[{i = 1, j = 1, k = 1},
ClearAll[allmin, allmax];
Off[Set::"partw", Part::"partw"];
allmin = Table[{Infinity, Infinity}, {Length[il]}];
allmax = -allmin;
Scan[(u1[#, il]) &, l];
On[Set::"partw", Part::"partw"];
il /. x_?NumberQ :> {il[[i++]], allmax[[j++]], allmin[[k++]]}
(* End of Module *)]
m[3][il_List, l_List] := Module[{i = 1, j = 1, k = 1, tmpl},
Off[Set::"partw", Part::"partw"];
(mi[#] = {Infinity, Infinity}) & /@il;
(ma[#] = -{Infinity, Infinity}) & /@ il;
Scan[(u2[#]) &, l];
On[Set::"partw", Part::"partw"];
tmpl = il /. x_?NumberQ :> {x, ma[x], mi[x]};
ClearAll[mi, ma];
tmpl
(* End of Module *)]
m[4][il_List, l_List] := Module[{i = 1, j = 1, k, tmpl},
Off[Set::"partw", Part::"partw"];
r = Dispatch[# -> {#, ma[#], mi[#]} & /@ il];
(mi[#] = {Infinity, Infinity}) & /@ il;
(ma[#] = -{Infinity, Infinity}) & /@ il;
Scan[(u2[#]) &, l];
On[Set::"partw", Part::"partw"];
tmpl = il /. r;
ClearAll[r];
tmpl
(* End of Module *)]
m[5][il_List, l_List] := Module[{i = 1, j = 1, k, tmpl},
Off[Set::"partw", Part::"partw"];
r = Dispatch[# -> {#, ma[#], mi[#]} & /@ il];
(mi[#] = {Infinity, Infinity}) & /@ il;
(ma[#] = -{Infinity, Infinity}) & /@ il;
(u2[#]) & /@ l;
On[Set::"partw", Part::"partw"];
tmpl = il /. r;
ClearAll[mi, ma, r];
tmpl
(* End of Module *)]
m[6][il_List, l_List] := Module[{i = 1, j = 1, k, tmpl},
Off[Set::"partw", Part::"partw"];
(mi[#] = {Infinity, Infinity}) & /@ il;
(ma[#] = -{Infinity, Infinity}) & /@ il;
l /. {x_, y_, z_} :> (u2[{x, y, z}]);
tmpl = il /. x_?NumberQ :> {x, ma[x], mi[x]};
On[Set::"partw", Part::"partw"];
ClearAll[mi, ma, r];
tmpl
(* End of Module *)]
m[7][il_List, l_List] := Module[{i = 1, j = 1, k, tmpl},
Off[Set::"partw", Part::"partw"];
r = Dispatch[# -> {#, ma[#], mi[#]} & /@ il];
(mi[#] = {Infinity, Infinity}) & /@ il;
(ma[#] = -{Infinity, Infinity}) & /@ il;
l /. {x_, y_, z_} :> (u2[{x, y, z}]);
tmpl = il /. r;
On[Set::"partw", Part::"partw"];
ClearAll[mi, ma, r];
tmpl
(* End of Module *)]
(* Generate data for timing table *)
Function[{n},
timel[n] =
Table[{N[Random[Integer, {1, n/2}]], Random[Real, 9],
Random[Real, 9]}, {n}];] /@
{10, 50, 100, 1000, 3000, 10000};
Function[{n},
timeil[n] =
Union[First /@ timel[n]];] /@ {10, 50, 100, 1000, 3000, 10000};
(* Generate Timing Table *)
TableForm[
Table[ (m[i][timeil[#], timel[#]]; // Timing // First)/Second, {i, 2,
7} ] & /@ {10, 50, 100, 1000, 3000, 10000} ,
TableHeadings -> {{10, 50, 100, 1000, 3000, 10000},
Table[m[i], {i, 2, 7}]}]
(********** END CUT and PASTE HERE **************)
--
Mark Van De Vyver
Department of Accounting and Finance
University of Western Australia
mailto:mvdv at bigfoot.com
http://www.bigfoot.com/~mvdv
Sent via Deja.com http://www.deja.com/
Before you buy.