News for hackers. Stuff that matters.
Re:I've implemented a new HTTP/1.1 request and response pars... by jerf on Monday November 30, 2009 @11:00PM (#969200)
"I can make it arbitrarily fast if I don't actually have to make it work": http://blogs.msdn.com/larryosterman/archive/2009/09/29/i-can...
Re:I've implemented a new HTTP/1.1 request and response pars... by nostrademons on Monday November 30, 2009 @11:20PM (#969220)
I'm disappointed that the student who hardcoded the results was disqualified. You should get points for finding bugs in your professors' specification.
Re:I've implemented a new HTTP/1.1 request and response pars... by andreyf on Tuesday December 01, 2009 @12:17AM (#969276)
Not to mention the "winning" entry did exactly the same thing: found an `n' # of words which works for this input only, then created a fast algorithm that works for this input only, but is incorrect in general.
Re:I've implemented a new HTTP/1.1 request and response pars... by ricree on Tuesday December 01, 2009 @10:38AM (#969879)
Especially since the other solution that got docked for breaking the rules actually performed the calculation that was requested.
Re:I've implemented a new HTTP/1.1 request and response pars... by jimbokun on Tuesday December 01, 2009 @11:53AM (#970072)
I'm stunned that this was not for seen by the professor. Wasn't it obvious that the best way to do this was to give some sample documents for development, but keep the text that the program would be judged on a secret?
Re:I've implemented a new HTTP/1.1 request and response pars... by Frazzydee on Tuesday December 01, 2009 @07:25AM (#969609)
Well the specs say that the program must "calculate the 10 most common words". The disqualified program doesn't really calculate the 10 most common words– it simply outputs the answer.
Re:I've implemented a new HTTP/1.1 request and response pars... by eru on Tuesday December 01, 2009 @12:24PM (#970142)
It doesn't say they have to be calculated from the input.
Re:I've implemented a new HTTP/1.1 request and response pars... by benatkin on Tuesday December 01, 2009 @01:30AM (#969348)
Sounds like red/green/refactor would have come naturally to her.
Re:I've implemented a new HTTP/1.1 request and response pars... by Confusion on Tuesday December 01, 2009 @04:12PM (#970759)
The student missed the most important part of the spec: the intent. 99 Out of a 100 times, you aren't implementing a rigorous spec. The ability to understand what is requested is much more important than the ability to be a wise-ass.
Re:I've implemented a new HTTP/1.1 request and response pars... by viraptor on Tuesday December 01, 2009 @10:37PM (#971435)
> 99 Out of a 100 times, you aren't implementing a rigorous spec.

I'd argue that most programmers do, or are supposed to. Either because they are not the designers of the system they build and what they are expected to do is to "fill in the blanks and make it work", or because they implement something that operates with another system and should strictly adhere to the interface/protocol.

The ones who have anything to say about the design are usually the system designers (duh), small project contributors (because there is no spec) and UI people (because they're designers). So yes - if your spec is "1. make it work on this input; 2. make it fast", then making it work in O(1) for this and only this input is basically the best thing you can do (unless you can make it faster for every input in less time of course). Spending time on generalising it is based on second-guessing the intent.

I'd even go as far as saying that specs have absolutely no intent. You have an intent and describe it while writing the spec and you'd better formalise your intent precisely or you will end up with something you didn't request. If you want something on every input, you'd better write it down (when you give a task to someone else).

Re:I've implemented a new HTTP/1.1 request and response pars... by gruseom on Tuesday December 01, 2009 @12:03AM (#969263)
I've seen that line referenced a couple of times here recently. I'm pretty sure it derives from Jerry Weinberg's Psychology of Computer Programming, which contains a story about some programmers defending an incorrect program on the grounds that it would process more cards per minute, to which Weinberg replied, "But your code doesn't work. If mine doesn't have to work I can do a million cards a minute!"

One of my favorite software stories.

Re:I've implemented a new HTTP/1.1 request and response pars... by viraptor on Monday November 30, 2009 @11:26PM (#969228)
After reading that, I wonder if trie-s (i.e. judy arrays) would beat hash tables in this exercise... (and I also think that hardcoding the results wasn't cheating)
Re:I've implemented a new HTTP/1.1 request and response pars... by codexon on Tuesday December 01, 2009 @12:26AM (#969283)
Since when are judy arrays synonymous with tries?

Judy arrays were only invented and publicized in 2004 and the only public implementation is GPLed.

[deleted]
Re:I've implemented a new HTTP/1.1 request and response pars... by weaksauce on Tuesday December 01, 2009 @01:08AM (#969328)
For the record, and I am sure it's what you meant, a more specific description of Judy arrays is that they are a specific type of trie(though a trie is a specialization of a tree a trie is more rigorous.)
Re:I've implemented a new HTTP/1.1 request and response pars... by andreyf on Tuesday December 01, 2009 @01:13AM (#969333)
Judy Arrays are all Tries are all Trees, but only some Trees are Tries, and only some Tries are Judy Arrays.
Re:I've implemented a new HTTP/1.1 request and response pars... by pstuart on Tuesday December 01, 2009 @01:13AM (#969332)
This of i.e. as 'that is' and e.g. as "example given'.
Re:I've implemented a new HTTP/1.1 request and response pars... by ramchip on Tuesday December 01, 2009 @01:35AM (#969352)
the only public implementation is GPLed

Actually no. Here's a BSD one: http://hackage.haskell.org/package/judy

Re:I've implemented a new HTTP/1.1 request and response pars... by codexon on Tuesday December 01, 2009 @02:05AM (#969378)
Actually no. That's only a binding if you look at the source code.

The sole C source code is only about 2-3 lines long with a "#include <Judy.h>" which isn't even included while the haskell source is littered with foreign function calls.

I discussed this issue with Don on my website a couple of months ago: http://www.codexon.com/posts/why-arent-functional-languages-...

and believe me, he would have told me if he really did have a completely reimplemented Judy array.

Re:I've implemented a new HTTP/1.1 request and response pars... by andreyf on Tuesday December 01, 2009 @12:28AM (#969286)
With some pointer arithmetic, I would imagine so (with tries, not sure what judy arrays are)... although it might depend into how quickly memory can be allocated/accessed. Assuming the text is a set of lower-case alphabet character strings, you could define a 26-ary trie with very few instructions to do each characters' lookup...
Re:I've implemented a new HTTP/1.1 request and response pars... by nostrademons on Tuesday December 01, 2009 @12:46AM (#969310)
I would be willing to bet that that implementation is slower than a hash table.

(Yeah, I do have some data to back that up - I wrote & benchmarked an autocomplete implementation for a financial software firm. String tries were roughly 10x slower than binary searching an array for a 20k word corpus, which is probably around the size you're dealing with here. They have terrible cache locality - each character makes you follow a pointer, which is probably a cache miss, and the total size of the trie is on the order of 26 * 8 * 20k = 4M. They become a bit better if the number of distinct words in the corpus is small (so that everything fits into cache) or if the number of words is huge (so that your hashtable or array blows the cache anyway).

Re:I've implemented a new HTTP/1.1 request and response pars... by tyler on Tuesday December 01, 2009 @06:45AM (#969587)
I've had the opposite experience with Tries v. Hash tables. Though that could be a result of the Trie implementation. Dual array tries have really impressive lookup times, especially compared to the naive implementation... Insertion is pretty bad though. (Though that can be mitigated: http://www.gongcaichun.info/PPT/21.pdf)
Re:I've implemented a new HTTP/1.1 request and response pars... by nostrademons on Tuesday December 01, 2009 @11:15AM (#969975)
The structure of your data matters a lot. If one will fit in cache but the other won't, the one that fits in cache will almost always win. Then they have different big-O characteristics: binary searching an array is O(log N) where N is the number of items, a trie is O(k) where k is the length of the key, a hashtable is O(1), but this is misleading because the hash function is usually O(k) and performance can degrade to O(n) if you have lots of hash collisions.

I thought that an autocompletion widget for stock tickers would be the perfect application for tries: short, dense key space, lots of elements, and a fair likelihood of hash collisions. But apparently not, because our data size just happened to be one where cache effects dominate. I talked to one of the GMail guys later and he was quite surprised, from which I inferred (but it was not stated) that GMail probably uses tries to good effect.

Re:I've implemented a new HTTP/1.1 request and response pars... by tyler on Tuesday December 01, 2009 @05:37PM (#970972)
Right on. My point was simply that the type of Trie you use has an effect on the data's size in memory. A dual-array setup is pretty good at keeping the data small... There's very little pointer overhead and proximity is fairly good as well.