soundex algorithm in C++

I couldn’t actually find a C++ version of the soundex algorithm (all the ones I found were C code with a .cpp extension), so I threw one together.
Here it is if anyone is interested.

static char     lookup[] = {
'0',    /* A */
'1',    /* B */
'2',    /* C */
'3',    /* D */
'0',    /* E */
'1',    /* F */
'2',    /* G */
'0',    /* H */
'0',    /* I */
'2',    /* J */
'2',    /* K */
'4',    /* L */
'5',    /* M */
'5',    /* N */
'0',    /* O */
'1',    /* P */
'0',    /* Q */
'6',    /* R */
'2',    /* S */
'3',    /* T */
'0',    /* U */
'1',    /* V */
'0',    /* W */
'2',    /* X */
'0',    /* Y */
'2',    /* Z */
};

std::string computeSoundex(const std::string &input, const int resultLength){

//keep the first character intact
std::string result = input.substr(0,1);

//compute value for each character thereafter
for(int i=1;i<input.length(); i++){
   //skip non-alpha characters
   if(!isalpha(input[i])){
   continue;
}

//uppercase the input value
const char lookupInput = islower(input[i]) ? toupper(input[i]) : input[i];
//lookup it's value
const char *lookupVal = &lookup[lookupInput-'A'];

//make sure this isn't a dupe value
if(result.find(lookupVal, 0) != 0 ){
   result.append(lookupVal);
}
}

//make sure we could actually encode something
if(result.length() >= resultLength){
return result.substr(0,resultLength-1);
}

//In cases of empty strings (or strings with no encodable
characters, return Z000
return "Z000";
}

Redis

Redis

http://code.google.com/p/redis/

I just came across this really cool persistent alternative to memcached.  I haven’t spent too much time looking at the internals, but it accepts write operations and writes then asynchronously. This introduces the possibility of some data loss if you have pending writes, and the machine goes down or the like, but overall, the performance boost and persistence more than make up for it in most use cases.

I’ve played around with it on my macbook pro (very simple to build and get running), and it seems pretty cool.  It supports more features than memcached like, list and set operations (which are atomic), and push/pop operations.  This means that this could be a good candidate for distributed queueing and messaging systems.  Not to mention, it also supports master/slave replication!

Also, currently the ruby client supports consistent hashing (which I haven’t used yet), but that adds a lot to the scalability.  Given the speed (reported at 110,000 SETs/second, 81,000 GETs/second), I can see Redis coming into use in a lot of situations where you don’t need all the overhead and guarantees that a ‘real’ database gives you.

The only downside that I can see at the moment is that it has to read the entire dataset into memory.  That limits the size of your datasets, so estimate your data size before going this route.  Also, another glaring omission is a Java client.  There are some in the works (and I’ve thrown together a simple one), but nothing that is polished and ready to use.

Premature Optimization

“We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.”

-Knuth

This post can be summed up in the following sentance.  ‘Make sure you can justify each and every optimization of your code, before you make the change’.  Stated another way ‘If you haven’t profiled your code, then you don’t know what to optimize’.

Now for the justification…

In my career I’ve done everything from QA, to Development, to Developer Support at Borland.  In that time I’ve seen a lot of funky code.  By funky, I don’t mean strange indentation, or variable naming, but code that jumps through convoluted hoops in the name of ‘efficiency’.  I may be overly sensitive to this, as I saw a lot of this when I was working in support (people would contact us for help after they couldn’t fix the bugs in their own code, or sometime ours).

I will say that this type of problem seems to be much more prevalent with C/C++ programmers than Java programmers.  I think this stems from the fact that most Java programmers don’t really think about memory management and performance when coding, but in their defense, they don’t normally have to.  But I digress…

Most of the hackery that I’ve seen in regards to performance isn’t really effective.  Sure, optimizing that long running startup code brings up the program faster, but since that only happens once every N number of hours, it’s not making a big difference overall.  Programmers will see some area in their code where they can use a new and sexy data structure or technique to speed things up, and will do so, justifying it as optimizing.

In almost every case that I’ve seen, programs spend the vast majority of their time in a very small portion of their code.  Optimizing that portion of code, no matter how un-sexy, is where the big gains will come from.  Also, that portion of the code base should have the best set of unit tests, so you have that much more assurance that you haven’t inadvertently introduced a bug.

Also, a lot of times the bottleneck isn’t in your code directly, but in a library or downstream dependency.  If it takes 2 seconds for for your query to return results, then you need to make sure your tables have the correct indexes, add caching, etc.  *D0 Not* fork the hibernate code your using to try and eek out a little more performance.

So please, justify with an estimate of the performance gain of your proposed optimization before you start modifying the code. If you have no idea what the gain will be, then you probably don’t understand how/why the code is slow well enough to start making changes effectively.

Mat