Edit Question - KnowledgeHub

Title Body

I have a list of N 64-bit integers whose bits represent small sets. Each integer has at most k bits set to 1. Given a bit mask, I would like to find the first element in the list that matches the mask, i.e. element & mask == element . Example: If my list is: index abcdef 0 001100 1 001010 2 001000 3 000100 4 000010 5 000001 6 010000 7 100000 8 000000 and my mask is 111000 , the first element matching the mask is at index 2. Method 1: Linear search through the entire list. This takes O( N ) time and O(1) space. Method 2: Precompute a tree of all possible masks, and at each node keep the answer for that mask. This takes O(1) time for the query, but takes O(2^64) space. Question: How can I find the first element matching the mask faster than O( N ), while still using a reasonable amount of space? I can afford to spend polynomial time in precomputation, because there will be a lot of queries. The key is that k is small. In my application, k <= 5 and N is in the thousands. The mask has many 1s; you can assume that it is drawn uniformly from the space of 64-bit integers. Update: Here is an example data set and a simple benchmark program that runs on Linux: http://up.thirld.com/binmask.tar.gz . For large.in , N =3779 and k =3. The first line is N , followed by N unsigned 64-bit ints representing the elements. Compile with make . Run with ./benchmark.e >large.out to create the true output, which you can then diff against. (Masks

Tags (comma-separated) Cancel