LabVIEW
How can I get the indexes of the biggest 40 data from a 1D array?
Solved!
Here's a solution that gives the indices of the 40 largest elements.
It can still be improved a little bit, but is certainly faster than your search approach. How big is your array?
(the "solution" in the post above gives the values of the largest 39 elements (not indices!), something completely different)
altenbach wrote:It can still be improved a little bit, ....
OK, here's the improvements I made on a quick hunch.
For a 10M array of random data it is about 60x faster (100ms vs 7000ms) than my simple solution above. (it's about 30x faster for a 1M array).
Basically, here we only keep the top 40 elements in an array and keep the currently smallest element in a shift register. If the new element is larger than the currently smallest element, we replace the smallest element by the new element, sort the top 40 array, and tag the currently smallest element. If the new element is smaller, we don't do anything.
You have to be careful, though, because the algorithm is now data dependent and can be slow for certain pathalogical data.
For example if the input is a perfectly sorted array, the penalty is very big, while if we have a reverse sorted array the algorithm is extremely fast. For random input arrays, the chance to find a new top 40 element gets smaller very quicky and we win because we mostly execute the empty case.
Modify as needed. You need to test on your typical data to make sure it is suitable.
I am sure there are even more optimized possibilities, anyone want to try? 😄
If you are looking for trivially simple code, here's yet another alternative. For a 10M array it's about 30x slower than the optimized solution but about twice as fast as my first solution, so it is certainly not competitive. It is probably sufficient for small datasets.
It just shows that there are quite a few ways to do all this. 😉
(slow, but simple!)
Maybe we should do a challenge competition. Who can make the fastest solution? 😄
Coq rouge wrote:
I was just wondering. How will your largest40IndicesFaster.vi cope with several equal number in the array. Will it not fail in such cases. Your last suggestion will cope better with this situation I think.
Well, you can always try, but I don't think it will fail. The array is initialized with all -inf, and the smallest element will remain -inf until the top 40 array is filled with real data. For example if you make an array that is duplicate by appending the input array twice, all solutions will still give the same result.
The results differ slightly if the input has less than 40 elements, because some solutions will be padded to 40 elements with -1 values.
The results may also differ for bad data, e.g. if the input contains NaN.
