Darren's Weekly Nugget 10/09/2006

Darren's Weekly Nugget 10/09/2006

Post by Darre » Wed, 11 Oct 2006 01:40:07


The following tip has been on my list of possible nuggets for a while, but since it has <a href=" http://www.yqcomputer.com/ " target="_blank">recently been discussed on LAVA</a>, I figured I should go ahead and mention it before it becomes old news.  :)  It's basically a faster way to accomplish the following:
<img src=" http://www.yqcomputer.com/ ">
You see here that we have a data structure where objects are identified by their names.  We could probably make this code easier to read (and possibly faster) by maintaining a separate array of the names and simply searching that array with Search 1D Array:
<img src=" http://www.yqcomputer.com/ ">
Both of these methods are inherently linear searches.  It turns out that the following method of accessing the data is much faster:
<img src=" http://www.yqcomputer.com/ ">
I had never given much thought to Variant Attributes until this trick was shown to me.  You can basically store each data object as a different attribute of some dummy variant.  I say it's a "dummy" variant because its actual value and datatype are inconsequential...we're purely using the variant to gain access to its attributes as a data store.  I'm no computer scientist, but apparently the variant attributes are stored using a "<a href=" http://www.yqcomputer.com/ " target="_blank">red/black tree</a>" algorithm, which ends up being an order log(n) search...this is much faster than an order n search, which is what the While Loop or Search 1D Array approach would be.
So the next time you find yourself creating a string array lookup similar to one of the two traditional approaches above, try giving the Variant Attribute approach a try.  Note that this approach is recommended for LabVIEW 8.0 and later, due to some performance improvements with variants that did not exist in LabVIEW 7.1 and previous.
-D P.S. - Check out past nuggets <a href=" http://www.yqcomputer.com/ ;message.id=1669" target="_blank"> here</a>. Message Edited by Darren on 10-09-2006 11:14 AM


variant_attribute.jpg:
http://www.yqcomputer.com/


while_loop.jpg:
http://www.yqcomputer.com/


search_1d.jpg:
http://www.yqcomputer.com/
 
 
 

Darren's Weekly Nugget 10/09/2006

Post by Jeff » Wed, 11 Oct 2006 01:40:12

Interesting, but unless I missed something (entirely possible, mind you) a few details remain to be explained.  Does this assume that the Object Data cluster contains a string?  If so, does said string have to be at the "top-level" of the cluster?  If there are multiple strings in Object Data, does it use the first one in the cluster order, the highest-level one, etc?
I also don't quite understand, the first two find an item with a particular name in an array of clusters.  The variant approach looks like it is doesn't have any arrays in it, so what is it searching through?Message Edited by Jeff B on 10-09-2006 11:27 AM

 
 
 

Darren's Weekly Nugget 10/09/2006

Post by Darre » Wed, 11 Oct 2006 01:40:13

Object Data can contain whatever you want...it's just that whenever you add the object data to the variant attributes, you're associating a specific name (the attribute name) with that data for looking up later.  You can check out the LAVA discussion I linked above for more details if it's still unclear.
-D
 
 
 

Darren's Weekly Nugget 10/09/2006

Post by Ben » Wed, 11 Oct 2006 02:10:08

Is there anyone out there who would like to translate this nugget for the "variant diabled" (like me!) ?
Given the "Old way" what would I have to do to convert my code to the new way?
Ben
 
 
 

Darren's Weekly Nugget 10/09/2006

Post by Ben » Wed, 11 Oct 2006 03:40:07

Thank you Jarrod,
I will attempt to review your example within the next couple of days ( I'm still working a LV 7.1 project at work, my LV 8.20 machine is at home).
I am always looking for faster ways to serach through lists of stuff, so I am hoping for an epiphany (sp?).
Ben
 
 
 

Darren's Weekly Nugget 10/09/2006

Post by Jeff » Wed, 11 Oct 2006 03:40:09

Yes Jarrod, your example clears things up nicely.
To elaborate slightly, part of the story is in changing the way you're storing your data in the first place (the part through and including the for loop in your example).  The first two examples above show an array of clusters, each element containing the name of that item.
Variant attributes are effectively name/value pairs, where value can be any datatype.  What you're doing here is removing the (redundant) name from the data cluster and using it as the attribute name, then using each array element as the attribute value.
Once you've stored data in this way, that's when you can use the trick Darren mentioned for speedy lookup.Message Edited by Jeff B on 10-09-2006 01:29 PM
 
 
 

Darren's Weekly Nugget 10/09/2006

Post by Jarrod S » Wed, 11 Oct 2006 03:40:09

This is the jist of the code I attached, with constants instead of controls so you can see what's going on. Hope this helps!
<img src=" http://www.yqcomputer.com/ "> Message Edited by Jarrod S. on 10-09-2006 01:23 PM


screenshot1.JPG:
http://www.yqcomputer.com/
 
 
 

Darren's Weekly Nugget 10/09/2006

Post by Darre » Wed, 11 Oct 2006 04:10:08

Sorry I wasn't more clear in my original post.  Here is an example VI I wrote demonstrating the power of the Variant Attribute lookup table.  One of the most common use cases I have for a lookup table is when I have data associated with different items in a Tree Control.  Since the items are stored in the Tree Control as string values (tags), I often have a data structure (in the form of a cluster) associated with each item in the tree...I identify the tree items using their tags, and thus must look up the data for a particular tag by its name...my old approach was to either keep the tag as part of the data structure (the While Loop example above), or maintain a separate string array and use Search 1D Array to find the items in that array.  Instead of taking these approaches, we have the alternative of using Variant Attributes to make name-value pairs that are more quickly accessed than the standard linear search through a string array.  In the example VI, we are simply reading the selected tag in the tree control and accessing the data for that specific tag through the Get Variant Attribute function.  Hopefully this example VI clears up some of the confusion.
-D


Variant Attribute Example.vi:
http://www.yqcomputer.com/
 
 
 

Darren's Weekly Nugget 10/09/2006

Post by Ben » Wed, 11 Oct 2006 04:10:09

Thank you all very much!
Star to all.
 
Ben
 
 
 

Darren's Weekly Nugget 10/09/2006

Post by altenbac » Wed, 11 Oct 2006 04:10:10

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 (<a href=" http://www.yqcomputer.com/ ;message.id=184759#M184759" target="_blank">Deepest toe player</a>) , 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! :D
 
 
 
 

Darren's Weekly Nugget 10/09/2006

Post by altenbac » Wed, 11 Oct 2006 04:40:07


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's Weekly Nugget 10/09/2006

Post by Darre » Wed, 11 Oct 2006 04:40:09

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