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

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

reddit.com

24 pointsniyazpk43 comments

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

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.

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

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.

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

Thanks! If you can't find it, don't worry, though. It's just that I recently implemented one myself and struggled a bit to make it elegant.

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.

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...

> {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.

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.

>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.

But what if you have multi-national staff, or at least expect to hire non-natives?

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.

See, there is a catch 22: If they had used English in the first place, they wouldn't run into these problems later on ;)

That's not a catch 22, it's just a problem.

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)

Does it really make it "much, much" harder to read? No proficient coder will be reading lines of code as English sentences, even if by some happy coincidence they happen to read that way. I don't think having a few keywords in a different language makes much difference. You might just as well say that the switch in languages makes the code easier to read, since it separates out keywords from variable names.

> Does it really make it "much, much" harder to read?

Yes. Maybe not harder, but more strenuous.

> No proficient coder will be reading lines of code as English sentences

In that case, I'm not a proficient coder. Neither was the inventors of the IF..THEN..ELSE and WHILE .. DO .. and DO .. WHILE .. statements. Or the guys who made the convention to use hasXX/isXX for boolean getters. Or LINQ.

> I don't think having a few keywords in a different language makes much difference.

I do, and I've coded and maintained a lot of code in both camps. And, we're not aiming for "much difference", we're aiming for "easier".

> You might just as well say that the switch in languages makes the code easier to read, since it separates out keywords from variable names.

Well, I don't think any proficient coder has any problem with that. We have syntax (and syntax highlighting) for that purpose.

>Yes. Maybe not harder, but more strenuous.

So, what you actually mean to say here is "no"? Sorry, but I just don't see that having non-English identifiers makes it any harder (or more strenuous) to read.

>In that case, I'm not a proficient coder.

You certainly are not proficient if you attempt to read lines of code as English sentences because they happen to contain a few English words.

>Well, I don't think any proficient coder has any problem with that.

Nor will any proficient coder have a problem with a few English keywords.

Because we live in the global world and you can never be sure where will your code end up. I have had to deal with comments and DB schema which were neither in English nor in a language I speak, there was little pleasure in that. Having at least schema and indetifiers in English would have made everything much much easier. All programming languages I work with are more or less English based, so having schemas, comments, etc. in English is just a good fit and makes code easier to get should it land on the lap of some guy in another country.

That may not remain the case for long:

http://www.chinesepython.org/cgi_bin/cgb.cgi/english/english...

>Because we live in the global world and you can never be sure where will your code end up

Well you can't be sure of anything, but sometimes you know for more-or-less certain that English speakers aren't going to read the code.

I think that greatly depends on the culture of the project and the language of those involved with it.

Personally I code up all my stuff with identifiers, function names and comments in English.

But I can't see why a German company writing code would be chastised for writing their code in German.

I'd rather have them use German and do it properly than in broken English. Now in Germany most if not all programmers will be fluent (to some degree) in English, but in plenty of other countries that is not the case.

Being able to program should not come with an automatic requirement to be fluent in English as well.

Obviously there are issues with character sets when writing comments, plenty of language implementations wouldn't know what to do if you threw utf-8 at them, but I think that any modern implementation should allow for identifier names and comments to be in any language. Why should the English speaking world get a free pass here, and everybody else be at a disadvantage ?

"Being able to program should not come with an automatic requirement to be fluent in English as well."

It doesn't, and I merely said that I think it's good practice to do so. (For various reasons, e.g. a multi-national team, possible maintenance and re-engineering scenarios where it might be helpful to use standardized abbreviations, etc.) I have personally worked on a reengineering project that used German identifiers because of a very specific ERP system--it was ultimately decided not to use English identifiers because the translations would be too cumbersome. (This was a small company, what I am trying to say is a company like SAP [big] code a DBMS [inherently English domain] using German comments makes no sense to me...)

I think you have a 'neutrality of viewpoint' issue.

SAP = BIG = not a reason to do stuff in english

DBMS = inherently English domain because people don't use their own language, that's self-referential

Using German comments makes perfect sense, SAP being a German company.

It works like this: a company starts out making a product for their local market, they get successful and branch out, and then a large amount of time later their code gets opened up to programmers not familiar with the native language.

Now, if the company were American, nobody would have a problem with dealing with identifiers and comments in what is for them a foreign language, say English.

But I really don't see why an American programmer would have a bigger problem dealing with identifiers and comments in German than vv.

Computer programming is not an exclusively English domain, and if to you code with identifiers and comments in a foreign language is hard to read then you have a bit of a hint how much effort the rest of the world has to make in order to make that step.

The fact that English got there 'first' is already enough of a head start, that shouldn't mean it becomes mandatory.

Something similar happens in the world of scientific publishing, where basically publishing in Spanish, Greek or Dutch is equal to not publishing at all.

An algorithm with Dutch, German or Swahili identifiers and comments is exactly equivalent to one in English.

Probably if you spent enough time you could figure out what the comments meant even if you didn't speak the language. Not that that would be very productive, and that's why most larger companies (and definitely multinationals) standardize on English.

You should be happy that's the case, but it is by no means a requirement or a sign of not being professional. If 90% of the team is German I'm all for them coding in German.

I am happy to assure you that I have no issue whatsoever, and I completely understand your argument--though I did not ever intend for it to get to quasi-religious dimensions. But for me this is a matter of taste and personal preference; nothing anyone can write will get me to abandon it (neither will anyone but myself be able to change any other of my preferences.)

It seems a little unreasonable to enter into a discussion if you're not open to changing your opinions based on what other people say. It's your prerogative, of course, but why bother discussing these things if your opinions are so fixed?

It certainly does not only seem to be unreasonable, but it actually is. Probably I did not even recognize a discussion here, because to me it was just a simple matter of preference and therefore did not want to get into a full-blown discussion in the first place. (HN already distracts too much time than I can regularly afford without discussions.)

PS: I would like to edit my previous comment on the "nobody can change except me"-thing but seem unable to do so. For clarification: I did mean it that takes initiative from me to change my preference and not to be denying written word by someone else as being able to change my mind (which would be obtuse and absurd since it would preclude learning anything from someone else).

HN has some subtlety, and not allowing you to edit your comments past a certain point is there for a purpose, in this case that purpose is served well, because the GP would look a little weird if you could edit the meaning of your comment.

Because you can't and you can 'catch' your mistake with a follow up comment there is absolutely no problem and the whole page makes sense.

>DBMS [inherently English domain]

What about DBs make it inherently English? If a German person needs to store data in a way that an Englishman might employ a DBMS, what construct does he turn to?

The domain of DBMS being English was meant for the implementation language of the DBMS, not any application of said DBMS. To the best of my knowledge, the first database management systems were created in English speaking countries and all research relating to them is English, too. Therefore the "vocabulary" is English and it seems natural for me to choose English as the implementation language for implementing a DBMS (or not so: I implement everything in English, because it enables others to read and understand it, so it is easier for me to share and for someone else to benefit from it [that's probably the main reason for any lingua franca])

PS: btw: I am not an English native, nor a resident of any English-speaking country.

All I am saying is Automotive engineering doesn't have a must speak German to work clause just because the first modern automobile was made in Germany. French mathematicians don't have to speak English to be taken seriously. Software development shouldn't have an English requirement. The only reason the vocabulary of CS is English is because speakers of other languages haven't taken ownership of their work and instead contribute it in English. To match your btw: I am an English native, and a resident of any English-speaking country. I find it kind of sad that people are trying to kill off their native tongue by not keeping it up to date.

> I think that any modern implementation should allow for identifier names and comments to be in any language. Why should the English speaking world get a free pass here, and everybody else be at a disadvantage ?

I disagree (I'm designing and implementing a language right now, as it happens). The most important quality of an identifier is that it identifies. Consider the identifier BHOCT. Does it consist of Latin letters or Cyrillic ones? You can't tell -- in many monospaced fonts, they look the same. In fact you could have 2 (or even 32) identifiers that look like BHOCT but which are all different.

Then there's the issue of recognising/recalling letters. If I see an identifier written in Latin letters, I can recognise the individual letters, keep thme in memory and write them down. If I see an identifier in a script I'm unfamiliar with, it just looks like a squiggle so I can't remember it. There are millions of people who know one of the Cyrillic, Chinese, Korean, Thai, Arabic, Devanagari, Tamil and Hebrew scripts, but how many people know all those scripts? Very few. So for identifiers, it's best to specify one script, the one that most people who use computers worldwide are familiar with, the Latin script.

The same argument applies to domain names, which are just identifiers anyway.

http://en.wikipedia.org/wiki/Internationalized_domain_name

Your point?

Domain names stopped being 'just the latin script' years ago.

Which still doesn't make it a good idea.

On the contrary, it is an excellent idea!

For instance many companies and individuals simply can't have their names expressed in the Latin alphabet.

Mine is one of them, but since the difference is minor I couldn't care less, but if you are from any one of a multitude of countries who have a script different from the western 26 character set then you're completely out of luck.

The internet is global, the DNS is a major component of it and it is absolutely a good idea that they try to be inclusive.

That this will lead to some adaptation issues is a nuisance, but since global networking is here to stay and we're currently in the infancy of that now is the time to make these changes.

> For instance many companies and individuals simply can't have their names expressed in the Latin alphabet.

If someone wants a UK passport, they have to express their name in the Latin alphabet. Given that there are British people with linguistic backgrounds from all over the world, including many different writing systems, and they all manage to do this, I disagree with your statement that it can't be done. It clearly can be done, and in fact is done on a regular basis.

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.

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

The best code is the oldest code:

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

Duff's device.

Reply on news.ycombinator.com