4
$\begingroup$

I'm looking for a way to optimize this procedure. This is the problem:

  • I have a list of bit vectors $\mathbf{A} = [ a_1, a_2, a_3, ..., a_n ]$
  • I have a list of bit vectors $\mathbf{B} = [ b_1, b_2, b_3, ..., b_m ]$

For every $b \in \mathbf{B}$, I need to find the following minimum hamming distance: $$\min \left\{ \forall x,y\in \mathbf{A}: hamming_d(x \land y, b) \right\}$$

if we define popcount as a function that counts the number of ones in a bit vector:

$$\min \left\{ \forall x,y\in \mathbf{A}: popcount(x \land y \oplus b) \right\}$$

In Python pseudo-code, it should look like this:

results = list()
for b in B:
    m = min(popcount((x & y) ^ b) for x in A for y in A)
    results.append(m)

A and B are both lists containing vectors of 0 or 1. & (and) and ^ (xor) are operations that are applied to every element of the bit vectors.

Any ideas?

$\endgroup$
  • $\begingroup$ What sort of performance are you getting now? How much faster do you need it to be? $\endgroup$ – Bill Barth Apr 6 '14 at 14:24
  • $\begingroup$ The current algorithm is $\mathcal{O}(n^2m)$. $n$ is a bit large (>10000), so this algorithm is really slow. It would be nice if I could get something closer to $\mathcal{O}(nm \log{n} )$. $\endgroup$ – dktyph Apr 6 '14 at 14:33
  • $\begingroup$ Right now, with n=50000 and m=10000 it takes some hours (~10) to complete. I would like to get it to minutes... $\endgroup$ – dktyph Apr 6 '14 at 14:36
  • $\begingroup$ How many bits long are your vectors? How are you storing them? $\endgroup$ – Jaime Apr 6 '14 at 15:18
  • $\begingroup$ Are you actually using Python or did you include that pseudocode just for illustrative purposes? Are your computations parallel? $\endgroup$ – Daniel Shapero Apr 6 '14 at 19:27
1
$\begingroup$

This is not a full answer, but it's possible to get bounds that could possibly be turned into a more efficient solution. For example if you have b : 00001111 x : 01010101 ^ ^ then regardless of y you will not get a lower popcount than 2 for this b and x. This ability to bound partial solutions makes me think that in practice you can make an algorithm that will be much faster than your brute force algorithm, even if the problem can be shown to be 'hard' in the worst case.

$\endgroup$
  • $\begingroup$ Yes, I'm trying some method like this with bounds. My biggest problem is the data structures - I'm using a binary tree to represent the multiple bit vectors. But I don't think it's a good structure for this kind of thing, though. $\endgroup$ – dktyph Apr 7 '14 at 0:41
1
$\begingroup$

Here's what I would try:

First, to count bits in an unsigned int z, i.e. "weigh" it:

n = table[ (z & 0xffff) ] + table[ (z >> 16) ];

where unsigned char table[1<<16]; is filled in ahead of time.

I tried to see if there was a way to simplify the outer loop, but XOR does not distribute over AND.

$\endgroup$
  • $\begingroup$ That was a good approach a few years ago. Today, the CPUs already have a built-in instruction POPCNT and GCC has the function __builtin_popcount() which are way faster. $\endgroup$ – dktyph Apr 23 '14 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.