Simple search algorithms
ama...@gmail.com
in programming.
I have a list of boolean such as {0,0,0,0,1,0,0,1,1,0,0,0,0}
I would like to find the fastest way to list the position of each "1".
It is critical for me to reduce the number of test to the *minimum*.
Some research on google gave me 2 methods: the linear search and the
binary search. Does anyone know anything more efficient?
thanks you in advance
Bo Yang
the element in the list? Absolutely no. So, there is no way to archieve
what you want under less than linear time.
Roberto Waltman
>I have a list of boolean such as {0,0,0,0,1,0,0,1,1,0,0,0,0}
>I would like to find the fastest way to list the position of each "1".
>It is critical for me to reduce the number of test to the *minimum*.
>Some research on google gave me 2 methods: the linear search and the
>binary search. Does anyone know anything more efficient?
A binary search is used to find a particular value in a sorted list.
It is not useful at all in your case.
If the "boolean" values (in what language?,) were encoded as
individual bits in another value, you could use them as indexes into
an array (or as a hash), with each array element being the
corresponding list of positions.
It is not possible to know if this is doable with the little
information you provided, and probably will be limited to relatively
small lists.
Roberto Waltman
[ Please reply to the group,
return address is invalid ]
Logan Shaw
> Sorry if the solution to this problem is obvious but I am totally new
> in programming.
>
> I have a list of boolean such as {0,0,0,0,1,0,0,1,1,0,0,0,0}
>
> I would like to find the fastest way to list the position of each "1".
> It is critical for me to reduce the number of test to the *minimum*.
As someone else said, if you already have a list such as this, there
is no way to find all 1's without examining every element.
However, you may still be able to speed things up somewhat.
The first observation is that you may have control over how the list
is stored and created. Maybe you have lots of 0's and very few 1's,
in which case you could use a sparse data structure. For example,
instead of storing the actual bits, you could store the positions
which have a 1 in them in a tree or hash. (After all, a list of
booleans is not really any different from a set of integers.) If
you have a million positions and only 1000 of them are 1's, and if
you are searching the list as often as you are setting or clearing
the booleans, that could yield a performance improvement, because
you should be able to directly iterate over the list of 1 values
(i.e. by visiting every node in the tree or whatever data structure
you used to store the set).
The second observation is that you can store boolean values in a
single bit, and modern machines easily support 32-bit values. So
you can test 32 values at once to see if they are non-zero. Or
64 values at once with a 64-bit machine, etc., etc. This, again,
is helpful if there are lots of 0 values and very few 1 values.
A little less obviously, it's *also* helpful even if there aren't
mostly 0 values, because it makes the data structure more compact
and thus you will have better performance reading the data from
memory -- you will only need 1/8th the bandwidth compared to storing
each boolean in an 8-bit byte.
- Logan
ama...@gmail.com
Thank you guys for your help and explanations. it is very helpful.
I want to apologize because I forgot to give you 2 very important
informations:
- As you guessed Logan they are very few 1's. Sometime there is only
one.
- when I talked about test, I forgot to tell you that I have the
possibility as well to know if there is at least a "1" in any subset
of the list. And this kind of test is as fast as testing a single
element.
I realized that the last information is quite important and change the
problem. sorry about
that.
Logan Shaw
> On Feb 24, 8:35 pm, Logan Shaw <lshaw-use...@austin.rr.com> wrote:
>> aman...@gmail.com wrote:
>>> Sorry if the solution to this problem is obvious but I am totally new
>>> in programming.
>>> I have a list of boolean such as {0,0,0,0,1,0,0,1,1,0,0,0,0}
>>> I would like to find the fastest way to list the position of each "1".
>>> It is critical for me to reduce the number of test to the *minimum*.
>> Maybe you have lots of 0's and very few 1's,
>> in which case you could use a sparse data structure.
> - when I talked about test, I forgot to tell you that I have the
> possibility as well to know if there is at least a "1" in any subset
> of the list. And this kind of test is as fast as testing a single
> element.
That makes the problem easy because in most cases you can eliminate
lots of work. If you can find an interval where some routine cheaply
shows that the entire interval has no "1" in it, you can eliminate
that entire section. Since there are very few "1"s overall, such
intervals would be easy to find.
The simplest way to go about this would be to use a recursive function.
It would check the first half of a range and the second half also, using
the routine that can cheaply check an entire range for "1"s. If either
interval shows no "1"s, it is eliminated. Most of the time, at least one
of the two intervals you check will be all "0"s because there are very
few "1"s.
That means this recursive function will cut the size of the problem in
half almost every time tests the first and second half, which should
make it overall quite fast. Then running time will be approximately
the logarithm of the length of the list of booleans, which is pretty good.
The recursive function would look something like this (which is
written in pseudocode):
find_1_bits_in_interval (int intervalstart, int intervalend,
list list_of_1_bits)
{
if (! range_contains_a_1 (intervalstart, intervalend))
{
return;
}
if (intervalstart == intervalend)
{
// interval size is just one item, and range_contains_a_1()
// returned true above, so intervalstart must be the index
// of a "1"
list_of_1_bits.append (intervalstart);
}
else
{
int intervalmiddle = (intervalstart + intervalend) / 2;
// check the first half
find_1_bits_in_interval (intervalstart, intervalmiddle);
// check the second half
find_1_bits_in_interval (intervalmiddle + 1, intervalend);
}
}
This is similar to a binary search, except the difference is that you
will sometimes need to examine both sub-intervals (but only if you have
more than a single "1" value in the list). In a binary search, you
always eliminate one of the two intervals. In this one, you do not
always eliminate one of the two, but you do eliminate them often if
you have very few "1"s.
Hope that helps.
- Logan
ama...@gmail.com
thanks a lot for your help
cheers
user923005
It might prove useful to use bitsets. The first function here finds
the first bit set in a 64 bit integer. The second function finds it
and clears it. These bitscan functions use something called de Bruijn
sequences.
http://en.wikipedia.org/wiki/De_Bruijn_sequence
If you need more than 64 items in your bit sets, then another method
would probably be better. On 64 bit CPUs (with 64 bit compilers)
these routines perform spectacularly.
///////////////////////////////////////////////////////////////////////////////
typedef unsigned long long Bitboard;
const int lsz64_tbl[64] =
{
0, 31, 4, 33, 60, 15, 12, 34,
61, 25, 51, 10, 56, 20, 22, 35,
62, 30, 3, 54, 52, 24, 42, 19,
57, 29, 2, 44, 47, 28, 1, 36,
63, 32, 59, 5, 6, 50, 55, 7,
16, 53, 13, 41, 8, 43, 46, 17,
26, 58, 49, 14, 11, 40, 9, 45,
21, 48, 39, 23, 18, 38, 37, 27,
};
//Gerd Isenberg's implementation of bitscan:
int GerdBitScan(Bitboard bb)
{
const Bitboard lsb = (bb & -(long long) bb) - 1;
const unsigned int foldedLSB = ((int) lsb) ^ ((int) (lsb >> 32));
return lsz64_tbl[foldedLSB * 0x78291ACF >> 26];
}
//Gerd Isenberg's implementation of bitscan with clear:
int GerdBitScanReset(Bitboard *bb)
{
const Bitboard lsb = (bb[0] & -(long long) bb[0]) - 1;
const unsigned int foldedLSB = ((int) lsb) ^ ((int) (lsb >> 32));
bb[0] &= (bb[0] - 1);
return lsz64_tbl[foldedLSB * 0x78291ACF >> 26];
}
These techniques (and others similar to these) are often used in game
programming.