Can someone help me further optimize the following Cython code snippets? Specifically,
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)