How can I get the indexes of the biggest 40 data from a 1D array?

[altenbach]

Thanks for doing some sanity checks, it is always important. 😄

Here are some findings:

• The first solution (1) fails if the array contains any NaN. Sorting such an array places NaN at the end, thus NaN gets counted as "largest" element. This might not be desirable.
• The fast (2) and the simple (3) solutions both ignore NaN values (a comparison with NaN is always false, and array min/max ignores NaN).
• If there are duplicate elements in the input, the solutions might have a different order, because the sort order of identical elements is ambiguous.
• If the input has less than 40 elements, the results differ as already mentioned above.
• If the input is such that there are several correct solutions, the results might differ, but they are all correct.

Of course further test should be done to ensure proper operation.

Solutions(2) can be further improved by placing the "reverse array" after the second FOR loop. Reversing might not even be needed if we don't care about the sort order of the result.

Message Edited by altenbach on 06-14-2009 10:45 AM

Message Edited by altenbach on 06-14-2009 10:51 AM

[altenbach]

---

altenbach wrote:

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.

I am sure there are even more optimized possibilities, anyone want to try? 😄

---

OK, I was bothered by the large penalty if the input array is sorted (and I was generally bothered by even having a sort step in there, because it is not really needed if we rearrange the code a little bit).

Here's a solution that eliminates the re-sorting and simply keeps track of the index of the currently smallest element. For a 10M array, it's only a few % faster than the earlier solution, but for a 1M array, it's already 20% faster. The benefits increase quickly for even smaller inputs. The big difference is however for sorted input arrays where the original solution had a huge penalty. For sorted inputs, the new solution is 20x faster than the old one!

So I would think this new solution is the best of both worlds and only slightly more complicated. Check it out. 😄

Message Edited by altenbach on 06-16-2009 08:37 AM

[foolooo]

Hi altenbach,

Thank you for your different versions of solutions! And I learned much from each of your replies. for this one I think you used two seperate arrays instead of a cluster, which is less handy but more efficient. I don't really need to sort the indices, and actually I prefer to keep the original order of them. But what's the node before 'sort 1D array'? I saw you used that to combine two array. Is it a new node in lv 8.6? I'm using 8.5.

Best wishes,

Bo

[altenbach]

---

foolooo wrote:

But what's the node before 'sort 1D array'?

---

It is "replace array subset" and all LabVIEW versions have it. Note that the shift registers contains a fixed size array of 40 elements and whenever we find an element that is bigger that the current smallest in the top 40, we replace the smallest element with it.

In the newest version, we keep track if the index of the smallest top 40 element, while in the sort solution, the smalles element is always the first and we don't need to wire the index. For efficiency, it is always best to operate "in place" on a fixed size array and "replace array subset" is the correct tool for that.

Each of my posts has the VI attach in LabVIEW 8.0, so you should be able to open any of them. You can right-click any icon and select help for more information of a function.

---

foolooo wrote:

I don't really need to sort the indices, and actually I prefer to keep the original order of them.

---

In this case you can simply sort the array of indices at the end. A trivial code change. 😉

[foolooo]

Hi altenbach,

Actually what I meant is 'build cluster array' node. I found that out from your code. Thank you for your help and your sharing. Cheers.

Best wishes,

Bo 

[altenbach]

---

foolooo wrote:

Actually what I meant is 'build cluster array' node. I found that out from your code.

---

It actually is index and bundle_cluster array. One of the more exotic cluster functions. 😉