Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

foreach array - delete current row ?

by JockoHelios (Scribe)
on Jun 02, 2013 at 21:07 UTC ( #1036622=perlquestion: print w/ replies, xml ) Need Help??
JockoHelios has asked for the wisdom of the Perl Monks concerning the following question:

UPDATE - Wow. Sorry for not responding to all who responded here. I'm sorely tempted to copy a thank-you to each, but that smacks of spam and insincerity so I'm not sure I want to do this. Up-Votes were done, though, so your contributions were not ignored.

My one defense is that you gave me so much to think about and work through that I put in a lot more time than usual to work the concepts into my code :) Successfully, too. I love it when that happens.

Original text

I'm running through an array via foreach, and as it runs through the array I'd like to be able to delete rows based on specific content. I've found reference material showing how to do this with a hash, but not with an array.

Changing over to a hash would add to the complexity. I need to keep the rows in the same order as they are read in from the file, and don't otherwise need hash features for this data.

Is it possible to just delete the current row from an array when looping through it without setting up a counter and splice operation ? That's the only way I can see of accomplishing this, and I suspect this problem could be solved in a more concise way.

I can clear the row with a regex substitution, but this leaves a blank row in place and the dreaded uninitialized value warning rears up...
Dyslexics Untie !!!

Comment on foreach array - delete current row ?
Re: foreach array - delete current row ?
by dave_the_m (Parson) on Jun 02, 2013 at 21:37 UTC
    Deleting elements from an array while iterating over it is explicitly documented as 'So don't do that' in perlfunc. Maybe grep is suitable for your use case:
    @array = grep { some-condition } @array;

    Dave.

Re: foreach array - delete current row ?
by vsespb (Hermit) on Jun 02, 2013 at 21:46 UTC
    delete the current row from an array when looping through it without setting up a counter and splice operation
    IHMO counter+splice is most feasible way. I use it when copying arrays with grep is too slow.
Re: foreach array - delete current row ?
by davido (Archbishop) on Jun 02, 2013 at 22:20 UTC

    Consider three options:

    • grep: Iterates through the haystack list and returns a new needles list comprised of elements from the haystack that meet the criteria you set forth. At the outset, this may seem expensive; it requires more memory than in-place editing, for example. But computationally it's a linear approach.
    • foreach and push onto a new array: This is a very similar approach to grep, but might feel more comfortable in cases where the criteria are not trivial. Again, you're walking through the haystack and creating a new list of found needles.
    • foreach and splice: Probably most memory efficient, but think of what's going on from a computational standpoint: Locate a delete line, delete it, then shift all remaining elements down one. Locate another delete line, delete it, then shift all remaining elements down one again, and so on. Worst case is deleting every line, starting with the first. In such a case, the computational complexity is a little better than quadratic. Each time you find a needle, you have to move every remaining piece of hay over one position.

    If you have the ability to throw memory at the problem, I would tend to favor the linear solution provided by grep or by foreach combined with push.


    Dave

Re: foreach array - delete current row ?
by Laurent_R (Vicar) on Jun 02, 2013 at 22:36 UTC

    Deleting elements from an array while iterating over it is explicitly documented as 'So don't do that' in perlfunc.

    Yes, this is really getting bad and messy. But for some reason, it seems that it sort of works fine with a hash. I had a program where I was progressively "improving" my hash by deleting useless elements, and everything went fine. Then I thought that it might be more efficient to use an array instead, and I figured out that it did not work at all. The array got completely messed up. In brief, it seems that you can delete records from a hash while processing it, but can"t do it in an array. OK, maybe I got it wrong and did not understand fully what was going on, but I got the feeling that you can modify a hash while processing it with the keys function, but not an array fith the foreach function.

    Does any monk here have an explanation for this apparently different behavor?

      As documented in each, it is safe to use the each iterator to iterate over a hash and delete the element most recently returned. It is also safe to generate a list of keys, and then delete hash elements by iterating over those keys -- you're not deleting elements from the list returned by keys, you're deleting elements from the hash that were listed by keys; a subtle but important difference.

      With an array, deleting elements requires rearranging the array, which (as the C++ folks like to say) invalidates the iterator, or as you mentioned, the array gets "completely messed up."


      Dave

Re: foreach array - delete current row ?
by BrowserUk (Pope) on Jun 02, 2013 at 23:41 UTC

    Three methods; which is best depends upon the size of the array, but grep is never a bad choice unless you're tight on memory:

    #! perl -slw use strict; use Benchmark qw[ cmpthese ]; our $N //= 1e3; cmpthese -1, { for_splice => q[ my @a = 1 .. $N; $a[$_] =~ /9/ and splice @a, $_, 1 for reverse 0 .. $#a; ], grep => q[ my @a = 1 .. $N; @a = grep !/9/, @a; ], offset_copy => q[ my @a = 1 .. $N; my $o = 0; for( 0 .. $#a ) { $a[$_-$o] = $a[$_]; $a[ $_ ] =~ /9/ and ++$o; } $#a = $#a - $o; ], }; __END__ C:\test>1036622 -N=1e2 Rate grep offset_copy for_splice grep 8144/s -- -14% -19% offset_copy 9489/s 17% -- -5% for_splice 10035/s 23% 6% -- C:\test>1036622 -N=1e3 Rate grep offset_copy for_splice grep 732/s -- -19% -44% offset_copy 898/s 23% -- -31% for_splice 1304/s 78% 45% -- C:\test>1036622 -N=1e4 Rate for_splice grep offset_copy for_splice 64.9/s -- -9% -33% grep 71.6/s 10% -- -27% offset_copy 97.5/s 50% 36% -- C:\test>1036622 -N=1e5 (warning: too few iterations for a reliable count) Rate for_splice grep offset_copy for_splice 1.56/s -- -78% -80% grep 7.00/s 348% -- -13% offset_copy 8.00/s 412% 14% -- C:\test>1036622 -N=1e6 (warning: too few iterations for a reliable count) (warning: too few iterations for a reliable count) (warning: too few iterations for a reliable count) s/iter for_splice grep offset_copy for_splice 71.8 -- -98% -98% grep 1.36 5183% -- -20% offset_copy 1.09 6467% 24% --

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

      Update 3: As BrowserUk notes below, my code is flawed. Since he already corrected it, I'll leave my incorrect code here. For future benchmarking, I think I'll have to try and remember to put in a test case to compare the results of all the routines to ensure that they match. I've done that sometimes in the past when I wasn't sure my code was correct. However it seems that I should *always* do it, since I was sure that *this* code was correct. <sigh>

      BrowserUk:

      Generally, I just build a new array because it's easiest. I didn't realize that it's reasonably fast, too.

      build_new_array=>q[ my @a = 1 .. $N; my @b; for (@a) { push @b, $_ if /9/; } ],

      I'm surprised at how much the for_splice version moves around in the rankings.

      While waiting for it to finish, I realized that your offset copy method would be faster if you saved the bookkeeping for the end, so I tweaked it a little:

      edit_in_place=>q[ my @a = 1 .. $N; my $o = 0; for (@a) { $a[$o++]=$_ if /9/; } $#a=$o-1; ],

      $ for J in 2 3 4 5 6; do perl 1036631.pl -N=1e$J; done Rate offset_copy grep for_splice build_new edi +t_in_place offset_copy 3288/s -- -10% -27% -37% + -38% grep 3657/s 11% -- -18% -30% + -31% for_splice 4483/s 36% 23% -- -14% + -16% build_new 5191/s 58% 42% 16% -- + -3% edit_in_place 5338/s 62% 46% 19% 3% + -- Rate offset_copy grep for_splice build_new edi +t_in_place offset_copy 319/s -- -14% -22% -37% + -40% grep 369/s 16% -- -10% -27% + -30% for_splice 411/s 29% 11% -- -19% + -22% build_new 505/s 58% 37% 23% -- + -5% edit_in_place 528/s 66% 43% 29% 5% + -- Rate for_splice offset_copy grep build_new edi +t_in_place for_splice 28.6/s -- -3% -8% -35% + -42% offset_copy 29.4/s 3% -- -5% -33% + -40% grep 31.1/s 9% 6% -- -29% + -37% build_new 43.8/s 53% 49% 41% -- + -11% edit_in_place 49.1/s 72% 67% 58% 12% + -- (warning: too few iterations for a reliable count) (warning: too few iterations for a reliable count) Rate for_splice offset_copy grep build_new edi +t_in_place for_splice 0.433/s -- -86% -87% -90% + -90% offset_copy 3.00/s 593% -- -11% -28% + -34% grep 3.36/s 676% 12% -- -19% + -26% build_new 4.17/s 862% 39% 24% -- + -8% edit_in_place 4.55/s 950% 52% 35% 9% + -- (warning: too few iterations for a reliable count) (warning: too few iterations for a reliable count) (warning: too few iterations for a reliable count) (warning: too few iterations for a reliable count) (warning: too few iterations for a reliable count) s/iter for_splice offset_copy grep build_new edi +t_in_place for_splice 632 -- -99% -100% -100% + -100% offset_copy 3.38 18587% -- -18% -28% + -36% grep 2.76 22785% 22% -- -12% + -22% build_new 2.43 25893% 39% 14% -- + -11% edit_in_place 2.16 29142% 56% 28% 13% + --

      ... will this *ever* finish? If it does before I go to work, I'll update the node with the result.

      Update: Added the edit in place chunk, and replaced the output to include those results as well.

      Update 2: The 1e6 case finally finished, so I added them. If anyone cares, this is on an Intel Atom 330 1.6GHz machine with 2GB RAM. Additionally, I slightly formatted the output (removing a few blank lines, and inserting some in other places) for readability.

      ...roboticus

      When your only tool is a hammer, all problems look like your thumb.

        There is a problem with your two routines that biases the benchmark in their favour.

        My routines remove any value containing a 9; yours only keep those containing a 9.

        Once you correct that (unless instead of if), you get a different set of numbers:

        C:\test>1036622 -N=1e3 Rate grep build_new_array offset_copy for_splice edi +t_in_place grep 678/s -- -22% -27% -34% + -41% build_new_array 870/s 28% -- -6% -15% + -24% offset_copy 929/s 37% 7% -- -9% + -19% for_splice 1024/s 51% 18% 10% -- + -11% edit_in_place 1150/s 70% 32% 24% 12% + -- C:\test>1036622 -N=1e4 Rate for_splice grep offset_copy build_new_array edi +t_in_place for_splice 71.5/s -- -9% -11% -22% + -39% grep 78.7/s 10% -- -2% -14% + -33% offset_copy 80.6/s 13% 2% -- -12% + -31% build_new_array 91.3/s 28% 16% 13% -- + -22% edit_in_place 117/s 64% 49% 46% 29% + -- C:\test>1036622 -N=1e5 Rate for_splice grep build_new_array offset_copy edi +t_in_place for_splice 1.29/s -- -75% -83% -84% + -85% grep 5.12/s 296% -- -33% -35% + -42% build_new_array 7.68/s 494% 50% -- -3% + -14% offset_copy 7.88/s 509% 54% 3% -- + -11% edit_in_place 8.89/s 587% 74% 16% 13% + -- C:\test>1036622 -N=1e6 s/iter for_splice grep build_new_array offset_copy edi +t_in_place for_splice 77.9 -- -98% -98% -99% + -99% grep 1.39 5503% -- -14% -18% + -38% build_new_array 1.20 6379% 16% -- -5% + -28% offset_copy 1.14 6737% 22% 6% -- + -24% edit_in_place 0.868 8884% 60% 39% 31% + --

        And actually, my original benchmark was also flawed -- or at least lazy -- in as much as it conflates the time taken to build the original array into the overall timings; which is unrealistic.

        Correcting for that

        I get yet another set of numbers:

        Which just goes to prove a) be careful what you benchmark; b) O(n2) in C can often be considerably faster than O(n) in Perl; if the former avoids the multiple opcodes of the latter.

        WHere the copy-offset (or your in-place) really come into their own is when the array being filtered is close to the limits of your memory to start with.


        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
Re: foreach array - delete current row ?
by sundialsvc4 (Monsignor) on Jun 03, 2013 at 02:11 UTC

    Instead of deleting the items that you want to discard from an array that you are iterating over ... which is a very dicey proposition in any programming language ... just create a new list and push the entries that you want to keep onto it.   (The grep function might do this in one fell swoop.)   Then, replace the original list with the new one.

    @list = grep( &keep_me, @list);

    In almost every case, the two lists consist of references to some bit of information ... and a reference, no matter what monstrosity it may refer to, is small and cheap.   You’re actually not moving the contents (big) around, just references-to (small) them.   As you build the new list, the reference-counts of all its contents briefly rises to “2,” then, when the new list replaces the old one (and the old one vanishes into the gloom of the garbage-collector ...) they all go down again.

      @list = grep( &keep_me, @list);

      I would add that the  keep_me() function of the example must operate on the  $_ default scalar, which is topicalized by grep.

      >perl -wMstrict -le "sub keep_me { return m{ [[:upper:]] }xms; } ;; my @list = qw(a b K d E f g h E P m e); @list = grep &keep_me, @list; print qq{@list}; " K E E P

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1036622]
Approved by Jim
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (10)
As of 2014-07-22 12:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (113 votes), past polls