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

41–50 of 108 posts

Re: The Universal Data Structure

#41

Post by jschwartzi »

pygy_ wrote: post #34
masklinn wrote: post #12

Earlier quoted context omitted.

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

They even mark the difference to the degree that foo[1] is stored in a special "array part" of the table, while foo["1"] ends up in the hash part. Predictably, the array part uses less memory.

Re: The Universal Data Structure

#42

Post by mdaniel »

dhimes wrote: post #27
seubert wrote: post #18

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

Aren't they just objects that have integer properties; that's why you can

    for (k in ['a', 'b']) {
      console.log(k);
    }
and get back 0, 1? However:

    var a = {0:'a', 1:'b'};
    for (k in a) {
      console.log(k);
    }
also outputs 0, 1.

Edit: turns out, you can even have doubles, too:

    var weird = {3.14:'hello', 6.28:'world'};
    // for loop above emits: 3.14, 6.28
    console.log(weird[3.14]); // emits 'hello'

Re: The Universal Data Structure

#43

Post by ignoramous »

Cushman wrote: post #8

This is a perfect example of the kind of humor that belongs on HN. Actually had me nodding along in parts, then screwing up my face at others. By the time I was sure it was satire, I was committed enough to see it through to the end. Best of all, I expect sincere discussion of the merits of the argument in this thread. Well executed, and heh heh .

Is this blog post a dig on Rich Hickey's talk 'Simple Made Easy'?

Re: The Universal Data Structure

#44

Post by bane »

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…

I don't know why the complexity estimates I find for Hashes are always so bad. They never account for growth (or depending on the implementation shrinking on delete), never account for the hash function, etc.

By the time you hash a key, you could have likely already inserted it into a trie.

Lookups on hashes are also not O(1) for similar reasons. You have to hash the search string, then compare the value at whatever location it hashed to (usually a string-comparison operation which aren't O(1)) and depending on the collision strategy, do more things if it doesn't match, but isn't an empty value.

Re: The Universal Data Structure

#46

Post by thaumasiotes »

pygy_ wrote: post #34
masklinn wrote: post #12

Earlier quoted context omitted.

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

> Lua tables accept arbitrary objects as keys, and make a difference between `foo[1]` and `foo["1"]`.

That sounds... completely normal? Python dictionaries will do that too. So will Java HashMaps.

Re: The Universal Data Structure

#47

Post by tomjakubowski »

mdaniel wrote: post #42
dhimes wrote: post #27

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

Aren't they just objects that have integer properties; that's why you can for (k in ['a', 'b']) { console.log(k); } and get back 0, 1? However: var a = {0:'a', 1:'b'}; for (k in a) { console.log(k); } also outputs 0, 1. Edit: turns out, you can even have doubles, too: var weird = {3.14:'hello', 6.28:'world'}; // for loop above emits: 3.14, 6.28 console.log(weird[3.14]); // emits 'hello'

JavaScript objects can only have string keys (this may have changed in ES2015 with Symbols). If you pass a non-string value in an object literal or inside a []-accessor, that value is converted to a string.

Re: The Universal Data Structure

#48

Post by sirclueless »

thaumasiotes wrote: post #46
pygy_ wrote: post #34

Earlier quoted context omitted.

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

> Lua tables accept arbitrary objects as keys, and make a difference between `foo[1]` and `foo["1"]`. That sounds... completely normal? Python dictionaries will do that too. So will Java HashMaps.

That comment was responding to a comment about PHP and JS, both of which do not make such a distinction.

Re: The Universal Data Structure

#49

Post by seabee »

thaumasiotes wrote: post #46
pygy_ wrote: post #34

Earlier quoted context omitted.

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

> Lua tables accept arbitrary objects as keys, and make a difference between `foo[1]` and `foo["1"]`. That sounds... completely normal? Python dictionaries will do that too. So will Java HashMaps.

There is another subtlety that values associated with integer keys are stored as an array. dicts and HashMaps don't do this.

Re: The Universal Data Structure

#50

Post by chriswarbo »

mdaniel wrote: post #42
dhimes wrote: post #27

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

Aren't they just objects that have integer properties; that's why you can for (k in ['a', 'b']) { console.log(k); } and get back 0, 1? However: var a = {0:'a', 1:'b'}; for (k in a) { console.log(k); } also outputs 0, 1. Edit: turns out, you can even have doubles, too: var weird = {3.14:'hello', 6.28:'world'}; // for loop above emits: 3.14, 6.28 console.log(weird[3.14]); // emits 'hello'

> Edit: turns out, you can even have doubles, too:

That's because Javascript doesn't actually have integers, it just has "Number":

> The Number type has exactly 18437736874454810627 (that is, 264−253+3) values, representing the double-precision 64-bit format IEEE 754 values as specified in the IEEE Standard for Binary Floating-Point Arithmetic

http://www.ecma-international.org/ecma-262/5.1/#sec-8.5

Post reply on HN