in reply to Re: round-robin on varying sequence
in thread round-robin on varying sequence

Yes, that's faster. But it doesn't work (consider not removing elements when $index=0). When I fixed youre code, it became slower -- though it may be possible to optimize it again: 
# the fix:
@items = grep {
    my $keep = !exists $del{$_};
    $i++;
    $index -= ($i < $index) unless $keep;
    $keep
  } @items;

# the results
Benchmark: timing 100000 iterations of BrowserUk, dpuu...
 BrowserUk: 13 wallclock secs (13.72 usr +  0.00 sys = 13.72 CPU) @ 72
+88.63/s (n=100000)
      dpuu: 10 wallclock secs ( 9.88 usr +  0.00 sys =  9.88 CPU) @ 10
+117.36/s (n=100000)
             Rate BrowserUk      dpuu
dpuu      10117/s       39%        --
BrowserUk  7289/s        --      -28%

[download]
To provide fair comparison, here are the results I got running your original benchmark on my system (note the increased iteration count -- my system is 5X faster): 
Benchmark: timing 100000 iterations of BrowserUk, dpuu...
 BrowserUk: 10 wallclock secs ( 9.26 usr +  0.00 sys =  9.26 CPU) @ 10
+795.64/s (n=100000)
      dpuu: 10 wallclock secs ( 9.87 usr +  0.01 sys =  9.88 CPU) @ 10
+118.39/s (n=100000)
             Rate      dpuu BrowserUk
dpuu      10118/s        --       -6%
BrowserUk 10796/s        7%        --

[download]
in constrast to your +25/-20%. --Dave

Update: The required optimization is this twisted expression: 

@items = grep { ++$i && !exists $del{$_} || ($index -= $i-1 <= $index)
+ && 0 } @items;

[download]

Replies are listed 'Best First'.
Re: Re: Re: round-robin on varying sequence
by BrowserUk (Patriarch) on Sep 08, 2002 at 00:12 UTC

    Your right. My code, both my offered solution and my benchmark, are deficient. I'll keep my excuses and offer a revised solution, which I believe I have fully verified for compatability with the results of your original.

    The code below runs the remove_item(s) subs against the test data for all possible $index values and compares the results against each other (yours and mine). It also benchmarks each for all input criteria and the results are that my new version now averages a tad under a third (32.9%) faster across all situations.

    I hope you find this useful. 

    sub remove_items {
    my ($i, %del) = (0);
    @del{@_} = undef;
    @items = grep { !exists $del{$_} 
                      and ++$i 
                      or $index -= ($i <= $index), 0 
               } @items;
}

    [download]

    The code for the full verification and the benchmark result (on my poor li'l 233MHz :) are below

    Read more... (16 kB)
[reply]
[d/l]
[select]
      Yep, that seems to work now. But I had to stare at that expression for a while to understand why it is correct! It seems to be equivalent to: 
      grep { exists $del{$_} ? ($index -= $i <= $index) && 0 : ++$i } @items

      [download]
      Interestingly, the ?: version is as fast as yours; but the same logic written as if/else is much slower. Thx. --Dave

      Update: added my ?: simplification, then saw BrowserUk's reply.

[reply]
[d/l]

        If it's of any interest. I went back to first principles and came up with this which verified correct and was about 12% quicker than your original. 

        @items = grep { 
    if (!exists $del{$_}) { 
        $i++;
        1;
    } else {
        $index -= 1 if $i <= $index;
        0 ;
    }
} @items;

        [download]

        Then I realised that by pre-incrementing $i, it would never be zero so I could drop the 1;.

        That the -= 1 if ($i <=$index) was identical to -=($i <= $index);

        The 'then' part of the if could then be replaced with and and the else> with or.

        The result is the improvement of +20% performance.

        Whether the reduction in readability is worth it is a matter of choice and the application. If the list is big and the deletions frequent and it was running as part of a CGI for instance, it probably is. Other situations you have to judge on a case by case basis.

        Personally, I would rather see 3 lines of comment explaining one efficient, (correct:) line of code, than 3 lines of self documenting code, but that is very much a personal preference.

        Well It's better than the Abottoire, but Yorkshire!
[reply]
[d/l]
[select]

In Section Cool Uses for Perl