Fast List Manipulation & more

*To*: mathgroup at smc.vnet.net*Subject*: [mg22965] Fast List Manipulation & more*From*: "Mark Van De Vyver" <mvyver at bigfoot.com>*Date*: Fri, 7 Apr 2000 02:54:47 -0400 (EDT)*Organization*: The University of Western Australia*Sender*: owner-wri-mathgroup at wolfram.com

Hi, I have been looking over previous posts re: fast list extraction, manipulation, etc., and it seems that to get the 'fastest' routine depends on the specific nature of the problem. I have not been able to recast my problem into one of the existing mg examples, partly I suspect because I cannot fully trandlate what is at time fairly cryptic code so I am posting this request even though there are some excellent pieces of example code out there (e.g. [mg12872] and the excerpts below) I've included (what seems to be the fastest) snippets from previous posts that I thought might be helpful. The problem is essentially this (using Mathematica 4.0 on NT 4.0 server): With list l={{i,x(i),y(i),..}}, and list il={i} extract the Max and Min of all the x's, y's,... for each i. In another setting we may also use an InterpolatingFunction, and in another we want just the maximums of the x's and the maximums of just the y's etc.but these can wait, unless there aresimple, fast solutions? il is built from l, but the i's are not neccessarily contiguous, both lists can be small, growing large Length[il]=1 to 2000, Length[l]=1 to 100,000. The relationship between the length of il and l is relatively straightforward, if il is length n then l is length k(n)+n, where k is a linear function of n, typically 3-50. Here i, x, y,.. are Real i, can be large (+/-) and x, y typically in the range of -1 to1, unlikely to ever be 9+ (I've noticed in some examples that this can make a difference!). In a seperate setting the x,y can be large, in the order of 10^2 One other criterion is memory :) If a large l is fed in a small result list, say r, may be returned Length[il]===Length[r]. Since this is going to be looping v.v.v. frequently it's important that Mathematica free memory, as well as be fast. (To be honest I've always stuggled to get Mathematica to give back what it takes in memory, even following the usual suggestions.) What I'd like to know is if anyone can come up with something fatser than what I have below, and what do people think of some alternatives ideas (hacked from other MG posts) that I've not been able to get to work :( Some ideas I had were to alter ss3 in [mg20688] to take the Max and Min rather then look at an interval at a time, though I'm not sure how to efficiently handle looking over x ,y, ... (* a slightly altered ss3 from [mg20688] *) ss3[events_List, gaps_Interval] := Module[{t = Length[events], se = Sort[events], bag = {}}, Do[While[t > 0 && se[[t]] > gaps[[i, 2]], --t]; While[t > 0 && se[[t]] >= gaps[[i, 1]], bag = {bag, t}; --t], {i, Length[gaps], 1, -1}]; Delete[se, List /@ Flatten[bag]]] It may also be possible to alter [mg12872], but now rather than /matchingselecting a single value from the larger list, we need to build a list of matching values... Another idea was to hack [mg21058] to build a list for each i and then look over that for the maximum and minmum, again though I was having trouble seeing how to modify this to tract the whole sequnces sublists {i, x, y,...} for each i by modifying: (#2- #1) & @@@ Cases[DeleteCases[Partition[t, 2, 1], Alternatives @@ nt, {2}], {_, _}] (* some data *) n = 500; tmp = Sort[ Flatten[Table[N[Random[Integer, {-n, n}]], {i, n}], 1]]; l[n] = Table[{tmp[[i]] , Random[Real, {-9, 9}], Random[Real, {-9, 9}]}, {i,n}]; il[n] = Union[tmp]; ClearAll[tmp, n]; (* MV1 - no laughing :) *) mv1= Compile[{{il, _Real, 1}, {l, _Real, 2}}, Table[({il[[j]], Max[#1], Min[#1]}) & [#1[[2]] & /@ Select[#1, #1[[1]] == il[[j]] &] & [l]], {j, 1, Length[il]} ] ]; (* Timing Pent Pro 200 *) mv1[il[20], l[20]]; // Timing mv1[il[100], l[100]]; // Timing mv1[il[500], l[500]]; // Timing mv1[il[1000], l[1000]]; // Timing Out[171]= {0. Second, Null} Out[172]= {0.031 Second, Null} Out[173]= {0.157 Second, Null} Out[174]= {3.734 Second, Null} Out[175]= {15.687 Second, Null} Well that's it. Look forward to any suggestions, TIA Mark

**Follow-Ups**:**Re: Fast List Manipulation & more***From:*Hartmut Wolf <hwolf@debis.com>