Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Universal Data Structure

elbenshira.com

Post reply on HN
Print view View original

21–30 of 108 posts

Re: The Universal Data Structure

#21

Post by masklinn »

jfe wrote: post #13

"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…

> Linked lists don't suffer from this problem, but at the cost of 1-2 pointers per item.

And decreased memory locality (more cache misses) and increased number of allocations.

Re: The Universal Data Structure

#23

Post by jsprogrammer »

jerf wrote: post #7

Having read over the entire thing, I have only one issues with it: The Universal Hash structure is only universal if the language implementing it permits you to create cyclic structures, so you can manipulate the "pointers" or relevant language concept to create the cyclic structures. There are a handful of languages that don't permit that, such as Erlang, and some languages like Haskell that permit you to use "tying…

Do you really need to create "true" (i.e. language level?) cyclic structures? Shouldn't you be able to simulate cyclic structures at the cost of requiring more space (and probably time) to compute the simulation?

Re: The Universal Data Structure

#24

Post by pmalynin »

jfe wrote: post #13

"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…

O(n) in the size of the string not the hash map.

Also, if the key space is known before hand, it is possible to build a perfect minimal hash table with 1.3n total keys (n is the size of the keyspace)

Re: The Universal Data Structure

#27

Post by dhimes »

seubert wrote: post #18
jfe wrote: post #13

"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…

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?"

Re: The Universal Data Structure

#29

Post by jerf »

jsprogrammer wrote: post #23
jerf wrote: post #7

Having read over the entire thing, I have only one issues with it: The Universal Hash structure is only universal if the language implementing it permits you to create cyclic structures, so you can manipulate the "pointers" or relevant language concept to create the cyclic structures. There are a handful of languages that don't permit that, such as Erlang, and some languages like Haskell that permit you to use "tying…

Do you really need to create "true" (i.e. language level?) cyclic structures? Shouldn't you be able to simulate cyclic structures at the cost of requiring more space (and probably time) to compute the simulation?

That would get into the stuff at the bottom, when you simulate other data structures within your data structure. A non-cyclic data structure can simulate cyclicness with IDs on nodes and things that store links... it's generally how you do it in Haskell, in fact, since while saying "it can't" do true graphs is perhaps a smidge overstrong it is certainly not practical to try to modify knot-tied structures. (I've seen the question "How would I do a graph?" repeatedly on /r/haskell, and "use IDs in a map" is generally what comes back.) But you're putting a layer on top of your store.

(By the by... you know you can trust me, because... semantic. Semantic.)

Re: The Universal Data Structure

#30

Post by shkkmo »

This 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 inflexible. It’s a strictly geometric constraint. Now we all use divs and CSS, because we get a much-more flexible CSS engine to define our layout. Postgres and her SQL friends are all table based, just like the of 1999. Don’t be 1999."

Post reply on HN