Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

Re^5: Powerset short-circuit optimization

by creamygoodness (Curate)
on Nov 06, 2006 at 02:45 UTC ( #582361=note: print w/replies, xml ) Need Help??

in reply to Re^4: Powerset short-circuit optimization
in thread Powerset short-circuit optimization

Hi, L~R...

First the good news: the algorithm seems fine to me, and there's only one language-specific gotcha I found that could have caused you problems. That's very impressive for someone with next-to-no C experience.

Now the critique: This is hard code to review. The explanation helps, but there are a lot of things that get in the way.

  • Code without any comments at all is lame. Lame, lame, lame. Especially when its A) dense, and B) implements an unusual algorithm.
  • Those initializations wrap in every browser I checked. Do they wrap in yours? Looks like $h$_ amigo! Do you care?
  • While single line for/while/if blocks are a common Perl idiom, they are rare in C code.
  • If the variable has nothing to do with a "bit", don't call it bit. Yes, I know now that's an artifact of having translated Perl code that used a bit vector. But coming in fresh, I didn't, and it threw me off.
  • 4 out of 5 coders surveyed recommend naming variables with meaningful monikers rather than nebulosities like "val".
  • There are no blank lines to break up that big C function into chunks. It would be much easier to digest if it were in paragraphs -- ideally, commented paragraphs, as Damian recommends in Perl Best Practices.

With all those impediments, the only way this ordinary human was able to get through that and follow it from start to finish was to rewrite it myself. In so doing, I'm happy to report the only thing I found that was really off was this:

memset(seen, '0', sizeof(seen)); /* ... snip ... */ if (seen[bit] == '1') { return; } seen[bit] = '1';

In C, '0' != 0 and '1' != 1. Those single quotes return the integer value of the enclosed character, which, for '0' on an ascii machine is not 0 but 48. :) You got away with it because you were consistent, though. :) That memset() should look like this:

memset(seen, 0, sizeof(seen));
Marvin Humphrey
Rectangular Research ―

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (4)
As of 2020-10-26 02:20 GMT
Find Nodes?
    Voting Booth?
    My favourite web site is:

    Results (249 votes). Check out past polls.