This article is pretty much spot-on. I'm taking a similar direction with the architecture of my startup. However, I'd like to point out one mistake. Your implementation of a linked list is suboptimal. A better implementation would be as a tree with a branching factor of one. That way, you don't expose object IDs that could then be cached by the user of the data structure. Hope this helps!
The Universal Data Structure
31–40 of 108 posts
Re: The Universal Data Structure
#32Earlier quoted context omitted.
I don't think the satire was particularly subtle!
Given the number of comments with "Please tell me this is a satire" in this thread, I would say it wasn't particularly explicit.
Then they obviously didn't read to the end:
"Unlike most academic work that has little to no practical implications, I think blindly following the stuff here will prove to be incalculably beneficial for you."
Re: The Universal Data Structure
#33I wish they had used the word "map" in place of "hash" throughout this entire article. The use of hashes is an implementation detail and wholly irrelevant.
> The use of hashes is an implementation detail and wholly irrelevant. Not in this case. An ordered map implemented as a tree has the same interface but with very different operation complexities
My comment was meant tongue in cheek. Maps are _the_ universal data structure: they can be used to map any input to any output. The rest is just an implementation detail.
One might even call them "functions", but that ruins the joke.
Re: The Universal Data Structure
#34Like a well trained Pavlov dog[1], reading the title brought "Lua table"[2] to my mind, the most flexible data structure I have worked with, by far. [1] https://en.wikipedia.org/wiki/Classical_conditioning [2] http://www.lua.org/pil/2.5.html
> reading the title brought "Lua table"[2] to my mind, the most flexible data structure I have worked with, by far. Which is not necessarily a good thing. PHP's array and JS's Object are essentially the same thing.
Lua tables accept arbitrary objects as keys, and make a difference between `foo[1]` and `foo["1"]`.
Plus all the metatables goodies: weak key and/or value references, prototype inheritance, ...
Re: The Universal Data Structure
#35Earlier quoted context omitted.
> The use of hashes is an implementation detail and wholly irrelevant. Not in this case. An ordered map implemented as a tree has the same interface but with very different operation complexities
My comment was meant tongue in cheek. Maps are _the_ universal data structure: they can be used to map any input to any output. The rest is just an implementation detail. One might even call them "functions", but that ruins the joke.
I missed an opportunity here.
Re: The Universal Data Structure
#36"Hashes are always O(1) reads, inserts and writes." Maybe, once you've found a location to read, insert, or write to. The author neglects the runtime cost required for the hash algorithm itself, which may not be trivial; computing the hash of a string key is typically an O(n) operation. Furthermore, unless a suitable table size is selected, integer keys (should one use a map like an array) will eventually hash to the…
>Maybe, once you've found a location to read, insert, or write to. The author neglects the runtime cost required for the hash algorithm itself, which may not be trivial; computing the hash of a string key is typically an O(n) operation.
Yeah, I know, it always came off to me as BS to repeat that hashes are O(1) lookup, like we're making a special exception. Anywhere else, you can look up the algorithm and derive its big-O without having to memorize, but not this one.
Pretty clearly, as the hash table grows linearly, the keyspace has to grow linearly and the key size logarithmically. Since you get the keys from the output of a (nice, well-mixed) hash function, then the computation for where to insert has to increase logarithmically -- a longer hash output requires more steps.
You only get O(1) by selectively ignoring one kind of asymptotic behavior (that of the computations needed for the hash).
Reddit discussion: http://www.reddit.com/r/compsci/comments/2z74z8/why_is_hasht...
Re: The Universal Data Structure
#37Earlier quoted context omitted.
It's even tagged "bad-theory." I think it's pretty clearly a joke! A really good one!
"And we can’t forget our favorite JavaScript interview question of all time: If you only had twenty-four hours to implement arrays in JavaScript, how would you do it?"
I'm not really versed on JavaScript. I presume this is a joke about the lack of a proper array structure in JavaScript? How would one answer this question anyway?
Re: The Universal Data Structure
#38This had me worried: "God-given axioms, which is academic lingo for a truth we accept purely by our God-given logic, like: if something is not true then it is false, something cannot exist in an empty set, something logical is logical." But then I saw this and started laughing: "Remember when everyone used tables to lay out their HTML? Well, that proved to be a horrible way to do things, because tables are inherently…
Why did the axioms bit have you worried? OP is pretty much exactly right, except for the part where we accept it by our "logic". Axioms are simply true, end of story; logic does not apply to axioms themselves, only how they can be used in relation to other axioms.
Re: The Universal Data Structure
#39Earlier quoted context omitted.
"And we can’t forget our favorite JavaScript interview question of all time: If you only had twenty-four hours to implement arrays in JavaScript, how would you do it?"
I'm not really versed on JavaScript. I presume this is a joke about the lack of a proper array structure in JavaScript? How would one answer this question anyway?
This is probably intended to be a joke about how Javascript was originally developed over about 10 days, which has been the root of many of JS's problems.
http://www.computer.org/csdl/mags/co/2012/02/mco2012020007.p...
Re: The Universal Data Structure
#40This... this is just very, very dedicated satire, right? Let's replace main memory with hash maps and then implement existing data structures on that . Yes. This is satire.
One commenter on the page said: "In retrospect this post is obviously satire."
I would agree - didn't realize it at first, but it does sound a bit too OTT on second thoughts...