[GAP Forum] Lookup tables in gap
hulpke at math.colostate.edu
Sat Jun 28 03:48:08 BST 2008
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
This should give you a substantial speedup.
All the best,
-- 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
More information about the Forum