That's one of the reasons I love awk (actually, gawk): this is the only data structure it has.
The Universal Data Structure
81–90 of 108 posts
Re: The Universal Data Structure
#82This... 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.
https://en.wikipedia.org/wiki/Content-addressable_memory
... is entirely different? I'm not sure what you're trying to say, since all you did was post a link.
Re: The Universal Data Structure
#83Good tongue-in-cheek. Technically, however, the hash was outdone by the Lisp CONS. CONSes could represent every conceivable data structure in 1959 and they were eaten raw by the CPUs of the time. But then, there were not so many people available for the following-blindly part.
Re: The Universal Data Structure
#84Earlier quoted context omitted.
When you say O(something), the something has a unit. Hash table lookups and insertions take time O(1), when talking about number of items already in the hash table - and that 'when talking about' is implicit and doesn't have to be said as anyone talking about the complexity of a hash table knows that, or would state otherwise as it would be an exception. Talking about the length of strings used as keys in the hash ta…
I have two kind of nits with this logic, but I could totally be wrong, and you should feel absolutely free to correct me. I'm fairly positive that a unit of measure should _ never _ be variable, otherwise it's fairly pointless. And if you don't think hashing a 1TB string takes significantly longer than a 100byte string ... Futher more, big O notation is supposed to be a wide upper bound, but I don't think that works…
I think the problem you would have with your boss would be that your boss asked you 'how long will this program run', and if you told them O(1), the question you are really answering is 'what is the time complexity of this algorithm, parameterised by the number of entries, as the number of entries tends towards infinity'.
If your boss really wanted O(), then they wouldn't care that hashing one key takes a day and another a second, because they're thinking in terms of a hash with infinite entries, so the difference between a day and a second to hash is irrelevant.
Re: The Universal Data Structure
#85Ehh, relational databases already proved that "sets" are the true universal data structures. Anything can be built upon them, including (hash)maps.
Well, and sets can be built by maps, so they are clearly of the same constructive strength in that regard.
Re: The Universal Data Structure
#86Earlier quoted context omitted.
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...
But this heritage produced, years later, a great presentation about the evolution of JavaScript... that was best viewed without JavaScript.
Re: The Universal Data Structure
#87Earlier 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?
While it's probably joke, JavaScript's Array is fine (although it's more like a 'vector'). JavaScript VMs implement it as a real array (in fact, plain objects are often optimized into arrays too).
Re: The Universal Data Structure
#88That's one of the reasons I love awk (actually, gawk): this is the only data structure it has.
It is* also true for PHP - almost any data structure internally is just a linked hash map.
*or was, I am not sure about current state
Re: The Universal Data Structure
#89"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…
> computing the hash of a string key is typically an O(n) operation.
The n in operation time on data structures usually refers to the number of members in the data structure. String length would be a different variable.
For example worst case for finding a string member in a linked list would be O(n * k) where n is the elements in the linked list and k is the string length. I.e. the worst case here assumes lots of members with shared prefixes.
So the O(1) in hash tables actually is O(1 * k).
This distinction often is important because the length of strings and the number of members are independent variables.
And for many use-cases (e.g. member names in classes or text-protocol keywords) k is essentially fixed, e.g. a maximum member name length of 255 characters or a similar limitation. And for big O notation that means O(1 * 1), since it's a constant.
Re: The Universal Data Structure
#90"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…
How about we refer to this as O(k) instead of O(1)?