[GAP Forum] Lookup tables in gap

[Alexander Hulpke]

Dear Arnaldo Mandel, Dear Forum,

> First, obvious solution: produced an ordered list L of all labels
> (that was fast!).  Although L is longer than N, it is true that the
> label of N[i] is L[i], so, given a label s, the corresponding record
> is N[Position(L,s)].  Also, since L is ordered, lookup should be fast.
>
> That seems fine, so I tried a traversal, which I know takes linear
> time on the number of links.  It took forever.  I had the routine
> print a progress report, and it was clearly crawling.

from the description given, I understand that you have a list of  
strings, in which you are searching. The performance problems indicate  
that the strings are not immutable. In this case GAP cannot store that  
the list is sorted, but checks it every time.
(The reason for this slightly disturbing behaviour is that it would be  
possible to change one of the strings (and thus making the list not  
sorted) without the list noticing. Section "Sorted Lists and Sets" in  
the manual has more details.

A workaround is easy. Simply do
for i in L do
   MakeImmutable(i);
od;

This should give you a substantial speedup.

All the best,

    Alexander Hulpke

-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke