Services & ResourcesWolfram ForumsMathGroup Archive

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

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>