Can someone help me further optimize the following Cython code snippets? Specifically, a
and b
are np.ndarray
with int
value (range(256)) in them. They are one dimension arrays with dynamic length. resultHamming
is a one-dimension array with float value in it (dynamic length). bits
is an int
list (size 256).
The function is to compare two dynamic length bit vector, and return a similarity value as the distance of the two, where the length of each vector is a multiple of 2048-bit (256 bytes). I want to find the best match between these two bit vector by comparing each 2048-bit block, where each bit vector is represented as ndarray
(read the bit sequence byte by byte, thus each position is range from 0 to 2^8 = 256). Rule for matching is to find global minimum distance between all block pairs and allow one block in A to be matched with more than one block in B if they have smaller distance. Always compare the smaller size vector against the larger one.
The following code assumes b
vector is smaller. We can limit resultHamming
to be smaller than size of numArrayB
and only record numArrayB
smallest distance value, but need to track the current size when inserting new value into it. Even with current case (record all the pairwise distance), we actually know the final size of resultHamming
at the beginning.
def compare(a, b):
cdef double dis, hammingTotal = 0
cdef int numArrayA = int(a.size/256)
cdef int numArrayB = int(b.size/256)
cdef int i, j, k, l, index
bits = list(xrange(256))
# Prepare a bit number table for fast query
for l in xrange(256):
# nnz() counts the number of 1s in value
bits[l] = nnz(l)
resultHamming = []
for i in xrange(numArrayB):
# Count the number of 1-bits in i-th block of B
onesB = sum(bits[b[k+256*i]] for k in xrange(256))
for j in xrange(numArrayA):
# Count the number of 1-bits in j-th block of A
onesA = sum(bits[a[k+256*j]] for k in xrange(256))
# Calculate the hamming distance between i-th block of B and j-th block of A
hammingCur = sum(bits[b[i*256+k] ^ a[j*256+k]] for k in xrange(256))
dis = (hammingCur) / (onesA + onesB)
# Insertion current dis to resultHamming with sorted order
k = len(resultHamming) - 1
if dis >= resultHamming[-1]:
resultHamming.append(dis)
else:
resulthamming.append(resultHamming[k])
while k > 0 and resultHamming[k-1] > dis:
resultHamming[k] = resultHamming[k-1]
k -= 1
resultHamming[k] = dis
# Extract k smallest distance from the distance array
for k in xrange(numArrayB):
hammingTotal += resultHamming[k]
return round(hammingTotal/(numArrayB), 3)
compare
? \$\endgroup\$