Hello World

January 8, 2013 Design PatternsLabVIEW  2 comments

Search and SortSo it looks like we will be keeping the first post as a Hello World. It seems a fitting start to a blog that will potentially be filled with programming tips and other tidbits.  In fact, I’ll be leaving a bit a LabVIEW code here that I find incredibly useful. The snippet that I’ll be describing is for what I call a Search and Sort algorithm.  This is design is used to search for desired values in an array and then remove them from the array.  In the example shown, a 1-D variant data type is used, however any data type can be used in place of the variant; boolean arrays tend to be used most.  It allows us to find the and extract desired data points in the fewest number of iterations.  The operation is split into three sections: Search, Prep, Sort.  Where in Search, we build an array of the indexes from values that we are looking for.  We then will Prep the data to be to be sorted.  Finally, we use a For loop to Sort the found data from the original array.

Step by step:

  1. Initialize the values for the loop shift register to zero and bring in the original array for Searching.  The shift register is used to hold the offset for the 1-D Array Search VI.
  2. The 1-D Array Search VI is the backbone of this pattern. What this VI does is starting at the index offset value, it searches through the array for the first found matching value and returns the index of the searched for value.
  3. The index of the found element is wired to the end of the loop and the tunnel is set to Auto-Index Enabled so as to build an array of found element indexes.  The index is incremented by 1 and passed into the shift register for the next iteration to be used for the index offset. The index offset must be  incremented in order to search for the next point. If you do not increment, then the search will keep finding the same index and the loop will never complete. The index is also compared to see if it is less than 0.  If there are no matching results, the returned index is -1 and when compared to less than 0, we get a true value that is wired to our conditional terminal thereby stopping the loop.
  4. In order to prep for the sort loop, I recommend deleting the last value from the newly build array of found indexes. It will always be -1 so there is no harm in keeping it during the sort loop if you want to leave this part out.
  5. This is the biggest and most important step in preparing for the sort loop.  We MUST reverse the array.  If we do no reverse the array, when we begin deleting values from the original array, the indexes will not match up to what we have found after the first delete. For example, if we found that indexes [1,3,5] where the indexes to delete, going in order would first delete index 1 from the array and make what was element[2] become element[1]. However, if we reverse the array and delete index 5 first, then the lower indexed values will remain unaffected until they are deleted.
  6. The sort loop.  Now that the prep work is all done, we can finally sort out the found data points.  The found elements array is auto-indexed though the For Loop.  This dynamically determines the number of iterations as well as steps through each value one at a time. We also use a shift register to keep track of the original array so that at the end we will have the modified array exiting from the shift register.  In this version, we are using the Delete From Array VI.  This VI will delete the value from the array and output it as well.  We wire up the deleted element to the end of the For Loop with Auto-Indexing Enabled so that we now build a new array of the found values.  The shift register will also output the original array without found elements.

Now this may seem more complicated than need be, however we have now reduced the number of iterations to be 2n+1 (2n+2 if not using step 4) where n is the number of matching elements found.  How? Simple, in the Search Loop, for 5 matching elements (n=5), the loop will iterate 5 times for each matching element and 1 more time to confirm there are no more matching elements (returning the index -1).  We delete the last element since it is -1, reverse the array and begin deleting.  Since we Auto-Index the found elements array into the Sort For Loop, we will only iterate the For Loop the same number of times as there are elements found. In this case since we deleted the last element, we will loop 5 times.  Put it all together to get: n+1 iterations (Search Loop) + n iterations (Sort Loop) = 2n+1 iterations.  If you had an array with 100 elements and only 5 matched, we’ve only looped 11 times!




Search and Sort




2 comments to Hello World

  • Mike P  says:

    Fyi. Delete from array takes a relatively long amount of time to function.This routine would be more efficient using the Array Subset function instead.

  • R4i Gold  says:

    Nice…thanks for this.

Leave a reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>