LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Darren's Weekly Nugget 10/09/2006

Wow, that's obscure!!! 😉
 
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! 😄
 
0 Kudos
Message 11 of 25
(6,694 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... 😉
0 Kudos
Message 12 of 25
(6,680 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

0 Kudos
Message 13 of 25
(6,675 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 😉

Joe Z.

Edit: search, not sort!

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

Message 14 of 25
(6,670 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.

 

0 Kudos
Message 15 of 25
(4,738 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
(4,261 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
(3,440 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
(3,430 Views)

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

 

Best regards,

Martin 

0 Kudos
Message 19 of 25
(3,416 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
(3,405 Views)