Re: [Algorithms] pattern search for large integer

[Niklas F. <ni...@gr...>]

> I have a large list of integers; each integer is of 128-bit in size.
> How to answer this question efficiently:
>
> find those integers with bit-X equals to 1, bit-Y equals to 0, and
> bit-Z equals to 1 (0<=X<Y<Z<=127).  ie, find integers in a large list
> with bit pattern of "*1*0*1*", where '1', '0', and '1' appears at
> fixed bit position X, Y, and Z.  The values of X, Y, Z are arbitrary
> between [0,127] and have no observable pattern.
>
> The brute-force method of iterating through the list via bit-mask
> check works, but it's O(n), and not practical if the list size is in
> millions and there're multiple bit patterns to be matched on the same
> integer list.
Is brute-force really too slow? Note that as you have described the 
problem, no algorithm can be faster than (n/8), since you would expect 
on average (n/8) numbers to match the pattern. So whatever algorithm you 
can come up with, you can never be more than 8 times faster than brute 
force.

And whatever complicated algorithm you come up with is likely to carry 
additional costs, such as using more memory, destroying the cache etc. 
Also, if you do any kind of processing on the numbers you may find the 
cost of that (n/8*p, where p is the processing cost) to be comparable to 
the (n) cost of finding the numbers.

You might be better off just using the brute force algorithm and 
optimizing it as much as possible with SIMD instructions and prefetch of 
cache lines.

// Niklas