What's the best / most interesting piece of code you've ever seen?

http://www.reddit.com/r/programming/comments/a4j4a/whats_the_best_most_interesting_piece_of_code/

by niyazpk • 17 years ago

24 43 17 years ago

jacquesm11• 17 years ago

Without a doubt quicksort. It was shorter, more elegant and a lot faster than any other sorting algorithm I'd seen up to that point.

Runner up for me would be K-means clustering, one specific implementation of it.

Tichy2• 17 years ago

Would be interested in seeing that implementation, remember the URL by any chance?

jacquesm11• 17 years ago

The K-means clustering one ?

let me have a look, I think I downloaded the code.

edit: I can't find it in a couple of minutes, I was interested in it because one of the companies I'm involved in needed a way to classify items without any prior knowledge of the number of groups so I read up on that.

The most interesting feature of that particular implementation was how they chose their initial 'seeds', that is a big factor in how long it takes for the algorithm to converge on a solution.

I'll keep looking for it, I'm fairly sure I have at least a bunch of references to it in an email and a copy of some papers on my harddrive somewhere. Note to self: get organized better.

sb8• 17 years ago

hm, there were certainly many pieces of interesting code I have come across in the past (e.g., regular expression automata, details of compilers [simple but fast like in Niklaus Wirth's compiler construction book], details of interpreters [Lisp SECD, Prolog WAM], etc.). PageRank was certainly among the highlights--clearity, brevity: one could immediately see that it was orders of magnitude better than the simple brute force method. Peter Norvigs simple Python script for a statistics-based spell checker is definitely a highlight, too.

Hard as I try, I cannot for the love of god single out one piece among them. Interestingly, I can immediatly name the worst piece of source code I have ever seen: SAP DB. (I don't even know whether it's still available online, but it was ugly {formatting inconsistent, somplaces littered with German comments, etc.}--there are shurely better contenders for this place, but the fact that one of the biggest software companies produced it, let alone having clients using it sent shivers down my spine...)

EDIT: PageRank, how could I have forgotten...

jacquesm11• 17 years ago

> {formatting inconsistent, somplaces littered with German comments, etc.}

I can see why formatting would not make it pretty but that would not say much about the algorithm, and why would German comments be ugly ? Programmers in different countries routinely comment their code in their native language, it's only natural really.

sb8• 17 years ago

No specifics about an algorithm (it's a DBMS system, there would be plenty to look for ;) But the title does not include any algorithm-requirements for beautiful code.

ad Language: Of course its only natural, albeit unprofessional. I would expect anybody in a project to code using English, comments and identifiers--regardless of where the people actually come from. IMHO this is good coding practice, but probably you have different experiences.

joe_bleau• 17 years ago

Duff's device.

huntse• 17 years ago

The appendix to Chris Okasaki's "Purely functional Data structures" has to be right up there.

kurtosis• 17 years ago

If you download the FFTW http://www.fftw.org/. At its heart is a OCaml program called genfft that generates optimized C fft routines for different window lengths by computing a good recursive decomposition and minimizing the number of arithmetic operations. It represents the fft as a DAG and traverses it in a pure functional style maintaining the state of the optimizer using monads. I don't spend that much time looking at code these days, but this one blew me away when I spent a lot of time coding. It was so much more impressive to me than all of the elegant haskell implementations of different sorting algorithms because it solved a real problem and it was better than all of the competition

gjm11• 17 years ago

Most striking at the time: symbolic differentiation in some ancient dialect of Lisp. I thought this was an example in McCarthy's original paper, but it turns out not; I forget where I actually saw it; but anyway, starting from very primitive beginnings and making something that did Real Mathematics is pretty mind-blowing when you're 15 or whatever age I was.

TeX: by a large margin the best-documented substantial piece of code I've ever seen, and (by now) with an extremely low bug count. As for the actual code, there's plenty to love and plenty to hate.

Lots of things in Norvig's "Paradigms of artificial intelligence programming". Nothing in there is really astonishing, but the standard is consistently extremely high and of course it's accompanied by a wealth of insightful comment, namely the actual text of the book.

Various bits of low-level bit-twiddling. I love the population-count trick that begins with x & 0x55555555, but typically it's not actually the best way to do the job (four lookups in a 256-element table will usually be faster), so instead I'll pick the trick for finding whether a word has a zero-byte in it (useful, e.g., for operations like strlen), the idea of which is basically to subtract 0x01010101 and look for evidence of borrows across byte boundaries.

stuartjmoore• 17 years ago

The best code is the oldest code:

http://betterexplained.com/articles/understanding-quakes-fas...

antirez• 17 years ago

Recently I had to study skip lists. After years of thinking black-red trees were the way to go it was a very refreshing experience to write an implementation of skip lists. In general most code implementing randomized data structures like bloom filters, skip lists, hash tables, tend to impress me a lot.

Another impressive stuff are IMHO genetic programming, neural networks and language interpreters. Every programmer should play with this stuff.

What's the best / most interesting piece of code you've ever seen?

Related Stories