Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Python sets and dictionaries can have quadratic-time performance

lemire.me

Post reply on HN
Print view View original

61–67 of 67 posts

Re: Python sets and dictionaries can have quadratic-time performance

#61

Post by mitxela »

amiga386 wrote: post #51

I 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 ", 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…

So why is it quadratic? Hashing 1I know you asked an AI later and it told you about hash collisions but I'm wondering where this first comment came from. Was it also AI?

Re: Python sets and dictionaries can have quadratic-time performance

#62

Post by mitxela »

afdbcreid wrote: post #41
ok123456 wrote: post #28

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.

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

Moat of the time if you have at least several hundred elements. Benchmark it and see.

Re: Python sets and dictionaries can have quadratic-time performance

#63

Post by zahlman »

mitxela wrote: post #61
amiga386 wrote: post #51

I 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 ", 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…

So why is it quadratic? Hashing 1 I know you asked an AI later and it told you about hash collisions but I'm wondering where this first comment came from. Was it also AI?

> I know you asked an AI later and it told you about hash collisions but I'm wondering where this first comment came from. Was it also AI?

That was two different people.

The first comment probably comes from finding the 1<<61-1 constant suspicious, running a micro-benchmark, and then not thinking about it too hard.

Re: Python sets and dictionaries can have quadratic-time performance

#65

Post by Good4boothee »

juancn wrote: post #9

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…

> but unless you're defending against some sort of denial of service attack, in practice it rarely matters.

That "rarely" contains most sites/webservices. Before programming languages started defending against it by applying randomization (and sometimes replacing degraded maps/buckets with treemaps) it was a real threat. I remember people were able to trigger DoS either by specially crafted query string params or HTTP headers. After all both are shoved into some kind of map by frameworks, before request is even passed to application code.

Re: Python sets and dictionaries can have quadratic-time performance

#66

Post by amiga386 »

mitxela wrote: post #61
amiga386 wrote: post #51

I 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 ", 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…

So why is it quadratic? Hashing 1 I know you asked an AI later and it told you about hash collisions but I'm wondering where this first comment came from. Was it also AI?

I wrote the first comment, thinking it's bignums, but no, it is hash collisions.

It's quadratic because that's what hash collisions mean for a closed hash. The worst cast scenario is that every item has the same hash value, thus goes in the same bucket, so to insert 40,000 unique items, you have to check against 0, 1, 2, 3, ... 40,000 existing items in a linear list (800,000,000 equality tests) to avoid inserting duplicates. To then do an inclusion test for all those items, you have to scan the list 40,000 times, stopping at element 0, 1, 2, ... 40,000, so another 800,000,000 equality tests.

It turns out that Python's hash value for integers is the integer itself, modulo (1<<62)-1, which is why he makes all his values multiples of that number, so they're all unique integers with the same hash value. Other than this very narrow case (or more likely creating unique objects whose __hash__ method deliberately/accidentally returns the same value), you'd find it hard to make this situation happen in normal code.

Re: Python sets and dictionaries can have quadratic-time performance

#67

Post by marcta »

streetfighter64 wrote: post #36
brudgers wrote: post #5

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…

> 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

I 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.
Post reply on HN