In python 3, I wrote a generator to loop over bits in an integer, 5 bits at a time:
def int_loop(x):
while(x):
yield x%32
x//=32
This works, but a bit slow.
My question is: is there a preexisting module that doe this faster?
-
Is it faster without yield?JaDogg– JaDogg2018-12-10 16:06:09 +00:00Commented Dec 10, 2018 at 16:06
-
about the same speedyigal– yigal2018-12-10 16:06:52 +00:00Commented Dec 10, 2018 at 16:06
-
What size numbers are you using this on?Patrick Haugh– Patrick Haugh2018-12-10 16:07:22 +00:00Commented Dec 10, 2018 at 16:07
-
from 0 to 100000yigal– yigal2018-12-10 16:07:50 +00:00Commented Dec 10, 2018 at 16:07
-
2What's really interesting is that I tried replacing your remainder and division operations with bitwise AND and bitshift, and it actually slowed it down by a few percent... Python is an odd beast.Nick Mertin– Nick Mertin2018-12-10 17:05:22 +00:00Commented Dec 10, 2018 at 17:05
|
Show 3 more comments
2 Answers
I am not sure what you mean by 'too slow' but you could improve things a bit since you know that x in [0, 100000]:
def loop5b(x):
g1 = (x & 0b00000000000011111)
g2 = (x & 0b00000001111100000) >> 5
g3 = (x & 0b00111110000000000) >> 10
g4 = (x & 0b11000000000000000) >> 15
if g4:
return g1, g2, g3, g4
if g3:
return g1, g2, g3
if g2:
return g1, g2
if g1:
return g1,
return ()
This saves about '0.05' seconds at my end compared to your while loop ('0.052' seconds vs. '0.098' seconds for x in range(0, 100000)). I am certain you could even do better by writing that piece in Cython. But the real question is: Is it really worth it? Remember: "premature optimization is the root of all evil"~Donald Knuth
2 Comments
tobias_k
Instead of "saves about 0.05s", how about "saves almost 50%"? (I did not test to verify, though)
MEE
Because saying that it saves 50% is an exaggeration when the total runtime is less than the tenth of a second in both cases. The OP can of course provide more details explaining how he figured that his while loop was the bottleneck. The input space is pretty tiny for it to be a bottleneck. The OP can simply cache all values in memory if they are used that heavily.
This version
def my_5_bits(n):
m = 0b11111
while n:
yield n & m
n >>= 5
consistently saves some time:
n=0b1111010101010111010011010110010111011110101010101110100110101100101110
%timeit list(my_5_bits(n))
1.76 µs ± 8.15 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
against
%timeit list(int_loop(n))
1.98 µs ± 33.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
Comments
