How to use a 5 or 6 bit integer in Python?
bokr at oz.net
Sat Dec 20 19:35:31 CET 2003
On Sat, 20 Dec 2003 19:38:36 +1100, Glen Wheeler <adsl5lcq at tpg.com.au> wrote:
>On 19 Dec 2003 06:02:23 GMT, bokr at oz.net (Bengt Richter) wrote:
>>If we can tease out a little more about your problem, maybe we can help better ;-)
>>E.g., how do your tuple-keys come into being and how many times are they re-used?
>>If there is no nesting, you could create a string key just by ''.join([chr(el) for el in tup])
>>which wouldn't be as compact as a compressed bit string, but would be smaller than the tuple.
>>If you were lucky, a change could gain you both time and space.
> I'll be implementing that this weekend, as my employer is expecting
>results before Christmas. Damn deadlines.
>>I'm curious what your dicts and their int tuples represent in the real world ;-)
> Well, I'm a researcher for an Australian university (University of
>Wollongong) and my current task is to enumerate every possible 6 digit
>binary Gray code.
> Most recently people have done the 5 digit BGCs, something which I
>have also accomplished, but never the 6 digit codes.
> For a graphical representation, think of a cube in n-dimensions,
>where n represents the number of digits in the code. A binary Gray
>code around that cube represents a path starting from any arbitrary
>point and then visiting every vertex exactly once.
> The applications of such research are enourmous, and I'll not go
>over them here, but that is my aim. To find the number of ways a 6
>dimensional fly could walk a 6d cube visiting every vertex exactly
> I've actually been working on this problem for many months now and
>have gotten so close. The previous best estimate for calculation time
>(with a program written in C, I might add) was 2.8 * 10^15 years.
>I've got the thing down to about 10^4 years. If the calculation
>becomes tractable on a supercomputer, e.g. Barossa hosted at
>www.ac3.com.au, then I'll run it on that.
> I hope that's sated your curiosity for now :). If you'd like any
>more information, or if anyone else would like to know anything about
>this, then I'll be happy to correspond with them. I don't know how
>on-topic it is for c.l.py.
Just to see if I understand your problem statement, does the following (though it's slow)
do what you are trying to do? If so, what would be the point of generating
all those gray code sequences? IOW, how are you going to use them? Assuming my
prog generated all the 6-bit grey code seqences to a monster file, all the 64-number
sequences packed into 64-byte strings end to end, then you would either have to
read that file sequentially, or seek to some point and read 64 bytes to get a
given gray code sequence. If the latter, how about an algorithm that would
do a virtual seek into the whole data as a virtual file, and then generate
what you would read? I.e., there would be no point in storing all that data
if you could easily generate an arbitrary segment of it. Of course, maybe that's
not so easy ;-) But I'm wonder what the use is going to be, and the access pattern,
if you assumed availability in a monster file, virtual or not.
If you really do want to generate all that data, I suppose the loop and recursions
could be fanned out to parallel processing. But first, do I understand the problem?
====< gray.py >=========================================================
# gray.py -- enumerate n-bit gray codes
# 20031220 10:34:27 alpha version by Bengt Richter. No warranties ;-)
Enumerate all possible complete n-bit gray code sequences
returning a list of 2**n-length strings whose bytes each
contain a complete gray code sequence in the ord values.
visit_mask = 2L**(2**n)-1
nbits = [1<<i for i in xrange(n)]
vbits = [1L<<i for i in xrange(2**n)]
codes = 
def visit(curr=0, visited=0L, code=''):
"""visit curr, and recursively available successors"""
visited |= vbits[curr]
code += chr(curr)
if visited == visit_mask:
for nbit in nbits:
succ = curr^nbit
if vbits[succ]&visited: continue
visit(succ, visited, code)
for start in xrange(2**n):
if __name__ == '__main__':
codes = enumgraycodes(int(sys.argv))
for code in codes:
print ''.join(['%02x'%ord(c) for c in code])
Example: (even 4 bits generates >3mb and takes a while, so I won't post it ;-)
[10:41] C:\pywk\clp\gray>python gray.py 2
[10:41] C:\pywk\clp\gray>python gray.py 3
More information about the Python-list