The Universal Data Structure • Hacker News Board

Re: The Universal Data Structure

#91

Post by chinpokomon » Wed, Jul 01, 2015, 12:51 PM UTC

rnovak wrote: post #79

chrisseaton wrote: post #67

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

To implement the hash table you wouldn't have to hash the whole string... of course this will depend on the data that you are trying to store. Assuming that the data is random, 100 bytes vs. 100 terabytes, you only need to figure out what bucket the data is saved. You could still base it on this concept if sightly modified

Re: The Universal Data Structure

#92

Post by Grue3 » Wed, Jul 01, 2015, 1:34 PM UTC

brudgers wrote: post #60

When in doubt, use brute force. -- Ken Thompson Using hashes as a first choice data structure is not necessarily a bad idea. 1] Until profiling a working implementation demonstrates otherwise, other data structures may be premature optimization. [1] Clearly an improvement over the Lisper's association lists.

It's not an improvement over small association lists. At least in Common Lisp hashes are pretty heavy and assoc lists will outperform them if there are less than ~100 elements.

Re: The Universal Data Structure

#93

Post by Cushman » Wed, Jul 01, 2015, 5:21 PM UTC

SilasX wrote: post #72

Cushman wrote: post #52

Earlier quoted context omitted.

This is mostly an issue with terms. Most (all?) of the operations we call constant-time, say, comparison, are technically logarithmic in the number of bits on real computers. Since that's usually not relevant to big-O analysis, we can sidestep the issue by specifying what we're counting: rather than say that mergesort is in O((log n) log (log n)) time, we say it takes O(n log n) comparisons. Whether you think of that…

But those situations aren't the same -- comparison sorts take O(n log n) because it is expressed in terms of n, the number of elements, which is orthogonal to element size. Even if you did account for the max element value V, it would be constant with respect to that value. The full bound would then be n log(V) log n -- regardless of your choice of V, you don't affect the scaling with respect to n. But for hashtables…

That example may have misfired-- perhaps consider that sorting an array of n elements requires addressing n elements, which requires arithmetic on words of log n bits, which are therefore log time operations. Limiting the size of each element won't help your complexity.

But we really don't care about that very much. In this case.

It's kind of described in that SO post I linked-- you can assume a constant-time hashing operation, but if that offends your conscience, assume an "integer RAM" model where arithmetic operations up to a certain word size w are constant time. Then you can observe that any reasonable w is inconsequential to your problem domain, and go back to treating hashing as a constant-time operation :)

The idea is that the fact that w increases at least as the log of n is shared by all computations modeled in integer RAM, so it's not a useful contribution to analysis at that scale. It's in the model, it's just not generally useful to the model. If you ever find yourself asking, is the bit width relevant? You can do some math and get a straight answer.

Of course real world algorithms often hash strings which complicates the analysis, but that's orthogonal, like my misstep earlier in implying the size of an element rather than the size of n. The mathematical sense in which hashing time must increase with the log of n is a fact of all algorithms that have ns.

I think your surprise at this just stems from wanting a rigorous definition for something that's more of a modeling tool, with different models to choose from. In real life, there's the time on the wall since you clicked "Run", and everything else is theorygramming.

Re: The Universal Data Structure

#94

Post by Cushman » Wed, Jul 01, 2015, 5:47 PM UTC

brudgers wrote: post #59

Cushman wrote: post #52

Earlier quoted context omitted.

This is mostly an issue with terms. Most (all?) of the operations we call constant-time, say, comparison, are technically logarithmic in the number of bits on real computers. Since that's usually not relevant to big-O analysis, we can sidestep the issue by specifying what we're counting: rather than say that mergesort is in O((log n) log (log n)) time, we say it takes O(n log n) comparisons. Whether you think of that…

Since we call cases where something that looks polynomial on the surface but actually performs in NP "pseudo-polynomial," does it makes sense to call the cases where something more or less takes constant time "pseudo-logarithmic?"

Or maybe, since O(1) is in O(log n), you can cover your bases by just calling everything logarithmic regardless :)

Re: The Universal Data Structure

#95

Post by Cushman » Wed, Jul 01, 2015, 6:02 PM UTC

bane wrote: post #80

chrisseaton wrote: post #67

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

Part of the problem when estimating hash complexity is that what's usually considered is something that's basically memory + offset. Basically a few mov's and an add. However, this is absolutely dominated by complexity of the hashing function, growth (which can be amortized, but is not O(1)) deletion (also not O(1)) and comparison functions (which are usually O(mn) or O(n) (or some similar depending)). We end up meas…

All of what you're saying is true, about the speed of real algorithms running on real hardware with real problem sizes.

But if you're talking about big-O, you are explicitly not talking about that. You're talking about how the speed of the algorithm hypothetically scales as some parameter tends to infinity.

To wit, O(n) doesn't mean "this algorithm takes kn time to run for a given n", it means "this algorithm's runtime for all n > c for is bounded above by nk for some c and k".

Sound like a analytic club that's rarely accurate to real-world performance? Yup, that's big-O :)

Re: The Universal Data Structure

#96

Post by rnovak » Wed, Jul 01, 2015, 7:54 PM UTC

chinpokomon wrote: post #91

rnovak wrote: post #79

Earlier quoted context omitted.

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…

To implement the hash table you wouldn't have to hash the whole string... of course this will depend on the data that you are trying to store. Assuming that the data is random, 100 bytes vs. 100 terabytes, you only need to figure out what bucket the data is saved. You could still base it on this concept if sightly modified

Yes. A valid hash function certainly can be defined as a F(n): N x N -> n % 100

But that certainly cannot be considered a reasonable hash function. A string is basically an array of bytes (or code-points, in case of UTF-8).

To have any decent property (like, producing different outputs for miniscule changes in the input), you have to touch every element in the array.

For custom objects, yes, you don't have to hash every property, but for strings, yeah, the hash function will almost always depend on the length of the string.

Re: The Universal Data Structure

#97

Post by SilasX » Wed, Jul 01, 2015, 8:14 PM UTC

Cushman wrote: post #93

SilasX wrote: post #72

Earlier quoted context omitted.

But those situations aren't the same -- comparison sorts take O(n log n) because it is expressed in terms of n, the number of elements, which is orthogonal to element size. Even if you did account for the max element value V, it would be constant with respect to that value. The full bound would then be n log(V) log n -- regardless of your choice of V, you don't affect the scaling with respect to n. But for hashtables…

That example may have misfired-- perhaps consider that sorting an array of n elements requires addressing n elements, which requires arithmetic on words of log n bits, which are therefore log time operations. Limiting the size of each element won't help your complexity. But we really don't care about that very much. In this case. It's kind of described in that SO post I linked-- you can assume a constant-time hashing…

You can't have it both ways: on the one hand, say that big-O is about arbitrarily large unrealizable values, but on the other hand make a bunch of exceptions for where things don't matter in practice, lest you be theory-gramming.

If you go the route that requires you to handle arbitrarily large tables, then computing a hash with a long enough value necessarily requires more steps, even if you assume all operations on length w integers are constant time -- because eventually your keys have to be larger than w, after which computing the hash increases in number of steps with the key size.

This is still different from the sorting problem. You can have a consistent computation model in which memory seek times are constant (even if unrealizable). That seems fundamentally different from a model where a hash computation is constant steps but also has arbitrarily long output.

The issue isn't whether the scaling of the hash computation matters in practice, but whether the big-O is properly O(1). And even if you did just care about "in practice" limitations, you're stuck with the problem of the hash computation taking longer than any realizable trie lookup would (as another poster mentioned is common), meaning that the O(1) claim misrepresents performance relative to another data structure.

Re: The Universal Data Structure

#98

Post by HanyouHottie » Wed, Jul 01, 2015, 8:22 PM UTC

michaelochurch wrote: post #63

While this is satire, it brings to mind some bit of industry history. My first reaction was, "you want to define a type class called Associative because you're talking about an interface , and that got me thinking about OOP vs. Haskell's type classes (a superior approach) (...and then I realized that the OP was a satire.) The major historical selling point of object-oriented programming (OOP) to the Forces of Evil--…

Why was this guy down voted? Everything he said is correct, if a bit hyperbolic at points.

This is relevant: http://www.smashcompany.com/technology/object-oriented-progr...

Re: The Universal Data Structure

#99

Post by rnovak » Wed, Jul 01, 2015, 8:29 PM UTC

chrisseaton wrote: post #84

rnovak wrote: post #79

Earlier quoted context omitted.

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

If you released software that was exponential, but your QA department only ever tested small inputs, I think it would be negligent to omit to your boss and|or clients the rate at which run-time could expand.

and I think it would be a horrible manager to not care about the difference between a day and a second.

Re: The Universal Data Structure

#100

Post by chrisseaton » Wed, Jul 01, 2015, 8:51 PM UTC

rnovak wrote: post #99

chrisseaton wrote: post #84

Earlier quoted context omitted.

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

If you released software that was exponential, but your QA department only ever tested small inputs, I think it would be negligent to omit to your boss and|or clients the rate at which run-time could expand. and I think it would be a horrible manager to not care about the difference between a day and a second.

Yeah I agree but my point is none of what you are talking about has anything to do with O(), which doesn't attempt or claim to do what you want to do.

It's like someone gave you a hammer and you're saying it's broken because it doesn't cut wood very well. It's not designed for that.