[GAP Forum] Lookup tables in gap

[Arnaldo Mandel]

Frank Lübeck wrote (on Jun 30, 2008):
 > Dear Arnaldo Mandel, Dear Forum,

Hello Frank and everybody,

 > 
 > 
 > > 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.
 > 
 > Short answer: Use N[PositionSorted(L,s)]. More generally, always use
 > 'PositionSorted' instead of 'Position', when you know that your list
 > is sorted (but you are responsible to make sure that this is true).

Tried this, and again it is a no go.
The traversal ran for several hours until I killed it.

Then, tried yet a little hack, based on your example: called
IsSortedList(L) just after MakeImmutable(L).  I would have thought it
completely innocuous, just from the documentation.  Alas...

Up, up and away, SuperGAP!  It really flew, and for my practical
purposes was as fast as dealing with the modified structure, in which
all strings were substituted by numerical indices.

Amazing how much difference giving GAP a hint can make.

Thanks, it was a very interesting learning experience.

[]
am

-- 
Arnaldo Mandel                        
Departamento de Ciência da Computação - Computer Science Department
Universidade de São Paulo, Bra[sz]il	  
am at ime.usp.br
Talvez você seja um Bright http://the-brights.net Maybe you are a Bright.