Darren's Weekly Nugget 10/09/2006

[altenbach]

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! 😄

[altenbach]

---

@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... 😉

[Darren]

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

-D

[Underflow]

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

[Mads]

"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.

[jyang72211]

Darren,

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

Yik

[Martin_Kroner]

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 

[PhillipBrooks]

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/

[Martin_Kroner]

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

Best regards,

Martin 

[PhillipBrooks]

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.