Just regard bitvectors as floating point vector using l2 norm is much faster for BLAS.
@@ -43,13 +43,16 @@ class BruteForceBLAS(BaseANN):
lens = (X ** 2).sum(-1) # precompute (squared) length of each vector
X /= numpy.sqrt(lens)[..., numpy.newaxis] # normalize index vectors to unit length
self.index = numpy.ascontiguousarray(X, dtype=self._precision)
+ elif self._metric == 'hamming':
+ # Regarding bitvectors as vectors in l_2 is faster for blas
+ X = X.astype(numpy.float32)
+ lens = (X ** 2).sum(-1) # precompute (squared) length of each vector
+ self.index = numpy.ascontiguousarray(X, dtype=numpy.float32)
+ self.lengths = numpy.ascontiguousarray(lens, dtype=numpy.float32)
elif self._metric == 'euclidean':
lens = (X ** 2).sum(-1) # precompute (squared) length of each vector
self.index = numpy.ascontiguousarray(X, dtype=self._precision)
self.lengths = numpy.ascontiguousarray(lens, dtype=self._precision)
- elif self._metric == 'hamming':
- self.index = numpy.ascontiguousarray(
- list(map(numpy.packbits, X)), dtype=numpy.uint8)
elif self._metric == 'jaccard':
self.index = X
else:
@@ -58,14 +61,8 @@ class BruteForceBLAS(BaseANN):
def query(self, v, n):
return [index for index, _ in self.query_with_distances(v, n)]
- popcount = []
- for i in range(256):
- popcount.append(bin(i).count("1"))
-
def query_with_distances(self, v, n):
"""Find indices of `n` most similar vectors from the index to query vector `v`."""
- if self._metric == 'hamming':
- v = numpy.packbits(v)
if self._metric != 'jaccard':
# use same precision for query as for index
@@ -79,10 +76,8 @@ class BruteForceBLAS(BaseANN):
# argmin_a (a - b)^2 = argmin_a a^2 - 2ab + b^2 = argmin_a a^2 - 2ab
dists = self.lengths - 2 * numpy.dot(self.index, v)
elif self._metric == 'hamming':
- diff = numpy.bitwise_xor(v, self.index)
- pc = BruteForceBLAS.popcount
- den = float(len(v) * 8)
- dists = [sum([pc[part] for part in point]) / den for point in diff]
+ # Just compute hamming distance using euclidean distance
+ dists = self.lengths - 2 * numpy.dot(self.index, v)
elif self._metric == 'jaccard':
dists = [pd[self._metric]['distance'](v, e) for e in self.index]
else:
@@ -92,8 +87,5 @@ class BruteForceBLAS(BaseANN):
def fix(index):
ep = self.index[index]
ev = v
- if self._metric == "hamming":
- ep = numpy.unpackbits(ep)
- ev = numpy.unpackbits(ev)
return (index, pd[self._metric]['distance'](ep, ev))
return map(fix, indices)
