6 ms·

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

24 points by niyazpk 17y ago

sb 17y 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...
- jacquesm 17y 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.
  - sb 17y 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.
    - foldr 17y ago
      >I would expect anybody in a project to code using English Why? This might make sense for open source code at the moment, but if it's code internal to (say) a German organization, commenting in the native language of the coders is likely to be easier and lead to less confusion.
      - sb 17y ago
        But what if you have multi-national staff, or at least expect to hire non-natives?
        jacquesm 17y ago
        In this case the answer would then be "Learn German". Most multi-nationals have coding standards that mandate the use of English though. But you'd be surprised how many companies that grew to be multi-nationals from regional companies have tons of code documented and written in the native language.
        sb 17y ago
        See, there is a catch 22: If they had used English in the first place, they wouldn't run into these problems later on ;)
        foldr 17y ago
        That's not a catch 22, it's just a problem.
      - mseebach 17y ago
        Because when you use English, you can write many statements that reads nicely - which you should aim for. if user.hasFoo() and company.isBar() then baz.play( jazz ) In German: if benutzer.hastFoo() and firma.istBar() then baz.spiel( jazz ) That's five language-switches in a single line. Much, much harder to read. (granted, only one if the language uses && and braces instead of and and then)
joe_bleau 17y ago
Duff's device.
jacquesm 17y 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.
- Tichy 17y ago
  Would be interested in seeing that implementation, remember the URL by any chance?
  - jacquesm 17y 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.
    - physcab 17y ago
      K-means is a fairly easy algorithm to implement. You just split your data depending on how many clusters you want, calculate the distance of every point to each cluster, assign, re-split, re-calculate, re-assign until some convergence criteria is met. There are a variety of implementations that speed this process up. One is canopy clustering which allows you specify which clusters the points will check with (ie checking with all the clusters takes a while, but canopies can limit the search). You can also try different distance metrics such as the triangle inequality. There should be lots of implementations online, specifically for Matlab which you can port over to another language if you wanted. It's one of the most widely used and most useful clustering algorithms and often provides initialization for lots of other algorithms such as Expectation Maximization (EM). This link comes to mind: http://cseweb.ucsd.edu/~elkan/fastkmeans.html http://cseweb.ucsd.edu/~elkan/fastkmeans.html
huntse 17y ago
The appendix to Chris Okasaki's "Purely functional Data structures" has to be right up there.
kurtosis 17y ago
If you download the FFTW http://www.fftw.org/ 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 17y 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 17y ago
The best code is the oldest code: http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ http://betterexplained.com/articles/understanding-quakes-fas...
antirez 17y 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.

24 points by niyazpk 17y ago

sb 17y 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...

jacquesm 17y 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.
- sb 17y 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.
  - foldr 17y ago
    >I would expect anybody in a project to code using English Why? This might make sense for open source code at the moment, but if it's code internal to (say) a German organization, commenting in the native language of the coders is likely to be easier and lead to less confusion.
    - sb 17y ago
      But what if you have multi-national staff, or at least expect to hire non-natives?
      - jacquesm 17y ago
        In this case the answer would then be "Learn German". Most multi-nationals have coding standards that mandate the use of English though. But you'd be surprised how many companies that grew to be multi-nationals from regional companies have tons of code documented and written in the native language.
        sb 17y ago
        See, there is a catch 22: If they had used English in the first place, they wouldn't run into these problems later on ;)
        foldr 17y ago
        That's not a catch 22, it's just a problem.
    - mseebach 17y ago
      Because when you use English, you can write many statements that reads nicely - which you should aim for. if user.hasFoo() and company.isBar() then baz.play( jazz ) In German: if benutzer.hastFoo() and firma.istBar() then baz.spiel( jazz ) That's five language-switches in a single line. Much, much harder to read. (granted, only one if the language uses && and braces instead of and and then)

joe_bleau 17y ago

Duff's device.

jacquesm 17y 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.

Tichy 17y ago
Would be interested in seeing that implementation, remember the URL by any chance?
- jacquesm 17y 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.
  - physcab 17y ago
    K-means is a fairly easy algorithm to implement. You just split your data depending on how many clusters you want, calculate the distance of every point to each cluster, assign, re-split, re-calculate, re-assign until some convergence criteria is met. There are a variety of implementations that speed this process up. One is canopy clustering which allows you specify which clusters the points will check with (ie checking with all the clusters takes a while, but canopies can limit the search). You can also try different distance metrics such as the triangle inequality. There should be lots of implementations online, specifically for Matlab which you can port over to another language if you wanted. It's one of the most widely used and most useful clustering algorithms and often provides initialization for lots of other algorithms such as Expectation Maximization (EM). This link comes to mind: http://cseweb.ucsd.edu/~elkan/fastkmeans.html http://cseweb.ucsd.edu/~elkan/fastkmeans.html

huntse 17y ago

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

kurtosis 17y ago

If you download the FFTW http://www.fftw.org/ 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 17y 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 17y ago

The best code is the oldest code: http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ http://betterexplained.com/articles/understanding-quakes-fas...

antirez 17y 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.