[GAP Forum] Performance degradation of LookupDictionary() for partitions between 4.7.2 and 4.7.6

[Matan Ziv-Av]

Hello,


there seems to be a decrease in the performance of LookupDictionary(), 
at least for partitions. A simple example is below:



In 4.7.6:

gap> d:=NewDictionary([[1],[2..10]],true);
<object>
gap> for i in PartitionsSet([1..10]) do AddDictionary(d,i,1); od ;
gap> time;
980
gap> Sum(PartitionsSet([1..10]),x->LookupDictionary(d,x));
115975
gap> time;
308640



In 4.7.2:

gap> d:=NewDictionary([[1],[2..10]],true);
<object>
gap> for i in PartitionsSet([1..10]) do AddDictionary(d,i,1); od ;
gap> time;
971
gap> Sum(PartitionsSet([1..10]),x->LookupDictionary(d,x));
115975
gap> time;
727


Perhaps when LookupDictionary was changed for IsListLookupDictionary, 
something like below should have been added:

#############################################################################
##
#M  LookupDictionary(<dict>,<obj>)
##
InstallMethod(LookupDictionary,"for sort dictionaries",true,
   [IsSortLookupDictionary,IsObject],0,
function(d,x)
   local p;
   p:=PositionFirstComponent(d!.entries,x);
   if p > Length(d!.entries) or d!.entries[p][1] <> x then
     return fail;
   else
     return d!.entries[p][2];
   fi;
end);


-- 
Matan Ziv-Av.                         matan at svgalib.org