It takes so long to generate dictionary of GL elements.
The following command
GL4dicthash={hash(g):None for g in GL(4,2)}
takes 9 seconds to execute. On the other hand
GL4dict={g:None for g in GL(4,2)}
takes minutes and does not seem to terminate.
If I understand python dictionary correctly, they should take about the same time. So what happened?
It seems
hash(g)
lies between 0 and 15 for allg
. It does not make any sense to me.Found this https://trac.sagemath.org/ticket/10950. Maybe I should update my Sage.
What version of Sage were you using?
Mutability and hashability are two different things. In the above case, for instance:
There is a
__hash__
method, sog
is hashable. There are $16$ different hash-values:But $G$ has order
In order to define a dictionary where
g
is a key, this element should be immutable. Then for each new key one has to check if the key is already used. This takes time. And before we try to understand the time problem, why do we need to work with such a complicated dictionary?@slelievre before 8.0 now 8.1 and everything is good now. @dan_fulea: I am implementing a group action that is quite tedious. GL(4,2) acts on [0..15] by left-multiplying its binary expression as a column vector in GF(2)^4. And then act on
Subsets([0..15])
. I would like to cache the action as there are only 20160·16 possibilities. Moreover, if there is a (fast) way to turng
into 16-bitint
then I need an array of size 65536·16, which is still affordable. What would make it triumph is that looking up array entry takes ~100ns.