Rendered at 19:26:03 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
ok123456 9 minutes ago [-]
Most algorithm analyses don't incorporate memory hierarchies. I'm not sure what the point of this post was.
If you are really concerned about it, compute the empirical roofline for your machine.
Also, if the point is to point out memory hierarchies, it's not 'quadratic performance.' The algorithm doesn't behave differently once it spills over. The costs just get bigger.
juancn 2 hours ago [-]
That's usually true of all common hash table implementations (when objects don't have a defined order, if they have you can get O(1) average and O(log N) worst case), regardless of language.
The O(1) is the expected average case, which usually holds.
Yeah, O(N^2) is theoretically possible, but unless you're defending against some sort of denial of service attack, in practice it rarely matters.
Still, if you can guess a sensible initial size for a hash table you can avoid a lot of the overhead of rehashing.
northisup 1 hours ago [-]
Raymond Hettinger has a great talk about how much python's dict has improved over the years. So this is super interesting and will probably just make the builtin dict better eventually.
The lesson of the talk is that if you are idiomatic then you will benefit as the language improves.
That is why I like to use __slots__ when defining a class. Unlike dicts, using __slots__ is a tuple so using it to store class attributes is much faster.
brudgers 22 hours ago [-]
But could we create a hash table that would be truly constant-time? No. As the size of your data structure grows, it requires progressively slower memory.
At a large enough size to be interesting, everything is dominated by IO and because IO is slow, at any interesting size performance is a matter of tailoring the implementation to the details of the data {0}.
Engineering is hard work, not naive math.
[0] Data might be arbitrary but it is never random. Not being random is what makes it data.
TristanDaCunha 2 hours ago [-]
Which statement in this article applies only to Python?
robrenaud 15 minutes ago [-]
The part where he chooses his inputs to hit worst case behavior in Python's hash function.
done_lurking 2 hours ago [-]
Time complexity is something that applies to algorithms, and is determined analytically. I don't think it's useful to equivocate the definition with performance of implementations of algorithms determined through real world data. Both of these things are important, but they are not the same. The fact that they differ is not very surprising and does not necessarily mean that a misunderstanding has occurred.
emil-lp 3 hours ago [-]
> To put it differently, saying that a hash table is O(1) or constant time is a model
Nobody really says that, nor is it a model. It is the expected time complexity.
t-writescode 1 hours ago [-]
People … say that all the time. *I* say that all the time. It’s true enough to be accurate in 99.9% of the cases; and we put barriers in place when implementing code (like configuring the hashing algorithm) to keep it that way.
robertlagrant 2 hours ago [-]
I think people do say a hash table is O(1). It's the average time complexity (for some value of average) though, not the worst case.
jpitz 1 hours ago [-]
Yeah but there's a formal term for average time complexity, Theta
emil-lp 1 hours ago [-]
Θ does not usually mean average, but simultaneously upper and lower asymptotic bounds.
xdavidliu 56 minutes ago [-]
you might want to read that chapter of CLRS again
lou1306 1 hours ago [-]
O(1) insertion is the amortized worst-case time complexity, actually. (Amortized in the sense that the O(n) cost of copying is paid only during the n-th insertion). Average complexity is a slightly different thing.
2 days ago [-]
stkdump 2 hours ago [-]
Once a hash table has outgrown all caches, it should have linear performance. It's just that caches accelerate it at sufficiently small sizes.
javcasas 2 days ago [-]
Java's HashMap also has O(log(N)) complexity on hash collision, and that is before memory/cache details.
In fact, some studying on data structures probably leads to the conclusion that it is impossible to guarantee that an unbounded set/map to have access performance under O(log(N)).
pfdietz 31 minutes ago [-]
One get can O(1) expected time on any set of keys if one uses "universal hashing": choosing the hash function at random from a universal set of hash functions. The expectation is now over this random choice, not over some random distribution of key inputs. So even if an adversary gets to choose the keys the expected behavior is good.
> Java's HashMap also has O(log(N)) complexity on hash collision
Only for keys that implement Comparable.
emil-lp 3 hours ago [-]
Expected
marcosdumay 2 hours ago [-]
Nowadays I expected an opaque dictionary to be amortized O(1).
Granted, one can technically call that O(log(n)), but that's not a helpful categorization.
emil-lp 1 hours ago [-]
You cannot guarantee that from a hash map since an adversary who knows the hash function (unless it's cryptographic) could game the data structure to their advantage.
jldugger 1 hours ago [-]
Uh, what is going on with this benchmark?
Why is M so big? Why does it cross the maxint boundary? Why is constructing the list comprehension part of the benchmark? Why are we summing the set? Why are we only measuring 5 values for n?
oefrha 2 hours ago [-]
This "quadratic-time performance" is incredibly disingenuous. First, it's doing n operations that are each O(n), so it's more like "can have linear time performance, but done n times so I can give you a scary title".
Edit: A charitable take is constructing a set/dict from a list is indeed a common operation so it's worthwhile to think about its complexity, but it's not really one of the standard operations when discussing the performance of a hashset/hashmap, so really shouldn't be this handwavy.
And instead of attacking some straw man "It is indeed widely believed that ..." claim (widely believed by who?), why not attack what's literally on docs.python.org? https://docs.python.org/3/library/time-complexity.html:
> dict
> The times listed for dict objects are average-case times, as they assume the hash function for the objects is sufficiently robust to make collisions uncommon. They also assume the keys are well-distributed among the set of possible keys. In the worst case, when every key hashes to the same value, each of the O(1) operations below instead takes O(n) time. They also assume that hashing and comparing a key is O(1). For more detail on the implementation, see How are dictionaries implemented in CPython?.
> ...
> set, frozenset
> See dict as the set and frozenset implementations are similar, and the same caveats apply. In the worst case, O(1) operations instead take O(n) time, and operations that look up every element degrade accordingly.
You explicitly construct a list of ints that are all multiples of sys.hash_info.modulus and hence all hash to 0, no shit you get that well documented O(n) behavior.
The discussion of CPU cache is good though, so why hide that behind this clickbait.
If you are really concerned about it, compute the empirical roofline for your machine.
Also, if the point is to point out memory hierarchies, it's not 'quadratic performance.' The algorithm doesn't behave differently once it spills over. The costs just get bigger.
The O(1) is the expected average case, which usually holds.
Yeah, O(N^2) is theoretically possible, but unless you're defending against some sort of denial of service attack, in practice it rarely matters.
Still, if you can guess a sensible initial size for a hash table you can avoid a lot of the overhead of rehashing.
The lesson of the talk is that if you are idiomatic then you will benefit as the language improves.
https://www.youtube.com/watch?v=npw4s1QTmPg
At a large enough size to be interesting, everything is dominated by IO and because IO is slow, at any interesting size performance is a matter of tailoring the implementation to the details of the data {0}.
Engineering is hard work, not naive math.
[0] Data might be arbitrary but it is never random. Not being random is what makes it data.
Nobody really says that, nor is it a model. It is the expected time complexity.
https://docs.oracle.com/javase/8/docs/api/java/util/HashMap....
In fact, some studying on data structures probably leads to the conclusion that it is impossible to guarantee that an unbounded set/map to have access performance under O(log(N)).
https://en.wikipedia.org/wiki/Universal_hashing
Only for keys that implement Comparable.
Granted, one can technically call that O(log(n)), but that's not a helpful categorization.
Why is M so big? Why does it cross the maxint boundary? Why is constructing the list comprehension part of the benchmark? Why are we summing the set? Why are we only measuring 5 values for n?
Edit: A charitable take is constructing a set/dict from a list is indeed a common operation so it's worthwhile to think about its complexity, but it's not really one of the standard operations when discussing the performance of a hashset/hashmap, so really shouldn't be this handwavy.
And instead of attacking some straw man "It is indeed widely believed that ..." claim (widely believed by who?), why not attack what's literally on docs.python.org? https://docs.python.org/3/library/time-complexity.html:
> dict
> The times listed for dict objects are average-case times, as they assume the hash function for the objects is sufficiently robust to make collisions uncommon. They also assume the keys are well-distributed among the set of possible keys. In the worst case, when every key hashes to the same value, each of the O(1) operations below instead takes O(n) time. They also assume that hashing and comparing a key is O(1). For more detail on the implementation, see How are dictionaries implemented in CPython?.
> ...
> set, frozenset
> See dict as the set and frozenset implementations are similar, and the same caveats apply. In the worst case, O(1) operations instead take O(n) time, and operations that look up every element degrade accordingly.
You explicitly construct a list of ints that are all multiples of sys.hash_info.modulus and hence all hash to 0, no shit you get that well documented O(n) behavior.The discussion of CPU cache is good though, so why hide that behind this clickbait.