11–20 of 44 posts
At my company we rolled our own too. The hard part was tracking down all the brain-dead servers that seemingly worked fine with browsers, but were off spec.
Earlier quoted context omitted.
"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...
I'm disappointed that the student who hardcoded the results was disqualified. You should get points for finding bugs in your professors' specification.
Earlier quoted context omitted.
"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...
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)
Judy arrays were only invented and publicized in 2004 and the only public implementation is GPLed.
Earlier quoted context omitted.
"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...
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)
Earlier quoted context omitted.
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)
Since when are judy arrays synonymous with tries? Judy arrays were only invented and publicized in 2004 and the only public implementation is GPLed.
Earlier quoted context omitted.
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)
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...
(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).
Earlier quoted context omitted.
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]
Earlier quoted context omitted.
[deleted]
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.)