I am programming c on linux and I have a big integer array, how to filter it, say, find values that fit some condition, e.g. value > 1789 && value < 2031. what's the efficient way to do this, do I need to sort this array first?
I've read the answers and thank you all, but I need to do such filtering operation many times on this big array, not only for once. so is iterating it one by one every time the best way?
If the only thing you want to do with the array is to get the values that match this criteria, it would be faster just to iterate over the array and check each value for the condition (O(n) vs. O(nlogn)). If however, you are going to perform multiple operations on this array, than it's better to sort it.
Sort the array first. Then on each query do 2 binary searches. I'm assuming queries will be like -
Find integers x such that a < x < b
First binary search would find the index i of the element such that Array[i-1] <= a < Array[i] and second binary search would find the index j such that Array[j] < b <= Array[j+1]. Then your desired range would be [i, j].
This algorithm's complexity is O(NlogN) in preprocessing and O(N) per query if you want to iterate over all the elements and O(logN) per query if you just want to count the number of filtered element.
Let me know if you need help implementing binary search in C. There is library function named binary_search() in C and lower_bound() and upper_bound() in C++ STL.
You could use a max heap implemented as an array of the same size as the source array. Initialize it with min-1 value and insert values into the max-heap as the numbers come in. The first check would be to see if the number to be inserted is greater than the first element, if it's not, discard it, if it is larger then insert it into the array. To get the list of numbers back, read all numbers in the new array till min-1.
To filter the array, you'll have to look at each element once. There's no need to look at any element more than once, so a simple linear search of the array for items matching your criteria is going to be as efficient as you can get.
Sorting the array would end up looking at some elements more than once, which is not necessary for your purpose.
If you can spare some more memory, then you can scan your array once, get the indices of matching values and store it in another array. This new array will be significantly shorter since it has only indices of values which match a specific pattern! Something like this
int original_array[SOME_SIZE];
int new_array[LESS_THAN_SOME__SIZE];
for ( int i=0,j=0; i<SOME_SIZE; i++)
{
if ( original_array[i]> LOWER_LIMIT && original_array[i]< HIGHER_LIMIT )
{
new_array[j++] = i;
}
}
You need to do the above once and form now on,
for ( int i=0; i< LESS_THAN_SOME_SIZE; i++ )
{
if ( original_array[new_array[i]]> LOWER_LIMIT && original_array[new_array[i]]< HIGHER_LIMIT )
{
printf("Success! Found Value %d\n", original_array[new_array[i]] )
}
}
So at the cost of some memory, you can save considerable amount of time. Even if you invest some time in sorting, you have to parse the sorted array every time. This method minimizes the array length as well as the sorting time ( at the cost of extra memory, of course :) )
Try this library: http://code.google.com/p/boolinq/
It is iterator-based and as fast as can be, there are no any overhead. But it needs C++11 standard. Yor code will be written in declarative-way:
int arr[] = {1,2,3,4,5,6,7,8,9};
auto items = boolinq::from(arr).where([](int a){return a>3 && a<6;});
while (!items.empty())
{
int item = items.front();
...
}
Faster than iterator-based scan can be only multithreaded scan...
