Fast operations between binary numpy arrays

There's the BitVector library that allows you to pack the bits denser with a nice API, although different than numpy. It may be easier to use it than implement the operations on top of numpy. Although it should be possible via the bitwise XOR.

If your -1 is represented as 0 in the bit vector and 1 as 1, then the dot product is the number of positions that have the same value in both vectors minus number of positions where the value differs.

You get the differing positions by XOR:

>>> m1_1 = BitVector(bitstring='0110')>>> m2 = BitVector(bitstring='0101')>>> xor = m1_1 ^ m2>>> print(xor)0011

You then sum this vector but you must take into account that zeros here mean 1 and ones mean -1. Therefore we'll subtract the number of bits set to one from the number of bits set to zero:

>>> bits_zero = xor.length() - xor.count_bits()>>> bits_zero - xor.count_bits()0>>> # Or just>>> xor.length() - 2 * xor.count_bits()0

It should be straightforward to port this approach to Numpy if your vector sizes align with the integer sizes (i. e. a multiple of 32, 64). Otherwise, you'll have to treat the last int specially.

Edit: As @Michael Butscher writes in the comment, you'll miss the function count_bits in Numpy. Going byte by byte, the lookup table is indeed small and efficient.

Note: although this should be more memory efficient, it's not certain if it brings any speedup. You must do your benchmarks.

Edit: Benchmark results

I've just timed the pure numpy (storing bit in int) vs. the BitVector.

vector_len = 64*1024matrix_rows = 1024# I tested various data typesdtype = np.int8m1 = 2 * np.random.randint(2, dtype=dtype, size=[matrix_rows, vector_len]) - 1m2 = 2 * np.random.randint(2, dtype=dtype, size=vector_len) - 1# this is being timed:dot = m1.dot(m2)m1_bv = [BitVector(bitlist = (row + 1) / 2) for row in m1]m2_bv = BitVector(bitlist = (m2 + 1) / 2)# this is being timed:dot_bv = [vector_len - 2 * (m1_row ^ m2_bv).count_bits() for m1_row in m1_bv]

The results are (64-bit Intel laptop processor):

• BitVector: horrific - 1min 7s ± 1.51 s
• int8: 192 ms ± 3.39 ms
• int16: 192 ms ± 1.6 ms
• int32: 40.6 ms ± 228 µs
• int64: 48.6 ms ± 307

I didn't get yet to implementing the bitwise dot product with Numpy but you can see that

1. BitVector is not really viable here.
2. Small integer types save memory but they make it harder for Numpy to optimize the computations.