6 ms·
Python sets and dictionaries can have quadratic-time performance
- deleted 1mo ago[deleted]
- TristanDaCunha 1mo agoWhich statement in this article applies only to Python?
- robrenaud 1mo agoThe part where he chooses his inputs to hit worst case behavior in Python's hash function.
- progval 1mo agoHe doesn't. Inputs are: M = (1 << 61) - 1 values = [i * M for i in range(1, n + 1)] which are effectively random from the hash function's point of view, especially with a randomized seed (the default on current versions).
- amiga386 1mo agoHis inputs are large numbers that don't fit in a standard integer. Bigints. The set inclusion test not only has a hash lookup but an equality test, which will be a bigint comparision rather than integer comparison, and bitint comparison is itself O(n) based on the size of the bignum. And the code that tests each bignum is in the set also _sums_ those bignums, which itself is an O(n) operation based on the size of the bignums being summed. So he's not testing dict/set performance, he's testing bignum performance, because of the inputs he deliberately chose https://news.ycombinator.com/item?id=49650737 https://news.ycombinator.com/item?id=49650737
- minitech 1mo agoCPython has the unfortunate property that ints aren’t covered by hash randomization, and `hash(x) == x % ((1 << 61) - 1)` always.
- progval 1mo agoOuch, that's a big footgun. Why was the lack of randomization considered a vulnerability, but not this?
- minitech 21d agoI haven’t looked into the history, but my understanding from the comments is that it exists to preserve `x == y -> hash(x) == hash(y)` for `x` and `y` with different numeric types (int, float, decimal) – which seems like it should be solvable, but isn’t a constraint I’d want to be working under, so I sympathize.
- 0xa2 1mo agoThe map is not the territory.
- javcasas 1mo agoJava'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.html 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)).
- emil-lp 1mo agoExpected
- marcosdumay 1mo agoNowadays 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 1mo agoYou 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.
- aw1621107 1mo ago> Java's HashMap also has O(log(N)) complexity on hash collision Only for keys that implement Comparable.
- pfdietz 1mo agoOne 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. https://en.wikipedia.org/wiki/Universal_hashing https://en.wikipedia.org/wiki/Universal_hashing For hashing with chaining, the hash function just has to make the hash values of keys pairwise independent to achieve O(1) expected time per operation; higher order independence is not needed.
- brudgers 1mo agoBut 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.
- streetfighter64 1mo ago> Data might be arbitrary but it is never random. Not being random is what makes it data. Counterexamples: crypto keys, stock price history, weather observations, radio telescope recordings
- marcta 1mo agoI think the point is that once it becomes a crypto key, stock price, weather observation, whatever, the datum ceases to be random and becomes arbitrary.
- streetfighter64 26d agoThat is a nonsensical definition of random. If I roll a dice it's random, but if I write down the result it's not? Arbitrary is also quite different from random. Bad passwords are arbitrary, good passwords are random. If you ask a human to give an arbitrary number between 1 and 10, the answer will be 7 way more often than a random number between 1 and 10.
- d0mine 1mo agoNote: weather observations being truly random data has been proved just recently (Navier-Stokes equations)
- emil-lp 1mo 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.
- robertlagrant 1mo agoI 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 1mo agoYeah but there's a formal term for average time complexity, Theta
- emil-lp 1mo agoΘ does not usually mean average, but simultaneously upper and lower asymptotic bounds.
- xdavidliu 1mo agoyou might want to read that chapter of CLRS again
- jpitz 1mo agoYou're right. It isn't the average bound, it is the upper and lower bound stated together ( as long as thats the same function )
- lou1306 1mo agoO(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.
- d0mine 1mo ago
- juancn 1mo agoThat'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.
- taeric 1mo agoI used to think of it more as O(1) being the expected average of the cases. My guess is I'm probably thinking of it more as an amortized cost, in that framing? (That is, not that it is the average case. Is the average of all cases.) To your point on the worst case being something you may worry about in denial of service, I think it is often the case that people should set bounds on what size N they will deal with in a program. And then decide from there on whether you are worried about some of the more esoteric growth patterns.
- afdbcreid 1mo agoIt is both amortized and average, because the map may need to grow. But the complexity without growing is average, not amortized (it's possible to build hash functions for which the probability will mean O(1) for all accesses, and hash functions which will be O(N) for all accesses).
- taeric 28d agoAmortized is a bit different, though? It largely implies that there is a heavy cost periodically. Average just implies that it varies. Which, fair that "massive cost periodically" is compatible with that. Just seems to have a very different context, to me. With hashtables, it was more that it was not guaranteed to be the minimal cost. Just, depending on statistics of the data that you feed to it, it shouldn't be the worst case.
- Good4boothee 1mo ago
- oefrha 1mo agoThis "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 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. +--------------------------------------+------------+ | Operation | Complexity | +--------------------------------------+------------+ | x in s | O(1) | | Copy (s.copy()) [6] [7] | O(n) | | Add (s.add(x)) [1] | O(1) | | Discard (s.discard(x), s.remove(x)) | O(1) | | ... | ... | +--------------------------------------+------------+ 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.
- stkdump 1mo agoOnce a hash table has outgrown all caches, it should have linear performance. It's just that caches accelerate it at sufficiently small sizes.
- done_lurking 1mo agoTime 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.
- aadyachinubhai 1mo agoThat 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.
- jldugger 1mo agoUh, 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?
- brody_hamer 1mo agoYea if I cast the large calculated integers to strings, performance is O(1) `values = [str(i * M) for i in range(1, n + 1)]` or `values = [i * M % 1_000_000_000_000_000 for i in range(1, n + 1)]`
- jldugger 1mo agoPart of the secret explained elsewhere on this HN post is that the OP is selecting values that all collide. Most hash tables handle collisions with linked lists that would be linear insert. It's O(1) average case but O(n) if you pull an "oops all collisions on the same bucket" stunt.
- northisup 1mo agoRaymond 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. https://www.youtube.com/watch?v=npw4s1QTmPg https://www.youtube.com/watch?v=npw4s1QTmPg
- sgdpk 1mo agoVery cool presentation. I loved how he says that they improved dict so much that they basically rediscovered database tables with indices.
- alexpotato 1mo agoDave Beazley has a great talk about using Python built ins. Def worth a watch as he is funny but also super cool to see someone use a REPL this way: https://www.youtube.com/watch?v=lyDLAutA88s https://www.youtube.com/watch?v=lyDLAutA88s
- jaydeepg 1mo ago[flagged]
- ok123456 1mo agoMost 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.
- koala_man 1mo ago> The costs just get bigger. By a constant factor no less (until we get into theoretical physics)
- afdbcreid 1mo agoBecause complexity models that involve memory hierarchy are an active research area and are super complex. Also, "plain" complexity is still useful: despite the constant factor, at large N (and this is sometimes a real possibility) the complexity will still win. For example, despite binary search being less cache-friendly (it can be made more with some tricks but not the same), it still defeats linear search most of the time.
- mitxela 1mo agoMoat of the time if you have at least several hundred elements. Benchmark it and see.
- vyftec_wpsec 1mo ago[flagged]
- coolThingsFirst 1mo agoLemire back again with CS101 insights. Next, he will teach us doubles have finite precision.
- ot 1mo agoO(1) doesn't mean constant, it means bounded by a constant. An algorithm can be faster with small n and converge to a horizontal asymptote as n goes to infinity, and it would still be O(1). In a real machine there is no infinity, but hundreds of GBs of memory are "infinity enough" compared to the cache size [1]. So asymptotic analysis is still a decent model. I'm surprised that even a CS professor confuses this. [1] Ok if we want to be pedantic memory access is logarithmic due to the traversal of page tables, but you can use huge pages.
- Insanity 1mo agoGenerally for performance, the rule is you _measure_ it, you don't rely on big-O. So if you're really concerned, please just use a profiler. Also hashmaps (python Dicts) have amortized O(1) and not O(1) big-O.
- afdbcreid 1mo agoMeasurement is for micro-optimizations, and it's definitely important. But you should also know the complexity.
- Drupon 1mo agoReal big brain moment in the comments >Can we say that since every real-life data structure size is bounded by some constant, it is O(1)? If not, why? >>You may, yes. Very powerful thinking coming from someone who is "a software performance expert. He ranks among the top 2% of scientists globally (Stanford/Elsevier 2025) and is one of GitHub's top 1000 most followed developers"
- anewhnaccount2 1mo agoIt's true you can. Just as you can say that you can enumerate all memory states in a real computer so it can be modelled as a finite state machine. These asymptotic models aren't real (our world as we experience it is finite and bounded) and exist as models from which to gain insights which we can transfer back. I love this argument BTW a classic that usually comes up in these discussions.
- Drupon 1mo agoAsymptotic models are not a statement of how long it will take; they are classes of functions modeling the relationship between some performance outcome (run time most often, but sometimes memory or other things) and data coming in. These mappings from input to performance characteristics are not conditioned on physical limitations but are rather abstract tools for measuring that relationship.
- Archer6621 1mo agoIf you have an instance (which is what I assume is implied by "real-life data structure") bounded by a particular size, then you could say that the runtime complexity is constant with respect to that bound. Whether that is a useful statement to make is another discussion entirely. On its own probably not. It can potentially be useful for analyzing the runtime complexity of operations in more complex algorithms that use this data structure up to a certain fixed size, e.g. as a buffer/cache of some sort.
- Drupon 1mo ago
- xboxnolifes 1mo agoReminds me of the article about random memory access being O(√N): https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
- deleted 1mo ago[deleted]
- amiga386 1mo agoI call shenanigans on this. import timeit def test(M,n): values = [i * M for i in range(1, n + 1)] s = set(values) sum(v in s for v in values) M = (1 << 61) - 1 for n in [1000, 2000, 4000, 8000, 16000]: print(f"M=2^61-1, {n=:5d} ->", timeit.timeit(lambda: test(M,n), number=3)) for n in [1000, 2000, 4000, 8000, 16000]: print(f"M=1, {n=:5d} ->", timeit.timeit(lambda: test(1,n), number=3)) Magically, when you stop using BIGINTS as the set members and just use regular ints, there is no such quadratic explosion. M=2^61-1, n= 1000 -> 0.13144792200182565 M=2^61-1, n= 2000 -> 0.48016051898594014 M=2^61-1, n= 4000 -> 2.058760045998497 M=2^61-1, n= 8000 -> 7.843778470996767 M=2^61-1, n=16000 -> 40.01485426299041 M=1, n= 1000 -> 0.000748768012272194 M=1, n= 2000 -> 0.0015750699967611581 M=1, n= 4000 -> 0.003037029004190117 M=1, n= 8000 -> 0.006664915999863297 M=1, n=16000 -> 0.012693285010755062 The runtime is being spent hashing bigints, comparing candidate bigint(s) against reference bigints, and summing bigints. And there's also some set lookups.
- nilslindemann 1mo agoActually, as the Google AI just taught me [1], the bad performance results from hash _collisions_, not from using bigints (which the author also mentions): import timeit def test(M, n): values = [i * M for i in range(1, n + 1)] s = set(values) sum(v in s for v in values) M = (1 << 61) - 1 # This is a bigint and also a Mersenne prime number N = (1 << 61) + 42 # This is a bigint, but not a Mersenne prime number # This runs slow for n in [1000, 2000, 4000, 8000, 16000]: print(f"M=2^61-1, {n=:5d} ->", timeit.timeit(lambda: test(M,n), number=3)) # This runs with normal performance for n in [1000, 2000, 4000, 8000, 16000]: print(f"N=2^61+42, {n=:5d} ->", timeit.timeit(lambda: test(N,n), number=3)) (1 << 61) - 1 is a Mersenne prime number, which Python uses internally on 64-bit systems for the hash algorithm for big integers. When multiplying numbers with this prime number, hash collisions become common, and this slows down the performance. This is not completely theoretical; hash-DoS attacks make use of that. For this reason, there is hash salting since Python 3.3 for strings, bytes, and datetime objects [2], but not for integers, because the most common attack surface is JSON, but JSON keys are strings, and hash salting would slow down the performance of math operations. [1] https://share.google/aimode/cXQyw0SDPr5FnhBc5 https://share.google/aimode/cXQyw0SDPr5FnhBc5, available for seven days [2] See the grey info box here: https://docs.python.org/3/reference/datamodel.html#object.__hash__ https://docs.python.org/3/reference/datamodel.html#object.__...
- deleted 1mo ago[deleted]
- hillbillyDev676 1mo ago[flagged]
- zahlman 1mo agoIt feels like I keep ending up leaving a comment on the unpopular version of a submission that ends up being reposted and getting traction later. https://news.ycombinator.com/item?id=49553744 https://news.ycombinator.com/item?id=49553744