How Optimize BK-Tree

I'm implementing a BK-Tree in Cython. For one million items, the search time is too long! It's ~30 seconds :( Here is my Cython code: # -*- coding: UTF-8 -*- from itertools impo

Solution 1:

You can save a lot of memory (and thus swapping and/or cache flushing) by representing your "256-bit hash" in 256 bits (32 bytes) instead of 256 or 512 bytes.

Python pseudocode:

num_bits_set = (0, 1, 1, 2, 1, etc etc, 7, 8)
assert len(num_bits_set) == 256

def ham_diff(a, b):
    h = 0
    for p, q in zip(a, b):
        h += num_bits_set[ord(p) ^ ord(q)]
    return h