Removing a list of indices from an array

[labuda]

Hi,

I have a large array (millions of entries) and a list of entries that i want deleted.

Making a for loop that removes one entry at a time is too time consuming.

Is there a subvi which will remove a list of entries from an array?

Basically, I want to remove (for example) entries [0, 3, 10, 12, 27, 1002, 1004, 20001, 100023] from array X, without using a for loop and shift register

Anyone have a clue?

Thanks

Aleks.

[Kenny_K]

If you check out the OpenG vis, they have a vi in the Array Pallete that is called "Delete Elements from Array" that takes an array of indices as an input.  That should do the trick for you quickly.

[Ray.R]

Are you allowed to create an array of the indexes (to the elements) that you want to delete?  You'd still need a loop, but it would only run for the number of elements to be deleted..

[Kenny_K]

if you wanted to do it more than once, yea you would need a loop, but here it is without one.

Message Edited by Kenny K on 08-29-2007 03:26 PM

[altenbach]

---

Basically, I want to remove (for example) entries [0, 3, 10, 12, 27, 1002, 1004, 20001, 100023] from array X, without using a for loop and shift register

---

This seems like a very silly restriction. How do you think the openG version does it. 😮

(If you don't want to use a loop, you would need 9 instances of your code fragment! Why????)

[labuda]

The problem comes out when you have 500 000 items to remove from the list. If you simply use the loop + shift register, then you end up clogging your computer; because your 1 000 000 size array goes back and forth.

I'm sure that Open VIs has an optimized algorithm to do this is a split second.

Where can i get this VI that kenny speaks of?

thanks

[Kenny_K]

http://forums.jkisoft.com/index.php?showtopic=233

[Ray.R]

How do you select which elements are to be removed?  is it automated? do you do this a number of times?

I like the solution from Kenny, but as Altenbach mentions, how does the OpenG solution do it?  😉 

...it probably sorts the array (of indexes) in decreasing order (to avoid loosing track of indexes), then deletes the elements indexed in the delete array by using a for loop.  but that's just a quick guess..  😉

[Kenny_K]

Joe makes a good point on how the indexes are determined.  If it is static, which I had assumed, then my solution will work pretty well.  If the indexes change each time, depending on how the indexes are determined, my solution will be wasteful and no faster than a shift register/loop setup.

[altenbach]

---

@labuda wrote:

The problem comes out when you have 500 000 items to remove from the list. If you simply use the loop + shift register, then you end up clogging your computer; because your 1 000 000 size array goes back and forth.

---

NO! A shift register pair is one memory location and if you do it right, all operation inside the loop are done "in place". NOTHING goes "back and forth"! EVER!

If you delete an array element, all higher elements need to be moved down by one slot, and it is very important to do this "in place". No matter what, each element needs to be touched by the code one way or another. In any case, you need to limit yourself to one array resize operation at the end, because they are very expensive and force a data copy. Constant resizing would really hurt your performance with such large arrays.

If you do it right, each element needs to be touched only once, no matter how many elements you delete.  Here's a quick way how you could do it.

To further optimize the code, especially for large arrays of indices to be removed, you should sort the array of indices, possibly remove duplicates, and index to the next comparison element in the FALSE case. There are probably many more optimizations possible.

If you have LabVIEW 8.5, you could also try the new "in place" structure.

The example was modified from one of my old VIs posted here for a similar taks (remove all element that are zero from an array):

http://forums.ni.com/ni/board/message?board.id=170&message.id=111936

You might want to read ithe entire thread for some ideas of performance considerations in such a case. Here are some beckmarks for the VIs in the quoted thread. As you can see, the differences can be orders of magnitude.

Message Edited by altenbach on 08-29-2007 02:25 PM