I’m not so sure about your assertion that Mark Nelson isn’t a bad programmer. If you put me in C and didn’t let me use my usual hashtable library, I still would have instinctually gone for an array sorted by keys. Since the list is short, a binary search isn’t going to take much longer than a hashtable lookup, and it doesn’t require implementing a hashtable from scratch. I probably would have done that on my first shot, and certainly if I’d thought about the problem long enough to optimize and write a blog post about it.
Maybe you could claim that my instinct there comes from knowledge of scripting languages, but I was doing that kind of thing in C before I’d ever worked full-time in a scripting language. And isn’t knowledge of your trade part of what makes you a good programmer?
Eh, maybe he’s not so bad. His optimized solution works out to be the same as using a linear search through an unsorted list instead of a binary search through a sorted list, and it runs fast enough.
Anonymous - 2007-11-01 17:47:16
I’m not so sure about your assertion that Mark Nelson isn’t a bad programmer. If you put me in C and didn’t let me use my usual hashtable library, I still would have instinctually gone for an array sorted by keys. Since the list is short, a binary search isn’t going to take much longer than a hashtable lookup, and it doesn’t require implementing a hashtable from scratch. I probably would have done that on my first shot, and certainly if I’d thought about the problem long enough to optimize and write a blog post about it.
Maybe you could claim that my instinct there comes from knowledge of scripting languages, but I was doing that kind of thing in C before I’d ever worked full-time in a scripting language. And isn’t knowledge of your trade part of what makes you a good programmer?
Anonymous - Thu 01 Nov 2007 19:25:22
Eh, maybe he’s not so bad. His optimized solution works out to be the same as using a linear search through an unsorted list instead of a binary search through a sorted list, and it runs fast enough.