LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Searching inside sorted 1D array

Hello,

 

I have a sorted 1D array of type U32 (all values are unique) and I would like to search inside this array for plurality (thousands) of matches. Definitely I could use the standard VI "Search 1D array", but it will not take the advantage of the sorted data. For large sorted arrays the searching could be substantially faster if using successful approximation (set index to the middle of the array and see if the search value is greater, smaller or equal to the selected cell, if greater - set index to the middle of right half, if smaller - set index to the middle of left half, if equal - search completed... and so on).

 

My question is - in LabView is there existing, ready to uses VI for searching inside sorted 1D arrays? If there is no such advanced searching VI I'll appreciate any help/ideas for building such high effective and optimised "Search in 1D sorted array" VI. Thank you. 

 

0 Kudos
Message 1 of 11
(2,382 Views)

LabVIEW does not have a binary search (see also this idea).

(Threshold 1D array comes close, but is not designed for integers).

 

Can you explain what "plurality" means in this context? How static is the array? Maybe you can turn it into a SET (LabVIEW 2019+, "collection" palette)?

 

0 Kudos
Message 2 of 11
(2,369 Views)

@altenbach wrote:

Maybe you can turn it into a SET (LabVIEW 2019+, "collection" palette)?

 


Here's what I had in mind:

 

altenbach_0-1600540329523.png

It will tell you if the value exists or not.

 

Note that if you are also interested in the original index of the element, you could use a MAP with the U32 value as key and the original index as value (not shown).

Message 3 of 11
(2,352 Views)

@altenbach wrote:
Note that if you are interested in the original index of the element, you could use a MAP with the U32 value as key and the original index as value (not shown).

Here's how that could look like:

altenbach_0-1600540985700.png

Message 4 of 11
(2,345 Views)

Thank you Altenbach,

 

In short about the project:

1. There is large C file with registers and register's field definitions (15K+ records). I extract all definitions and keep the addresses of the registers (U32) and the name of the register (string) into array of clusters. The array of cluster is sorted (ascending order), addresses are not always sequential

2. From the tested device I need to read the real values of all registers through SWD interface (JLink) and display them in a tree form

3. From the sorted array of clusters (address, register name) I build a table with SWD read instructions. Read instruction table is optimized to speed the data polling - where possible SWD is reading area (multiple words) instead of single words. 

4. At the end I have to display the live data for all registers


The critical moment is the time - everything should be done as faster as possible.

 

Definitions (addresses and register names coming from C file) are static and technically don't change.

 

 

I'll check your idea of using sets, thanks.

 

BTW, there is one post about binary search:

https://forums.ni.com/t5/LabVIEW/Binary-search-1D-array-example-code-bug/td-p/204026

 

 

0 Kudos
Message 5 of 11
(2,343 Views)

Maps should work just fine. Very high performance and O(log2(N)) scaling like binary search.

0 Kudos
Message 6 of 11
(2,296 Views)

Does that file ever change?  If the entire lookup table is static, you could just turn it into a map constant where the register is the key and the string is the value.

 

Of course of the data is already sorted, it might be even faster to do a binary search. For a some simple code have a look at my NI week sets&Maps benchmark. One code alternative uses a home-made binary search (BinarySearchStringInsert.vi). Maybe you can adapt it to your problem.

 

I would probably have two 1D arrays. Do a binary search on the array of keys, then use the found index to index into the matching array of strings.

Message 7 of 11
(2,231 Views)

I'd be more worried about >15k items in a tree... That's gonna kill performance.

 

Even if you do all the ordering as pragmatic as you can, it's probably going to be neglectable compared the tree update. 

 


@peter111 wrote:

The critical moment is the time - everything should be done as faster as possible.


Faster then possible 😉? (couldn't resist, point is clear though.)

 

But seriously, make a quick test to see what is slowing things down.

 

There's not really a point in tweaking a 1.0 ms routine, while some other part (the tree 😁) burns .5 s...

0 Kudos
Message 8 of 11
(2,202 Views)

wiebe@CARYA wrote:

I'd be more worried about >15k items in a tree... That's gonna kill performance.

 

Even if you do all the ordering as pragmatic as you can, it's probably going to be neglectable compared the tree update.


15k is peanuts for a map or set. that's only 14 decisions for a lookup. If you look at my benchmark, a set operation is only a few microseconds and going 100x larger only adds maybe a microsecond or two. (old laptop). Note that each iteration here involves an insertion and rebalancing step except for the very last iteration.

 

I also understand (maybe mis-understand?) that the table is static and sorting is never needed at runtime.

0 Kudos
Message 9 of 11
(2,176 Views)

beside the speed of searching with existing methods, why not implementing a binary search? I never need this algorithm, but the implementation needs not much time. It needs less time than to reading this thread.

Anyone interested? I'm willing to share with something like the " Zero Clause BSD" licence.

0 Kudos
Message 10 of 11
(2,157 Views)