> < ^ Date: Thu, 16 Dec 1993 11:35:05 +0000
> < ^ From: Steve Linton <sal@dcs.st-and.ac.uk >
< ^ Subject: Re: Efficiently locating records in lists

I'm writing some gap code to work with representations of simple Lie algebras.
Although I'm already very pleased with the performance, (the gap version is
more than 10 times faster than a Mathematica version!); I am finding that no
less than half of the time (according to "Profile") is spent looking up the
position of elements in lists -- using "Position" or "PositionProperty",... .
Now the next set of calculations involves even more of this type of operation.
So I would like any pointers on how to improve the efficiency of locating
elemets in list.

The key general idea is to use Sets rather than lists.

Suppose you have a = List[ <stuff> ] and you will want to do
Position(a, <thing>) lots of times, it is better to do:

b := ShallowCopy(a);
c := [1..Length(a)];
SortParallel(b,c);

then Position(a,<thing>) = c[Position(b,<thing>)]

and the Position calculation in b can be done by binary chop rather
than linear search.

Steve


> < [top]