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

Confusion about code sample in perlfaq4

by vr (Initiate)
on Feb 22, 2013 at 18:47 UTC ( #1020203=perlquestion: print w/ replies, xml ) Need Help??
vr has asked for the wisdom of the Perl Monks concerning the following question:

I'm confused about code sample from here:

How do I manipulate arrays of bits?

They say:

...given a vector in $vec , you can get those bits into your @ints array:

and give following code as "fast general algorithm"

use integer; my $bits = unpack "b*", $vec; push @ints, 0 if $bits =~ s/^(\d)// && $1; push @ints, pos $bits while($bits =~ /1/g);

What are they trying to do with two lines starting with push operators? Don't they want to get a list "e.g. ( 1, 0, 0, 1, 1, 0 ... )" as stated in the beginning of that section, i.e. do reverse conversion? They can't do it with this code, do they?

Comment on Confusion about code sample in perlfaq4
Download Code
Re: Confusion about code sample in perlfaq4
by thundergnat (Deacon) on Feb 22, 2013 at 19:36 UTC

    The wording does seem to imply that it would return a list of bit values, but that isn't what it is doing. Rather, that routine returns a list of bit positions that are set (have a 1 in them).

    If you just want the list of bits, it is probably simplest to split an unpacked string.

    my @bits = split //, unpack "b*", $vec;

    To furthur demonstrate:

    use integer; my $vec = 42; my @ints; my $bits = unpack "b*", $vec; my @bits = split //, unpack "b*", $vec; push @ints, 0 if $bits =~ s/^(\d)// && $1; push @ints, pos $bits while($bits =~ /1/g); print "\n"; print join ', ', @ints; print " <-- bit positions set\n"; print join ', ', @bits; print " <-- bits \n";
    2, 4, 5, 9, 12, 13 <-- bit positions set
    0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0 <-- bits 
    
Re: Confusion about code sample in perlfaq4
by BrowserUk (Pope) on Feb 22, 2013 at 19:50 UTC
    Don't they want to get a list "e.g. ( 1, 0, 0, 1, 1, 0 ... )" as stated in the beginning of that section,

    Why not just try it out?

    $vec = pack 'V', int( 2**32* rand() );; print $bits;; 011000001111110110010000101101 @ints = (); { use integer; push @ints, 0 if $bits =~ s/^(\d)// && $1; push @ints, pos $bits while $bits =~ /1/g; };; print @ints;; 1 2 8 9 10 11 12 13 15 16 19 24 26 27 29

    The are producing a list of the positions of the bits that are set.

    I do agree that the section title and description and the sub name are woefully bad.

    I'm also less than impressed with the claims for efficiency:

    C:\test>perl -MMath::Random::MT=rand -minteger -MBenchmark=cmpthese $vec = pack 'V*', map int( 2**32* rand() ), 1 ..10;; cmpthese -1, { a=>q[ my @ints; my $bits = unpack 'b*', $vec; use integer; push @ints +, 0 if $bits =~ s/^(\d)// && $1;push @ints, pos $bits while($bits =~ +/1/g); ], b=>q[ my @ints = grep{ vec( $vec, $_, 1 ) } 0 .. length( $vec ) -1; ] +, };; ^Z Rate a b a 22306/s -- -79% b 108646/s 387% --

    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.

      Thanks for great answers. Maybe, part of my confusion was because first "push" in faq code is unnecessary - why not replacing both lines

      push @ints, 0 if $bits =~ s/^(\d)// && $1; push @ints, pos $bits while $bits =~ /1/g;

      with

      push @ints, pos($bits)-1 while $bits =~ /1/g;

      And it's faster, if i'm not mistaken with how i checked it with Benchamrk module.

        why not replacing both lines

        If you look carefully at the first line, you'll see that in addition to pushing 0 if the first bit(byte!) is set, it also removes the first byte.

        Which means that the second line operates on the string with the first byte removed.

        That's because the value pos returns is the position after where the last match occurred, so by removing the first byte the positions come out correctly.

        Of course, they could have just subtracted 1 from pos, then: a) that first line; b) two visits to the regex engine; and c) modifying the string; become unnecessary.

        But then, if you use the tool perl provides for the job, you not only avoid the regex engine, but also the need to unpack the vector to a string of 1s & 0s:

        print grep vec( pack('V',1431655765), $_, 1), 0 .. 31;; 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 print grep vec( ~pack('V',1431655765), $_, 1), 0 .. 31;; 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31

        A very curious FAQ answer.


        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.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (11)
As of 2014-10-23 09:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (125 votes), past polls