Ask Your Question
1

It takes so long to generate dictionary of GL elements.

asked 2018-02-05 19:03:25 -0500

Symbol 1 gravatar image

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?

edit retag flag offensive close merge delete

Comments

It seems hash(g) lies between 0 and 15 for all g. It does not make any sense to me.

Symbol 1 gravatar imageSymbol 1 ( 2018-02-05 19:21:25 -0500 )edit

Found this https://trac.sagemath.org/ticket/10950. Maybe I should update my Sage.

Symbol 1 gravatar imageSymbol 1 ( 2018-02-05 19:36:48 -0500 )edit

What version of Sage were you using?

slelievre gravatar imageslelievre ( 2018-02-05 23:12:52 -0500 )edit

Mutability and hashability are two different things. In the above case, for instance:

sage: G = GL(4,2)
sage: g = G.one()
sage: g.__hash__()
0

There is a __hash__ method, so g is hashable. There are $16$ different hash-values:

sage: list( set( [ g.__hash__() for g in G ] ) )
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

But $G$ has order

sage: prod( [ 2^4-2^k for k in [0..3] ] )
20160
sage: G.order()
20160

In order to define a dictionary where gis 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?

dan_fulea gravatar imagedan_fulea ( 2018-02-06 02:50:18 -0500 )edit

@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 turn g into 16-bit int 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.

Symbol 1 gravatar imageSymbol 1 ( 2018-02-06 18:14:04 -0500 )edit

1 answer

Sort by » oldest newest most voted
0

answered 2018-02-06 16:11:39 -0500

dan_fulea gravatar image

The generation took on my slow linux machine approximatively 10s CPU time...

sage: %timeit -n1 GL4dict = { g : None for g in GL(4,2) }
1 loop, best of 3: 9.29 s per loop

This is

sage: version()
'SageMath version 8.1, Release Date: 2017-12-07'

Please update to the new version, if there is such a big run time difference.

edit flag offensive delete link more

Comments

Thank you. I did update from 8.0 to 8.1. I was not aware of the version-issue because I thought I was quite new. Now everything works fine. hash(g) gives crazy numbers such as -32759827368972486.

Symbol 1 gravatar imageSymbol 1 ( 2018-02-06 18:05:00 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-02-05 19:03:25 -0500

Seen: 51 times

Last updated: Feb 06