LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Darren's Weekly Nugget 10/09/2006

Wow, that's obscure!!! Smiley Wink
 
Of course worrying about performance for things like that makes only sense for huge data structures. Here's something I recently pondered.
 
An interesting variation would be a "search array" function if we can assume that the array is sorted. In this case, we could sort the names and create a lookup table for the original location of each element. If we need many lookups in huge tables, sorting first is comparatively cheap. (As a product suggestion we could add a boolean input to "search array"  to indicate that the input array is sorted, default is FALSE). During my work on the tic-tac-toe challenge (Deepest toe player) , I needed a very fast way to determine if a value exists in a huge sorted lookup table to create the recursive scoring table of all possible positions. The table only contained decisive positions, so for most lookups we would get a "-1" and "search array" would have inspected every single element in vain.
 
An early implementation of the full recursive scoring table generation for 4x4 tic tac toe using "search array" took half an hour while a custom written "search array" (same functionality, but assumes that the table is sorted) did the full recursive table generation in about 10 seconds. Big difference! Smiley Very Happy
 

LabVIEW Champion Do more with less code and in less time
0 Kudos
Message 11 of 25
(5,107 Views)


@Darren wrote:
Hopefully this example VI clears up some of the confusion.
Make sure you're fair in benchmarking the full code. Currently the entire first loop is "folded" into a constant in 8.20. If the names are allowed to change at runtime, this would need to be recalculated. How expensive is that actually? Sorry, I rarely use variants... Smiley Wink

LabVIEW Champion Do more with less code and in less time
0 Kudos
Message 12 of 25
(5,093 Views)

That example wasn't intended to be benchmarked...I just wanted to demonstrate how you would populate, then later read, the variant attributes. 

-D

DNatt, LV R&D
0 Kudos
Message 13 of 25
(5,088 Views)
NI keeps a 1D array binary search implementation at:

http://zone.ni.com/devzone/cda/epd/p/id/220

Like the red-black tree, that implementation will search a sorted array in O(log n) time (that is, the worst case time for the search is proportional to the log of the number of elements n being searched).  But!  The array must be sorted.  Worst case for most generalized sorts is O(n), and the sort needs to be done every time an element is added (unless you did a binary search to see where to add it!).

Red-black trees are a very good generalized search structure.  You can usually only get better by creating custom implementations based on the shape and function of your data (B+ trees in databases, for instance).  Of course, this assumes that the LV implementation is of the usual high quality Smiley Wink

Joe Z.

Edit: search, not sort!

Message Edited by Underflow on 10-09-2006 03:00 PM

Message 14 of 25
(5,083 Views)

"Of course worrying about performance for things like that makes only sense for huge data structures. ".

 

On a PC yes...On a PAC no. On PACs you run into a performance issue pretty quick as the standard search is in the order of 20 times slower than on a PC....

 

With the variant attribute-trick the PAC can even outperform a PC running the standard search.

 

MTO
Check out ClampOn CAN Monitor on the LabVIEW Tools Network.
0 Kudos
Message 15 of 25
(3,151 Views)

Darren,

 

would you be able to post the code for the approaches?  I want to get a better handle on them.

 

Yik

------------------------------------------------------------------

Kudos and Accepted as Solution are welcome!
0 Kudos
Message 16 of 25
(2,682 Views)

Actually I was building a "generic" functional variable than hold arbitrary variables. I started using a simple array of strings but then I learned about this variant trick described here. However this performes much slower in my code than the 1D array of strings (I use the "substitute variable" convention to define variables). In my small test vi it turnes out that the array can be written 5 times faster than the variant using the set variant attribute vi.

For the array I am first searching the array for the name of the variable to then replace the value string. So I am wondering if this variant attributes only perform better at low number of attributes?

 

Best regards,

Martin 

0 Kudos
Message 17 of 25
(1,861 Views)

What version of LabVIEW are you using? There appears to have been a significant boost in Variant Attribute performance between LV 8.6 and 2009.

 

http://lavag.org/topic/12223-variant-attribute-performance/

 


Now is the right time to use %^<%Y-%m-%dT%H:%M:%S%3uZ>T
If you don't hate time zones, you're not a real programmer.

"You are what you don't automate"
Inplaceness is synonymous with insidiousness

0 Kudos
Message 18 of 25
(1,851 Views)

Thanks for the response! I am using version 10.0f (32 bit).

 

Best regards,

Martin 

0 Kudos
Message 19 of 25
(1,837 Views)

Something doesn't sound right, I would expect that the variants would perform better (for searches) as the array size grows.

 

If your previous array implementation has a small number of elements and the elements are sorted, that might explain the good performance.

 

Most discussions on the forums that involve the Variant Attribute technique suggest that the variants will always be faster for moderate to large arrays.


Now is the right time to use %^<%Y-%m-%dT%H:%M:%S%3uZ>T
If you don't hate time zones, you're not a real programmer.

"You are what you don't automate"
Inplaceness is synonymous with insidiousness

0 Kudos
Message 20 of 25
(1,826 Views)