There are very long arrays with byte-sized entries. I want to make it so that each bit from every byte becomes its own array entry.
An example of what I want to do is to manipulate the following array:
[0b00001111, 0b01010101, 0b11110000]
to get this array:
[0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0]
I know that it is possible to do this via loops but I want to see whether there is a faster method (with less time complexity) first.
On
Benchmark with 10^5 random bytes:
3.89 ± 0.08 ms bits_Kelly_juanpa
5.84 ± 0.06 ms bits_Kelly_4
6.24 ± 0.16 ms bits_Kelly_3
6.44 ± 0.05 ms bits_Kelly_2
6.64 ± 0.06 ms bits_Kelly_1
177.09 ± 1.33 ms bits_sbottingota_1
177.28 ± 1.83 ms bits_sbottingota_3
183.16 ± 2.39 ms bits_sbottingota_2
Python: 3.11.4 (main, Sep 9 2023, 15:09:21) [GCC 13.2.1 20230801]
Benchmark code:
from timeit import timeit
from statistics import mean, stdev
from random import shuffle
import numpy as np
import os
import sys
def bits_Kelly_1(a):
bitss = [[*map(int, f'{i:08b}')] for i in range(256)]
bits = []
for byte in a:
bits += bitss[byte]
return bits
def bits_Kelly_2(a):
bitss = [[]]
for _ in range(8):
bitss = [bits + [bit] for bits in bitss for bit in (0, 1)]
bits = []
for byte in a:
bits += bitss[byte]
return bits
bitss = [[]]
for _ in range(8):
bitss = [bits + [bit] for bits in bitss for bit in (0, 1)]
def bits_Kelly_3(a):
bitss_ = bitss
bits = []
for byte in a:
bits += bitss_[byte]
return bits
def bits_Kelly_4(a):
i = int.from_bytes(bytes(a))
s = f'{i:0{len(a)*8}b}'
s = s.translate(s.maketrans('01', '\0\1'))
return list(s.encode())
# Using unpackbits() from juanpa's answer
def bits_Kelly_juanpa(a):
a = np.frombuffer(bytes(a), dtype=np.uint8)
return list(np.unpackbits(a).tobytes())
def bits_sbottingota_1(l):
l_expanded = []
for n in l:
l_expanded.extend(format(n, "08b"))
return [int(n) for n in l_expanded]
def bits_sbottingota_2(l):
l = map(lambda n: format(n, "08b"), l)
return [int(item) for sublist in l for item in sublist]
def bits_sbottingota_3(l):
return list(map(int, (b for num in l for b in format(num, "08b"))))
funcs = [bits_Kelly_1, bits_Kelly_2, bits_Kelly_3, bits_Kelly_4, bits_Kelly_juanpa, bits_sbottingota_1, bits_sbottingota_2, bits_sbottingota_3]
expect = [0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0]
for f in funcs:
result = f([0b00001111, 0b01010101, 0b11110000])
print(result == expect or result, f.__name__)
a = os.urandom(10**5)
times = {f: [] for f in funcs}
def stats(f):
ts = [t * 1e3 for t in sorted(times[f])[:5]]
return f'{mean(ts):6.2f} ± {stdev(ts):4.2f} ms '
for _ in range(50):
shuffle(funcs)
for f in funcs:
t = timeit(lambda: f(a), number=1)
times[f].append(t)
for f in sorted(funcs, key=stats):
print(stats(f), f.__name__)
print('\nPython:', sys.version)
Using Kelly's program I added a few variants of sbottingota
def bits_sbottingota_4(l):
table = [format(num, "08b") for num in range(256)]
return list(map(int, (b for num in l for b in table[num])))
def bits_sbottingota_5(l):
table = [list(map(int, format(num, "08b"))) for num in range(256)]
result = []
for b in l:
result.extend(table[b])
return result
def bits_sbottingota_5f(l):
table = [list(map(int, f'{num:08b}')) for num in range(256)]
result = []
for b in l:
result.extend(table[b])
return result
bitstable = [list(map(int, format(num, "08b"))) for num in range(256)]
def bits_sbottingota_6(l):
result = []
for b in l:
result.extend(bitstable[b])
return result
def bits_sbottingota_7(l):
result = []
for b in l:
result += bitstable[b]
return result
def bits_juanpa_1(l):
return [b for b in np.unpackbits(np.array(list(l), dtype=np.uint8))]
def bits_juanpa_2(l):
return list(np.unpackbits(np.array(list(l), dtype=np.uint8)).tobytes())
The results on my machine (a bit slower than Kelly's)
The fast versions are 4 times slower, but the slow versions are about as fast as Kelly's
12.91 ± 0.19 ms bits_juanpa_2
23.30 ± 0.35 ms bits_Kelly_3
23.59 ± 0.33 ms bits_Kelly_2
23.80 ± 0.20 ms bits_Kelly_1
24.38 ± 0.12 ms bits_sbottingota_7
25.50 ± 0.34 ms bits_sbottingota_5f
26.23 ± 0.10 ms bits_sbottingota_5
26.35 ± 0.31 ms bits_sbottingota_6
75.57 ± 0.43 ms bits_juanpa_1
142.38 ± 0.75 ms bits_sbottingota_4
170.92 ± 0.59 ms bits_sbottingota_2
172.71 ± 0.62 ms bits_sbottingota_3
184.91 ± 0.98 ms bits_sbottingota_1
It is not the conversion from number to bits (format()) that takes most of the time but the manipulation of the lists.
The construction of the lookup table is a bit more clear using list(map(int, format(num, "08b"))) then Kelly's method.
The f-strings are faster than format().
I tried if creating a local ref to the lookup table makes things faster but it differs on several runs, so most likely it is negligible, just as the length of the local variable name. And Python already knows that bitstable is global because it uses a LOAD_GLOBAL instruction. It does not look in the locals first. The global dictionary is a big larger than the local dictionary and that could have a small influence in the lookup in case of name collision.
I am surprised that list::+= is faster than list::extend (see disassembly)
For an array of size 100'000 it does not matter if you pre-calculate the bitstable as a global variable
The numpy version (juanpa) is the fastest, if you know numpy (peeked at Kelly's code: to_bytes())
Bytecode for result.extend(bitstable[b]):
10 12 LOAD_FAST 1 (result)
14 LOAD_METHOD 0 (extend)
16 LOAD_GLOBAL 1 (bitstable)
18 LOAD_FAST 2 (b)
20 BINARY_SUBSCR
22 CALL_METHOD 1
24 POP_TOP
Bytecode for result += bitstable[b]:
16 12 LOAD_FAST 1 (result)
14 LOAD_GLOBAL 0 (bitstable)
16 LOAD_FAST 2 (b)
18 BINARY_SUBSCR
20 INPLACE_ADD
22 STORE_FAST 1 (result)
Looks like INPLACE_ADD is faster for lists than CALL_METHOD (extend), or it is the number of instructions 3 compared to 2.
On
So, I just want to point out, if performance really matters here, then probably, you would be best served by using numpy. You should start with an unsigned, 8-bit integer array:
>>> import numpy as np
>>> arr = np.array([0b00001111, 0b01010101, 0b11110000], dtype=np.uint8)
Then, you can do:
>>> np.unpackbits(arr)
array([0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0,
0, 0], dtype=uint8)
Or:
>>> np.unpackbits(arr).reshape(-1, 8)
array([[0, 0, 0, 0, 1, 1, 1, 1],
[0, 1, 0, 1, 0, 1, 0, 1],
[1, 1, 1, 1, 0, 0, 0, 0]], dtype=uint8)
Or perhaps more efficiently:
>>> np.unpackbits(arr[..., None], axis=1)
array([[0, 0, 0, 0, 1, 1, 1, 1],
[0, 1, 0, 1, 0, 1, 0, 1],
[1, 1, 1, 1, 0, 0, 0, 0]], dtype=uint8)
I think what you mean by using loops is something like this:
Output:
You could do this in one line like this:
But if speed is your biggest concern, you should probably use numpy:
Output:
You may also want to reshape your ndarray so that each number has its own row:
Output: