Search 1D Array complexity

[SPM]

Hi, all,

Can someone please tell me the order-of-magnitude complexity of the "Search 1D Array" VI in the number of elements of the array?

I'd expect O(log n) but wanted to confirm that for a fact.

Thanks,
- Steve.



Message Edited by SPM on 06-23-2008 09:30 AM

[smercurio_fc]

I think the LabVIEW Help has the answer for you:

Search 1D Array

Searches for an element in a 1D array starting at start index. Because the search is linear, you need not sort the array before calling this function. LabVIEW stops searching as soon as the element is found.

Note that the search is linear.


Message Edited by smercurio_fc on 06-23-2008 09:35 AM

[SPM]

Oh-kay. Any way to get better than linear performance out of the existing VI library without incredible amounts of pain?

Thanks,
- Steve.

[unclebump]

Could you do something with a binary sort, but the array needs to be sorted?? Supposedly only takes seven searches.

[altenbach]

You cannot do better unless you have more information on the array. One way or another it needs to inspect every element until it finds a match.

Only for "special cases" dramatic improvements are posssible. For example if you know that the array is sorted, you can do a binary search, which is O(logN).

This would be easy to implements, I have done it in the past. I think there is also an example available here on NI.com.

(You also might want to make a product suggestion. It would be nice if "search array" had an boolean input named "array is sorted" that would switch to a binary search if TRUE.)

EDIT: found it: Binary Search 1D Array function for LabVIEW

Message Edited by altenbach on 06-23-2008 08:15 AM

[SPM]

I don't know where the "seven searches" comes from, but binary search on a sorted array is O(log n). I'm just used to the OO standard libraries and would prefer not to implement it myself if LV already does it for me somewhere. (Most OO language standard libraries have some sort of an O(log n) lookup via a height-balanced tree or hash table, with O(log n) complexity for insertion and deletion.)

Thanks,
- Steve.

EDIT: Thanks, Altenbach! Since I only have to sort the array once in its lifetime, this will do it. -S.



Message Edited by SPM on 06-23-2008 10:21 AM

[altenbach]

Of course if you sort the array first, you will lose the information on the original position of the found element.

If you are only interested if the array contains a certain element or not, this might be acceptable. 😉

[SPM]

I'm going to use it as an index structure (indexing from some sort of string or numeric identifier to an array of LVOOP objects, for use in a "handle" type scheme.) Can probably pull some sort of trick to reorder the indexed array to correspond to the indexes, or that might not even be necessary.

Because there are going to be a potentially large number of object instances floating around, the indexing has to be fast.

The objects can't be hardwired together because the entire structure needs to be configurable when the application starts.

NOW I'm in for it!

- Steve.

[PhillipBrooks · Accepted solution]

You might be able to take advantage of variants. Read more in this LAVA thread:

Faster Lookup Table, Stolen secrets of variant attributes

[SPM]

Cool -- I gotta read up on this variant stuff!

- Steve.