Is there any better algorithm than O (N) to find the first bit set in a bitarray, which is mostly contiguous blocks?
Suppose we have a bitarray and we know that the array is of very low complexity: it consists mostly of contiguous "1" or "0" chunks. That is, if we read two consecutive bits, the probability of their identity is much higher than 50%. For example:
00001111100011100000111111100000
This is a typical array in this format as it is composed mostly of contiguous chunks of the same bit. Similar:
00000000000000000000011111111000
But this is not the case:
10100110001010011100110001000111
This concept can be formalized in more precise ways, such as "iterating through an array that we see at most a bit (N) bits", or "the probability that two consecutive bits will be identical is> 95%", but I Not sure if it matters.
My question is, what is the fast algorithm for finding the index of the first bit set in a bitmap (i.e. 1
)?
source to share
Count Leading Zeros clz
can do this much faster depending on your system . This is typical for ARM architectures. With this operation, you can count several unsorted bits at once. This with some changes (mostly free on ARM) might speed things up a bit. Count 0s, not bits, offset of known bits, repetition.
Still linear, but much faster linear, especially if the data has many runs in it, as you suggest.
source to share
You haven't defined your input model unambiguously, but assume it matches the Markov chain. This means that the first bit is what it is, and then when you go from one bit to the next, the probability of bit flipping values is p and the probability of stopping is (1-p). If you know p but little p, you can make some progress on this problem. Check the first bit first. If it's 1, then you're done. Otherwise, you are looking for the first jump from 0 to 1. Note that if you count k consecutive bits at a time, then the probability of getting exactly one jump in those k bits is kp (1-p) ^ (k-1). On the other hand, the probability of getting 2 or more transitions is essentially the same as getting exactly 2 transitions if p is small relative to k, and this probability is k * (k-1) p ^ 2 (1-p) ^ (k-2) / 2. Do you want to,so that the first quantity is not too small and the second quantity is much less. This will happen, for example, if you choose k = round (1 / sqrt (p)). Then if p is small, the probability that you will get one transition over k consecutive bits is essentially sqrt (p), and the probability that you will get two transitions is basically p / 2, which is much less. So just check every kth bit until you see a 1, and then a binary search between the previous and current positions to find the first occurrence of 1. It will most likely be the first occurrence in 1. The expected running time is O (sqrt (p) * n + log (k)), assuming a Markov chain model and the probability of error is O (sqrt (p)). So if p is small and you know p, this is a good compromise (assuming you accept the model, of course).and the second number was much less. This will happen, for example, if you choose k = round (1 / sqrt (p)). Then if p is small, the probability that you will get one transition over k consecutive bits is essentially sqrt (p), and the probability that you will get two transitions is basically p / 2, which is much less. So just check every kth bit until you see a 1, and then a binary search between the previous and current positions to find the first occurrence of 1. It will most likely be the first occurrence in 1. The expected running time is O (sqrt (p) * n + log (k)), assuming a Markov chain model, and the error probability is O (sqrt (p)). So if p is small and you know p, this is a good compromise (assuming you accept the model, of course).and the second number was much less. This will happen, for example, if you choose k = round (1 / sqrt (p)). Then if p is small, the probability that you will get one transition over k consecutive bits is essentially sqrt (p), and the probability that you will get two transitions is basically p / 2, which is much less. So just check every kth bit until you see a 1, and then a binary search between the previous and current positions to find the first occurrence of 1. It will most likely be the first occurrence in 1. The expected running time is O (sqrt (p) * n + log (k)), assuming a Markov chain model, and the error probability is O (sqrt (p)). So if p is small and you know p, this is a good compromise (assuming you accept the model, of course).if p is small, the probability that you will get one transition over k consecutive bits is essentially sqrt (p), and the probability that you will get two transitions is basically p / 2, which is much less. So just check every kth bit until you see a 1, and then a binary search between the previous and current positions to find the first occurrence of 1. It will most likely be the first occurrence in 1. The expected running time is O (sqrt (p) * n + log (k)), assuming a Markov chain model, and the error probability is O (sqrt (p)). So if p is small and you know p, this is a good compromise (assuming you accept the model, of course).if p is small, the probability that you will get one transition over k consecutive bits is essentially sqrt (p), and the probability that you will get two transitions is basically p / 2, which is much less. So just check every kth bit until you see a 1, and then a binary search between the previous and current positions to find the first occurrence of 1. It will most likely be the first occurrence in 1. The expected running time is O (sqrt (p) * n + log (k)), assuming a Markov chain model, and the error probability is O (sqrt (p)). So if p is small and you know p, this is a good compromise (assuming you accept the model, of course).So just check every kth bit until you see a 1, and then a binary search between the previous and current positions to find the first occurrence of 1. It will most likely be the first occurrence in 1. The expected running time is O (sqrt (p) * n + log (k)), assuming a Markov chain model and the probability of error is O (sqrt (p)). So if p is small and you know p, this is a good compromise (assuming you accept the model, of course).So just check every kth bit until you see a 1, and then a binary search between the previous and current positions to find the first occurrence of 1. It will most likely be the first occurrence in 1. The expected running time is O (sqrt (p) * n + log (k)), assuming a Markov chain model, and the error probability is O (sqrt (p)). So if p is small and you know p, this is a good compromise (assuming you accept the model, of course).
source to share
It seems to me that you can treat a bit array as a byte (or word). Read the bytes until you get a byte that is not 0. Then use one of the bit hacks, similar to this one , to determine which bit is in which byte.
The algorithm looks something like this:
bitPosition = 0 byteIndex = 0 while (array[byteIndex] == 0) { bitPosition += 8; ++byteIndex; } bitPosition += GetFirstSetBit(array[byteIndex]);
It's O (n / 8), which is still technically O (n), but it will be much faster than checking every bit.
Think about it, you can do it with words, words or four words and realize even more savings depending on your hardware.
If you want to find bit 0 following the first 1 bit, then the next 1 bit, etc., this algorithm still works. For example, if you are reading bytes and you find that the first bit of a set of bits is 4, you set the top three bits (which were previously 0), invert the value, and look for the first bit of the set. If the bit is not set, you loop back into the read byte loop, but invert each value as you read it.
You can go on like this endlessly. It's still O (n), but the constant is significantly less than if you were checking every bit every time.
source to share
So the problem at hand goes along the ray traversing the 3D array until you click to change the pixel value. There are two very different approaches that I know about speeding up such searches. Both are only useful if you need to perform the above operation on multiple rays, be they rays coming from the same point in different directions or rays coming from multiple origin points. I've done a bit of work on very large 2D meshes (floats, not bools), but generalization to 3D is straightforward.
The first approach is to start by creating a mipmap of your mesh. That is, for each 2x2 set of pixels in 2D (or 2x2x2 set of pixels in 3D), the number of non-zero values in the "2nd level" grid is stored. Then, for every 2x2 (or 2x2x2) set in the second level grid, add those numbers to the "third level" grid. Continue until you get a few pixels on the "highest level" grid. Note that on the pixels, the Nth level meshes are 2 times larger and higher (and deeper in the 3D case) than the original ones.
Suppose now that you are looking for the nearest pixel of the value 1, starting from a given point in a given direction. After you get to the border of the current second level mesh, you can check the value of the next second level pixels in the direction of your ray. If your data is really sparse, then the chances are that those pixels will indicate that all of its entries are 0 or 1. So you can skip the entire pixel. And now you are at the border of the third level grid, which is 4x4x4 pixels. If your data is really really sparse, you will again have the same value for all pixels and can go to a 4th level grid, with 8x8x8 pixels. If your data is really really REALLY sparse, you can go back to the 16x16x16 area ... Finally, you hit the N level grid.which tells you that there are pixels of different values. Now you can start decreasing the level of the grid you are looking into until you find a pixel of a different value. If the changes to your data are extremely sparse, the above search should take O (log N).
There are many mipmaps for anisotropic data at different rates of resolution in the other direction. The best choice will depend on the details of the problem.
Now the second approach is to create a quadtree for 2D data or an octree for 3D data. The basic idea, as with mipmaps, is to search for sparse data in O (log N) time. However, there are several fundamental differences.
First, quadtree (and octrees) are organized as trees, not arrays. Second, they encode transitions between pixel values, not pixel values. Third, they can have very variable depths in different regions of your data, depending on the level of transition density in those regions.
The latter feature, the ability to vary depth based on data density, results in significantly better performance than mipmaps when the transition density is quite variable. It is very possible that bad inputs preclude the benefits of mipmap, but such failures are more rare with quadrants.
For industrial applications, it can be helpful to try both approaches and see which leads to better performance. For example, it may happen that quads work better on the processor and mipmaps work better on the GPU, etc.
source to share
You can't do it less than O (N), where N is the number of elements in the array, but you don't need to scan every bit:
public class FirstBitSet
{
private static final int[] lookup =
{
0, 1, 2, 27, 3, 24, 28, 7, 4, 17, 25, 31, 29, 12, 14, 14,
5, 8, 18, 29, 26, 23, 32, 16, 30, 11, 13, 7, 28, 22, 15, 10,
6, 21, 9, 20, 19,
};
public static int firstBitSet(int i)
{
int j = i & -i;
int k = j % 37;
k = Math.abs(k);
int b = lookup[k];
return b;
}
}
E & OE. There may be some errors in the table, but you get the idea.
Note that this does not work for null inputs, so you need to filter them out.
source to share
Several answers here.
First, strictly speaking, you can't do better than O (N) because you have to scan every bit one way or another. Given the statement of the problem, most of which you can hope to be is to reduce the constant factor in O (N).
Secondly, many processors have hardware support that will allow you to scan a word at a time, rather than a bit at a time.
Third, and most importantly, I suspect that you can improve the performance of your application by changing the way you present your data. Travel length encoding is very efficient for encoding this kind of data for much faster processing.
Fourth, the Run-length encoding works well with the Huffman encoding . Early in my career, I dealt with Modified Huffman Codes for fax machine emulation. The fax data looks about the same as yours: 1 s stretch followed by 0 s spans; this data is usually transmitted as Huffman encoded travel lengths with the same bits. There are several additional smart optimizations in modified Huffman codes; for example, only run lengths are encoded, without specifying the quoting of the bit corresponding to the run, assuming that the bit is flipped between runs, etc.
I don't know the exact nature of your algorithm, but if it is something like image processing or signal processing and the bits corresponding to the pixel / signal do not change over an extended period of time, encoding the path length will take you very far, do you choose to combine it with additional compression through Huffman or other codes.
source to share