ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 22 Sep 2018 09:31:58 +0200It takes so long to generate dictionary of GL elements.https://ask.sagemath.org/question/40987/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?
Tue, 06 Feb 2018 02:03:25 +0100https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/Comment by Symbol 1 for <p>The following command</p>
<pre><code>GL4dicthash={hash(g):None for g in GL(4,2)}
</code></pre>
<p>takes 9 seconds to execute. On the other hand</p>
<pre><code>GL4dict={g:None for g in GL(4,2)}
</code></pre>
<p>takes minutes and does not seem to terminate.</p>
<p>If I understand python dictionary correctly, they should take about the same time. So what happened?</p>
https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=40988#post-id-40988It seems `hash(g)` lies between 0 and 15 for all `g`. It does not make any sense to me.Tue, 06 Feb 2018 02:21:25 +0100https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=40988#post-id-40988Comment by Symbol 1 for <p>The following command</p>
<pre><code>GL4dicthash={hash(g):None for g in GL(4,2)}
</code></pre>
<p>takes 9 seconds to execute. On the other hand</p>
<pre><code>GL4dict={g:None for g in GL(4,2)}
</code></pre>
<p>takes minutes and does not seem to terminate.</p>
<p>If I understand python dictionary correctly, they should take about the same time. So what happened?</p>
https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=40989#post-id-40989Found this https://trac.sagemath.org/ticket/10950. Maybe I should update my Sage.Tue, 06 Feb 2018 02:36:48 +0100https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=40989#post-id-40989Comment by slelievre for <p>The following command</p>
<pre><code>GL4dicthash={hash(g):None for g in GL(4,2)}
</code></pre>
<p>takes 9 seconds to execute. On the other hand</p>
<pre><code>GL4dict={g:None for g in GL(4,2)}
</code></pre>
<p>takes minutes and does not seem to terminate.</p>
<p>If I understand python dictionary correctly, they should take about the same time. So what happened?</p>
https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=40990#post-id-40990What version of Sage were you using?Tue, 06 Feb 2018 06:12:52 +0100https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=40990#post-id-40990Comment by dan_fulea for <p>The following command</p>
<pre><code>GL4dicthash={hash(g):None for g in GL(4,2)}
</code></pre>
<p>takes 9 seconds to execute. On the other hand</p>
<pre><code>GL4dict={g:None for g in GL(4,2)}
</code></pre>
<p>takes minutes and does not seem to terminate.</p>
<p>If I understand python dictionary correctly, they should take about the same time. So what happened?</p>
https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=40993#post-id-40993Mutability 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 `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?Tue, 06 Feb 2018 09:50:18 +0100https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=40993#post-id-40993Comment by Symbol 1 for <p>The following command</p>
<pre><code>GL4dicthash={hash(g):None for g in GL(4,2)}
</code></pre>
<p>takes 9 seconds to execute. On the other hand</p>
<pre><code>GL4dict={g:None for g in GL(4,2)}
</code></pre>
<p>takes minutes and does not seem to terminate.</p>
<p>If I understand python dictionary correctly, they should take about the same time. So what happened?</p>
https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=41006#post-id-41006@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.Wed, 07 Feb 2018 01:14:04 +0100https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=41006#post-id-41006Answer by dan_fulea for <p>The following command</p>
<pre><code>GL4dicthash={hash(g):None for g in GL(4,2)}
</code></pre>
<p>takes 9 seconds to execute. On the other hand</p>
<pre><code>GL4dict={g:None for g in GL(4,2)}
</code></pre>
<p>takes minutes and does not seem to terminate.</p>
<p>If I understand python dictionary correctly, they should take about the same time. So what happened?</p>
https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?answer=41003#post-id-41003The 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.
Tue, 06 Feb 2018 23:11:39 +0100https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?answer=41003#post-id-41003Comment by slelievre for <p>The generation took on my slow linux machine approximatively 10s CPU time...</p>
<pre><code>sage: %timeit -n1 GL4dict = { g : None for g in GL(4,2) }
1 loop, best of 3: 9.29 s per loop
</code></pre>
<p>This is</p>
<pre><code>sage: version()
'SageMath version 8.1, Release Date: 2017-12-07'
</code></pre>
<p>Please update to the new version, if there is such a big run time difference.</p>
https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=43720#post-id-43720@Symbol 1 -- you can accept the answer if it solves the problem in your question.
If an answer solves your question, please accept it by clicking the "accept" button
(the one with a check mark, below the upvote button, score, and downvote button,
at the top left of the answer).
This will mark the question as solved in the list of questions on the main page of
Ask Sage, as well as in lists of questions related to a particular query or keyword.Sat, 22 Sep 2018 09:31:58 +0200https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=43720#post-id-43720Comment by Symbol 1 for <p>The generation took on my slow linux machine approximatively 10s CPU time...</p>
<pre><code>sage: %timeit -n1 GL4dict = { g : None for g in GL(4,2) }
1 loop, best of 3: 9.29 s per loop
</code></pre>
<p>This is</p>
<pre><code>sage: version()
'SageMath version 8.1, Release Date: 2017-12-07'
</code></pre>
<p>Please update to the new version, if there is such a big run time difference.</p>
https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=41005#post-id-41005Thank 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`.Wed, 07 Feb 2018 01:05:00 +0100https://ask.sagemath.org/question/40987/it-takes-so-long-to-generate-dictionary-of-gl-elements/?comment=41005#post-id-41005