Comment by dpark | Hacker News Reader

Comment by dpark | Hacker News Reader

Parent Full thread

This feels very much to me like architecture astronaut behavior. This overwhelming drive to pull "elegance" out of everything mundane or tediously complicated.

Yes, you can sometimes rewrite your algorithm to eliminate "special cases", but if you do it at the cost of comprehensibility, it's not a net gain. In the case of these examples, we're not really even talking about "special cases", but edge cases, where you literally need to deal with an edge in the data. In the case of the neighbor sums, edge cases were masked by padding. In the case of the staircase, the edge is just obfuscated by the doubled labels and then hidden in a modulo operation. These are totally fine except that they seem to provide no value except "elegance", and they come at a high cost in terms of understandability. (The first step is literally "transform to a different problem", so now you need to understand the original problem as well as the new problem, and how they relate.)

I'm all for elegance when it comes bundled with understandability or legibility or performance or even simplicity. But often it actually means "clever" and it's an extremely subjective measure that delivers little to no value and is prone to causing problems later.

That first example in the article was interesting because it made me realise that I have a strong aversion to pushing the complexity into the data rather than into the code. Modifying the list seems to me that it could be a cause of other bugs (what if the list is re-used and something depends on it?).

Never mind bugs, imagine that array has 5 million elements. Good luck re-allocating and copying that to add an element at the start and another at the end.

I don't like the approach of pointlessly reallocating the array this way, but 5 million elements is not a problem on any machine built in the last 20 years. That's just 20 megs for 4-byte integers. With modern GC, this is cheap. It's not something you'd want to do in a tight loop (the copy time will start to matter), but for something like the example, the cost (in machine terms) is negligible.

I also experienced an instinctual aversion to padding the array that I can't really motivate (honestly) except to say "I don't like it."

The version with special cases feels cleaner to me.

Padding the array is a bit of a code smell. You can't just pad an array without allocating a new block of memory. After allocation you need to copy the array into the new space. This is a significant amount of overhead to a fairly straightforward and efficient algorithm.

Well, that's easy to fix - copy your array into a linked list so you an insert elements at the head efficiently. ;-)

Yes, the real problem with this implementation is the data structure they use. But is `next == null` a special case? ogod what do we do?!

This is interesting. Is it possible to implement a linked list while eliminating the end of the list ‘edge case’, in the fashion of the parent article?

Create a "sentinel" node which represents null and also points to itself, perhaps?

> we're not really even talking about "special cases", but edge cases

Indeed. This article has a bit of a smell. Sacrifice performance to the almighty gods of your opinions about elegant code? It doesn't make code less buggy. It verges on a holier-than-thou attitude, that case-y code is Bad(TM), with a sequence of increasingly-contrived examples.

And in fact, lots of algorithms are unavoidably case-y. Teaching programmers to sneer at bounds-checking, as this article does, is downright irresponsible. Sure; the right language might do that for you -- but whether it's a default value or a runtime error, a programmer's failure to fully explore the edge cases will result in incorrect behavior, crashes or both.

I do feel that elegant implementations are superior to others (all other things being equal). However, we need to be careful how we define “elegant”. For instance, while I fundamentally understand the drive to eliminate special cases, I don’t think that zero-padding the input (or concatenating the reversed input) is necessarily more elegant. It certainly incurs a nontrivial runtime overhead (unless done via lazy data structures, in which case we’ve just hidden the special cases).

Reply on news.ycombinator.com