the context behind my issue is not important, as my question itself is fairly self-contained.
Im currently trying to assign numbers to sequences of bits. Such that, if i ask functionA
for bit sequence 42, it would return the corresponding bits, say "0110101011..." (not correct, just an example), and if i gave functionB
the sequence "0110101011...", it could give me the number 42.
Currently, the way im assigning each sequence's number is through the pattern
bits val
| 0 | 0 |
| 1 | 1 |
| 00 | 2 |
| 10 | 3 |
| 01 | 4 |
| 11 | 5 |
| 000 | 6 |
| 100 | 7 |
and so on and so fourth. Currently, the functions i have created to do this work as such
from itertools import product
def bit_lookup_num(lookup):
if lookup == '':
return -1
bits=[]
current_len=1
while lookup not in bits:
bits.extend(["".join(perm[::-1]) for perm in product(["0","1"],repeat=current_len)])
current_len =1
return bits.index(lookup)
def num_lookup_bit(lookup):
if lookup == -1:
return ''
bits=[]
current_len=1
while len(bits)-1<lookup:
bits.extend(["".join(perm[::-1]) for perm in product(["0","1"],repeat=current_len)])
current_len =1
return bits[lookup]
Where num_lookup_bit
functions as my prior example's functionA
, and bit_lookup_num
serves as functionB
. However, my implementation becomes quite slow for large bit sequences, and its due to my use of the product()
function from itertools. There surely must be a faster way to accomplish this than generating every possibility using product()
and checking its position in the list, alas i have yet to discover this workaround.
How can i improve upon these functions by avoiding brute-force algorithms?
CodePudding user response:
Your bit sequences are just, take the binary representation of val 2, chop off the leading 1
, and reverse it:
def bit_sequence(val):
# [3:] removes the '0b1'
return bin(val 2)[3:][::-1]
# return bin(val 2)[:2:-1] would be a bit faster, but a bit harder to understand
def val_for_bit_sequence(bits):
binary = '1' bits[::-1]
return int(binary, 2) - 2
CodePudding user response:
Incremental approach:
def num_lookup_bit(num):
x = 2
bits = ''
while num >= 0:
bits = '0' if num%x < x/2 else '1'
num -= x
x *= 2
return bits
def bit_lookup_num(bits):
x = 2
num = 0
for b in bits:
num = x//2 if b == '0' else x
x *= 2
return num-1
CodePudding user response:
Here is an inelegant way to do this:
import math
def num_lookup_bit(lookup: int) -> str:
log = int(math.log2(lookup))
diff = lookup - sum(2**i for i in range(1, log))
return f"{diff:0{log}b}"
def bit_lookup_num(lookup: str) -> int:
length = len(lookup)
return sum(2**i for i in range(1, length)) int(lookup, 2)
They key thing to understand is that you first index into a "bin" which corresponds to the binary digit, then you count from there!
There's probably a super obvious elegant way to do this, but the above seems to work for me.