LabVIEW
Removing a list of indices from an array
Now the question would be if we can improve things even more using the new In Place Element Structure of LabVIEW 8.5.
(See also http://forums.ni.com/ni/board/message?board.id=170&message.id=265705 for some discussion of this new feature)
Jason,
Could you mold your tecnique into something that is input compatible with the above VIs so I can do some benchmarks. Of course we need to include the time to make the boolean array.
For special cases we can even to the tagging in the original array if we know that a certain element cannot exist. (e.g. NaN, -Inf, +Inf for DBL, -1 if all values are known to be positive, etc.).
We simply do the tagging in place, then remove all tagged elements. This seems to be the fastest yet. As you can see from the buffer allocation display, everything is "in place"!
(To inline an image, attach it first, then edit the post and point to the image link of the attachment).
Message Edited by altenbach on 08-30-2007 11:15 AM
Christian:
I attached some VIs for you, including the indexer, the wrapper you requested, a solution optimized for huge arrays, and a different example which shows a more normal use case for array filtering. I think for the stated problem of huge arrays, a lot depends on the size of the deletion list. If is usually small, like < 1% of the total size, it may be better to iterate over the deletion list rather than iterating over the input array. I would love to see a benchmark, because I would think it is not necessary for LabVIEW to copy the array just to delete an element.
For more typical cases with the input array containing fewer than maybe 100000 elements, I would bet it is more intensive and certainly more programming work to generate the index list than to use the boolean array. So it's kind of unfair to benchmark this solution with the overhead of generating the boolean array unless you also benchmark the creation of the index list for other solutions. I believe the index list is only beneficial for the original poster's less common question of deleting a few items from an enormous array.
Here is a picture of how I normally use the filter:
I guess I am trying to say that once I started using the array indexer, I don't know how I ever got on without it (Good-bye build array in a case structure in a for loop!). I also have to give the credit to my amazing co-worker Rob Calhoun who took my original version and optimized the heck out of it.
Jason
I attached some VIs for you, including the indexer, the wrapper you requested, a solution optimized for huge arrays, and a different example which shows a more normal use case for array filtering. I think for the stated problem of huge arrays, a lot depends on the size of the deletion list. If is usually small, like < 1% of the total size, it may be better to iterate over the deletion list rather than iterating over the input array. I would love to see a benchmark, because I would think it is not necessary for LabVIEW to copy the array just to delete an element.
For more typical cases with the input array containing fewer than maybe 100000 elements, I would bet it is more intensive and certainly more programming work to generate the index list than to use the boolean array. So it's kind of unfair to benchmark this solution with the overhead of generating the boolean array unless you also benchmark the creation of the index list for other solutions. I believe the index list is only beneficial for the original poster's less common question of deleting a few items from an enormous array.
Here is a picture of how I normally use the filter:
I guess I am trying to say that once I started using the array indexer, I don't know how I ever got on without it (Good-bye build array in a case structure in a for loop!). I also have to give the credit to my amazing co-worker Rob Calhoun who took my original version and optimized the heck out of it.
Jason
Message Edited by jdunham on 08-30-2007 03:01 PM
Thanks Jason. Maybe I can study this tonight.
As far as I know, arrays must occupy contiguous memory locations. So if you have an array with one million points and delete element #2, elements #3 and above need all to be moved down by one slot. Even if you don't allocate a new array for the result, all higher elements must be moved for each deletion operation so if you delete 100000 elements using "delete from array" in a loop, the last element in the array needs to be moved down 100000 different times. That's a lot of work! In my original code, each element is only moved exactly once.
@jdunham wrote:
I would love to see a benchmark, because I would think it is not necessary for LabVIEW to copy the array just to delete an element.
Yes, but it's really, really fast. Just think of how fast LV can transpose a huge 2D array (it's fast).
@altenbach wrote:As far as I know, arrays must occupy contiguous memory locations. So if you have an array with one million points and delete element #2, elements #3 and above need all to be moved down by one slot.
I would agree that as you get to a large deletion list, my solution may lose its advantage. But your method still runs a bunch of LabVIEW nodes for each element of your huge array, that is guaranteed to be somewhat slow, since you are taxing the LabVIEW scheduler. My other solution (the one with the array of booleans) has the same problem, but for non-huge applications it is both fast and simple to code.Even if you don't allocate a new array for the result, all higher elements must be moved for each deletion operation so if you delete 100000 elements using "delete from array" in a loop, the last element in the array needs to be moved down 100000 different times. That's a lot of work! In my original code, each element is only moved exactly once.
I hope you get a chance to benchmark them and tell us where the break-even point is.
Oh, and there was a bug in my original solution regarding the removing of unique elements, so I attached a new version
Jason
Message Edited by jdunham on 08-30-2007 03:33 PM
Message Edited by jdunham on 08-30-2007 03:34 PM
Message Edited by jdunham on 08-30-2007 03:35 PM
Here's an example using the In-Place structure. Seems to work, although I must admit I'm not 100% why! Anyone want to profile it against Altenbach's other method?
I'll attach the pic for those of you without LV85.
I'll attach the pic for those of you without LV85.
Message Edited by Jarrod S. on 08-30-2007 05:19 PM
