Python sets and dictionaries can have quadratic-time performance
1–10 of 67 posts
Re: Python sets and dictionaries can have quadratic-time performance
#2[deleted]
Re: Python sets and dictionaries can have quadratic-time performance
#3The map is not the territory.
Re: Python sets and dictionaries can have quadratic-time performance
#4Java's HashMap also has O(log(N)) complexity on hash collision, and that is before memory/cache details.
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)).
Re: Python sets and dictionaries can have quadratic-time performance
#5But 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.
Re: Python sets and dictionaries can have quadratic-time performance
#6Java's HashMap also has O(log(N)) complexity on hash collision, and that is before memory/cache details. 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)).
Expected
Re: Python sets and dictionaries can have quadratic-time performance
#7> 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.
Re: Python sets and dictionaries can have quadratic-time performance
#8Java's HashMap also has O(log(N)) complexity on hash collision, and that is before memory/cache details. 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)).
> Java's HashMap also has O(log(N)) complexity on hash collision
Only for keys that implement Comparable.
Re: Python sets and dictionaries can have quadratic-time performance
#9That'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.
Re: Python sets and dictionaries can have quadratic-time performance
#10> 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.
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.