Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

Re: Loops loosing Performance

by spurperl (Priest)
on Jun 10, 2005 at 05:02 UTC ( #465420=note: print w/replies, xml ) Need Help??

in reply to Loops loosing Performance

What you have here is the classical "bit counting problem". By ANDing the two numbers all you need is find the amount of 1s in the result. The bit counting problem is a terrific example of the tradeoffs between space and time efficiency, and is one my my favorite interview questions.

You can find a lot of info about it online, for example here.

To make a long story short, the fastest technique is table lookup. Precompute the counts for all bytes (256 of them) in a table and do a simple lookup to find results later.

What you've been shown by kaif and others are the more arcane and enjoyable methods, but table lookup will be faster.

Replies are listed 'Best First'.
Re^2: Loops loosing Performance
by kaif (Friar) on Jun 10, 2005 at 07:16 UTC

    spurperl is right, table lookup is fastest. Using the notation op for original poster, lt for "lookup table", and the rest obvious, the overall benchmark looks something like this:

    Rate op4 op5 hv7 hv6 roy4 kaif lt op4 64233/s -- -33% -33% -52% -57% -72% -76% op5 96098/s 50% -- -0% -28% -36% -58% -64% hv7 96399/s 50% 0% -- -28% -35% -58% -64% hv6 134032/s 109% 39% 39% -- -10% -41% -50% roy4 149447/s 133% 56% 55% 12% -- -34% -45% kaif 227019/s 253% 136% 135% 69% 52% -- -16% lt 270514/s 321% 181% 181% 102% 81% 19% --

    Just be sure to initialize your table outside of your function, that is, initialize only once.

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://465420]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (1)
As of 2021-10-23 15:44 GMT
Find Nodes?
    Voting Booth?
    My first memorable Perl project was:

    Results (88 votes). Check out past polls.