Re: fast bit twiddling

sub stest
{
    my $str = shift;
    my $last_index=1;
    my @sorted_indexes = sort { $a <=> $b } @_;
    die "bad index" if( $sorted_indexes[0] < 1 );
    
    my $offset;
    do {
    $last_index += ( 
        ( $offset = 
            ( (shift @sorted_indexes 
           || return true) 
          - $last_index
        ) || next 
        )
    );
    substr($str, 0, $offset, "");
    } while( $str=~/^01|^10/ );
    return false;
}
[download]

USE: stest( $bit_string, @indexes ) Should be ridiculously fast, because it takes every opportunity to jump out of the main loop as soon as the relevant data is available, and often before it is stored. There is no recursion, and extremely tiny memory footprint. The only potential bottleneck is that it requires the bit list to be sorted.

Comment on Re: fast bit twiddling Download Code

Replies are listed 'Best First'.
Re: Re: fast bit twiddling by BrowserUk (Patriarch) on May 03, 2004 at 13:55 UTC
A couple of problems. 'true' and 'false' are not keywords in perl, and using next in a do while loop is a no-no, resulting, in this case, in the subroutine returning with the error message: "Exiting subroutine via next at..." Examine what is said, not who speaks. "Efficiency is intelligent laziness." -David Dunham "Think for yourself!" - Abigail	[reply]
Re: Re: Re: fast bit twiddling by esialb (Initiate) on May 03, 2004 at 15:15 UTC
oof, yes, i seem to have lost some of my perl-fu. i've recently been drawn to the dark side, aka functional languages. But I shortened my program even more `sub stest { my $str = shift; foreach (@_) { substr($str,$_-1,2) =~ /^(10\|01)/ \|\| return; } return 1; } #USE: stest( $bit_string, @indexes )` [download]	[reply] [d/l]