Re: [Algorithms] pattern search for large integer

[Tony C. <to...@mi...>]

If there is nothing special about the list (i.e. it's not sorted or indexed=
 in a useful way), then you must visit every element in it at least once, s=
o the best you can possibly hope to do is O(n).

After that, all you can really do is hope to improve the running time by a =
constant factor - which quickly gets into low-level stuff like what kinds o=
f prefetching and bit-twiddling stuff happens to be efficient on your targe=
t architecture.

Touching the memory is likely to be the dominating factor in performance on=
 a modern architecture - proper prefetching will probably be your biggest w=
in.

If you have multiple bit patterns to match on the same run, you are probabl=
y best testing all the bit patterns in one pass (assuming the number of pat=
terns to match is a relatively small number) to avoid refetching the memory=
 multiple times. If you have lots of patterns to match (to many to do singl=
e pass), break it up into cache-sized blocks and do multiple passes on a bl=
ock before moving on to avoid refetching.

All of these tricks are just hacking away at the constant factor, though.

- Tony

-----Original Message-----
From: gda...@li... [mailto:gdalgorithms-=
lis...@li...] On Behalf Of Drakie Awita
Sent: Sunday, March 25, 2007 8:56 PM
To: GDA...@li...
Subject: [Algorithms] pattern search for large integer

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<=3DX<Y<Z<=3D127).  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.

Any faster algorithm?