Re: foreach array - delete current row ?

Replies are listed 'Best First'.
Re^2: foreach array - delete current row ? by roboticus (Chancellor) on Jun 03, 2013 at 10:50 UTC
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/; } ],` [download] 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; ],` [download] $ 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% + -- [download] ... 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.	[reply] [d/l] [select]
Re^3: foreach array - delete current row ? (flaws) by BrowserUk (Patriarch) on Jun 03, 2013 at 13:44 UTC
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% + -- [download] 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 : #! perl -slw use strict; use Benchmark qw[ cmpthese ]; our $N //= 1e3; our $I //= -1; our @as; @{ $as[ $_ ] } = 1 .. $N for 0 .. 4; cmpthese $I, { for_splice => q[ my $ar = $as[0]; $ar->[$_] =~ /9/ and splice @$ar, $_, 1 for reverse 0 .. $#$ar +; $I == 1 and print "0: ", "@$ar"; ], grep => q[ my $ar = $as[1]; @$ar = grep !/9/, @$ar; $I == 1 and print "1: ", "@$ar"; ], offset_copy => q[ my $ar = $as[2]; my $o = 0; for( 0 .. $#$ar ) { $ar->[$_-$o] = $ar->[$_]; $ar->[ $_ ] =~ /9/ and ++$o; } $#$ar = $#$ar - $o; $I == 1 and print "2: ", "@$ar"; ], build_new_array=>q[ my $ar = $as[3]; my @b; for( @$ar ) { push @b, $_ unless /9/; } $I == 1 and print "3: ", "@b"; ], edit_in_place=>q[ my $ar = $as[4]; my $o = 0; for( @$ar ) { $ar->[$o++] = $_ unless /9/; } $#$ar = $o - 1; $I == 1 and print "4: ", "@$ar"; ], }; [download] I get yet another set of numbers: C:\test>1036622 -N=1e3 Rate grep build_new_array offset_copy edit_in_place +for_splice grep 1464/s -- -20% -43% -61% + -65% build_new_array 1820/s 24% -- -29% -52% + -56% offset_copy 2578/s 76% 42% -- -32% + -38% edit_in_place 3803/s 160% 109% 48% -- + -8% for_splice 4144/s 183% 128% 61% 9% + -- C:\test>1036622 -N=1e4 (warning: too few iterations for a reliable count) Rate grep build_new_array offset_copy edit_in_place +for_splice grep 159/s -- -25% -44% -62% + -66% build_new_array 212/s 33% -- -26% -49% + -54% offset_copy 287/s 80% 36% -- -31% + -38% edit_in_place 419/s 163% 98% 46% -- + -10% for_splice 464/s 191% 119% 62% 11% + -- C:\test>1036622 -N=1e5 Rate grep build_new_array offset_copy for_splice edi +t_in_place grep 15.4/s -- -22% -50% -69% + -70% build_new_array 19.8/s 28% -- -36% -60% + -62% offset_copy 31.0/s 102% 57% -- -37% + -40% for_splice 49.6/s 222% 151% 60% -- + -4% edit_in_place 51.6/s 235% 161% 66% 4% + -- C:\test>1036622 -N=1e6 Rate grep build_new_array offset_copy edit_in_place +for_splice grep 1.60/s -- -23% -51% -70% + -71% build_new_array 2.06/s 29% -- -37% -61% + -62% offset_copy 3.28/s 105% 59% -- -38% + -40% edit_in_place 5.26/s 229% 155% 60% -- + -4% for_splice 5.49/s 243% 166% 67% 4% + -- [download] Which just goes to prove a) be careful what you benchmark; b) O(n²) 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.	[reply] [d/l] [select]
Re^4: foreach array - delete current row ? (flaws) by roboticus (Chancellor) on Jun 03, 2013 at 18:05 UTC
BrowserUk: Yarch! I hate it when I mess up a benchmark. Thanks for the catch! ...roboticus When your only tool is a hammer, all problems look like your thumb.	[reply]
Re^4: foreach array - delete current row ? (flaws) by Anonymous Monk on Apr 27, 2015 at 01:55 UTC
A bit late to the game, but... I think your benchmark is still flawed because you're applying a destructive operation multiple times without re-initializing the test data in between. On the first iteration of each test case, the corresponding array contains multiple matches. After the first iteration, the matches are removed, so you're simply testing which method can remove zero matching elements the fastest. It makes sense that the splice approach will do this quickly, since splice is never actually called; while the grep approach, which needs to copy every element of the array, is not so fast.	[reply]
Re^5: foreach array - delete current row ? (flaws) by BrowserUk (Patriarch) on Apr 27, 2015 at 08:24 UTC

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/;
        }
    ],
[download]

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;
    ],
[download]

$ 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%    
+        --
[download]

... 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.

[reply]
[d/l]
[select]

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%    
+        --
[download]

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

:
#! perl -slw
use strict;
use Benchmark qw[ cmpthese ];

our $N //= 1e3;
our $I //= -1;

our @as;
@{ $as[ $_ ] } = 1 .. $N for 0 .. 4;

cmpthese $I, {
    for_splice => q[
        my $ar = $as[0];
        $ar->[$_] =~ /9/ and splice @$ar, $_, 1 for reverse 0 .. $#$ar
+;
        $I == 1 and print "0: ", "@$ar";
    ],
    grep => q[
        my $ar = $as[1];
        @$ar = grep !/9/, @$ar;
        $I == 1 and print "1: ", "@$ar";
    ],
    offset_copy => q[
        my $ar = $as[2];
        my $o = 0;
        for( 0 .. $#$ar ) {
            $ar->[$_-$o] = $ar->[$_];
            $ar->[ $_ ] =~ /9/ and ++$o;
        }
        $#$ar = $#$ar - $o;
        $I == 1 and print "2: ", "@$ar";
    ],
    build_new_array=>q[
        my $ar = $as[3];
        my @b;
        for( @$ar ) {
            push @b, $_ unless /9/;
        }
        $I == 1 and print "3: ", "@b";
    ],
    edit_in_place=>q[
        my $ar = $as[4];
        my $o = 0;
        for( @$ar ) {
            $ar->[$o++] = $_ unless /9/;
        }
        $#$ar = $o - 1;
        $I == 1 and print "4: ", "@$ar";
    ],
};
[download]

I get yet another set of numbers:

C:\test>1036622 -N=1e3
                  Rate grep build_new_array offset_copy edit_in_place 
+for_splice
grep            1464/s   --            -20%        -43%          -61% 
+      -65%
build_new_array 1820/s  24%              --        -29%          -52% 
+      -56%
offset_copy     2578/s  76%             42%          --          -32% 
+      -38%
edit_in_place   3803/s 160%            109%         48%            -- 
+       -8%
for_splice      4144/s 183%            128%         61%            9% 
+        --

C:\test>1036622 -N=1e4
            (warning: too few iterations for a reliable count)

                 Rate  grep build_new_array offset_copy edit_in_place 
+for_splice
grep            159/s    --            -25%        -44%          -62% 
+      -66%
build_new_array 212/s   33%              --        -26%          -49% 
+      -54%
offset_copy     287/s   80%             36%          --          -31% 
+      -38%
edit_in_place   419/s  163%             98%         46%            -- 
+      -10%
for_splice      464/s  191%            119%         62%           11% 
+        --

C:\test>1036622 -N=1e5
                  Rate grep build_new_array offset_copy for_splice edi
+t_in_place
grep            15.4/s   --            -22%        -50%       -69%    
+      -70%
build_new_array 19.8/s  28%              --        -36%       -60%    
+      -62%
offset_copy     31.0/s 102%             57%          --       -37%    
+      -40%
for_splice      49.6/s 222%            151%         60%         --    
+       -4%
edit_in_place   51.6/s 235%            161%         66%         4%    
+        --

C:\test>1036622 -N=1e6
                  Rate grep build_new_array offset_copy edit_in_place 
+for_splice
grep            1.60/s   --            -23%        -51%          -70% 
+      -71%
build_new_array 2.06/s  29%              --        -37%          -61% 
+      -62%
offset_copy     3.28/s 105%             59%          --          -38% 
+      -40%
edit_in_place   5.26/s 229%            155%         60%            -- 
+       -4%
for_splice      5.49/s 243%            166%         67%            4% 
+        --
[download]

Which just goes to prove a) be careful what you benchmark; b) O(n²) 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.

[reply]
[d/l]
[select]

BrowserUk:

Yarch! I hate it when I mess up a benchmark. Thanks for the catch!

...roboticus

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

[reply]

A bit late to the game, but...

I think your benchmark is still flawed because you're applying a destructive operation multiple times without re-initializing the test data in between.

On the first iteration of each test case, the corresponding array contains multiple matches. After the first iteration, the matches are removed, so you're simply testing which method can remove zero matching elements the fastest. It makes sense that the splice approach will do this quickly, since splice is never actually called; while the grep approach, which needs to copy every element of the array, is not so fast.

[reply]