newbio has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks, How to dynamically remove array elements? For example, I want to remov +e certain elements of @array whose indices are stored in @arrayindex. + However, when I try to execute the code below, it does not work beca +use in each loop the length of @array changes thus making the origina +l index values (stored in @arrayindex) inappropriate. foreach my $i (@arrayindex) { splice(@array, $i, 1); } Any suggestions on how this should be done. Thanks Monks.

Replies are listed 'Best First'.
Re: Remove array elements dynamically!
by Joost (Canon) on Aug 27, 2007 at 19:46 UTC
    If your indexes are sorted, you could keep a separate counter for the number of items removed and subtract it from $i when splicing.

    However, it's much easier and more efficient to create a new array instead of splicing the same array, since each splice needs to copy all the elements from $i to the end of the array rearrange/copy the pointers to the elements from element $i to the end of the array.

    my @newarray; foreach my $i (@arrayindex) { push @newarray,$array[$i]; }
    Depending on your algorithm, you could probably do that at the same time/instead of building the @arrayindex array.

    Another way would be to use grep (if you can determine which elements to keep based solely on their value):

    my @kept = grep { $_ < 4 and $_ > 10 } @array;
    or even
    @array = grep { $_ < 4 and $_ > 10 } @array;
      ... since each splice needs to copy all the elements from $i to the end of the array.

      Is that so? I always thought of splice being highly efficient, working "in-place", just "re-arranging elements", without need to copy anything. Can you ascertain your statement?

      --shmem

      _($_=" "x(1<<5)."?\n".q·/)Oo.  G°\        /
                                    /\_¯/(q    /
      ----------------------------  \__(m.====·.(_("always off the crowd"))."·
      ");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}
      Ummm... you do realize that, while a valid example, nothing can ever be less than 4 AND greater than 10?
      array = grep { $_ > 4 and $_ < 10 } @array;

                      - Ant
                      - Some of my best work - (1 2 3)

      Thank you Joost. I am interested in the array that is left after removing/splicing out +the indices (defined in @arrayindex) from @array. But, I have got an idea from your hint. Let's see. Thanks.
Re: Remove array elements dynamically! (reverse)
by lodin (Hermit) on Aug 27, 2007 at 20:37 UTC

    Just do it from the back.

    foreach my $i (reverse @arrayindex) { splice @array, $i, 1; }

    lodin

    Update: This assumes sorted indexes. See GrandFather's note if they're not sorted.

      assuming of course that the indexes are sorted in ascending order. Safer is:

      foreach my $i (sort {$b <=> $a} @arrayindex) { splice @array, $i, 1; }

      which sorts in descending order thus guaranteeing the indexes are sorted, and removing the need for the reverse.


      DWIM is Perl's answer to Gödel

        Assuming of course that there are no duplicate indexes. Super-safest is:

        foreach my $i (sort { $b <=> $a } unique(@arrayindex)) { splice @array, $i, 1; }

        ;-)

        lodin

Re: Remove array elements dynamically!
by throop (Chaplain) on Aug 28, 2007 at 01:39 UTC
    For small arrays, lots of approaches work. For large ones, how about
    * Putting the elements of @arrayindex in a hash for fast access. * Go thru @array, incrementing a counter. If the counter value is in indexHash, select the element. Otherwise, pass an empty list
    my %indexHash; my $ix =0; foreach (@arrayindex){ $indexHash{$_}=1}; my @cleansedArray = map { $indexHash($ix++) ? $_ : ()} @array
    throop
Re: Remove array elements dynamically!
by b4swine (Pilgrim) on Aug 28, 2007 at 01:47 UTC
    Dear newbio,

    While many answers have been given above, every one of them is a quadratic-time solution (Update: Oops! didn't see throop's solution, which is also linear time as pointed out by ikegami. I guess I was writing while throop was posting.). The first removal shifts the top elements of the array down by 1. The next shifts more (including shifting the same previous elements once again), ...). On the other hand these operations are fast enough, that clarity and elegance of code may be reasons enough to not worry about efficiency.

    While not as elegant as the previous entries, here is a linear time solution (I am assuming that @arrayindex is a reverse sorted & unique'd list. If not, use Grandfather's technique in Re^4: Remove array elements dynamically! (reverse)). At the end of the loop, the answer is stored in @newarray and @array is empty.

    my @newarray = (); foreach my $i (@arrayindex) { unshift @newarray, (splice @array, $i); pop @array; }
    Note that while we are not doing this inplace, there is no memory hit, because the @newarray grows, just as @array shrinks.

      While many answers have been given above, every one of them is a quadratic-time solution

      Great solution, but throop's hash solution is linear like yours.

Re: Remove array elements dynamically!
by suaveant (Parson) on Aug 27, 2007 at 20:22 UTC
    @array = (1..10); for(my $i=0; $i<@array; $i++) { if($array[$i]%2) { splice(@array,$i,1,()); $i-- #array is one shorter, now; } } print "@array\n";

                    - Ant
                    - Some of my best work - (1 2 3)

Re: Remove array elements dynamically!
by FunkyMonk (Bishop) on Aug 27, 2007 at 19:40 UTC
      Hello FunkyMonk, Thanks for your reply. I understand "delete" function simply removes t +he value and does not change the index. However, what I want is to re +move the value along with its index (like what splice function does). + Thus imho, I guess delete will not help here? Any other solution? Th +anks, delete @array[@arrayindex];
        It may be too inefficient if your arrays are large, but it does what you ask.
        my @array = 1 .. 10; my @arrayindex = ( 2, 6, 4, 5 ); splice @array, $_, 1 for sort { $b <=> $a } @arrayindex; print "@array\n"; # 1 2 4 8 9 10

        Thanks to Joost and newbio for pointing out that an aray slice doesn't delete elements not at the end of an array.

Re: Remove array elements dynamically!
by QM (Parson) on Aug 27, 2007 at 20:57 UTC
    At the expense of more memory, use a hash? The index is the key, value is the original value

    -QM
    --
    Quantum Mechanics: The dreams stuff is made of

Re: Remove array elements dynamically!
by snoopy (Curate) on Aug 28, 2007 at 23:58 UTC
    Another approach is to create a complementary index, then take the array slice.
    my @keep = (0..$#array); $keep[$_] = undef for (@arrayindex); @array = @array[grep {defined $_} @keep];