Python sets and dictionaries can have quadratic-time performance

Join the discussion

• Hacker News
• 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.
  by aadyachinubhai
• 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.
  by done_lurking
• Reminds me of the article about random memory access being O(√N): https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
  by xboxnolifes
• 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.

  by ok123456
• 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.

  by brudgers
• 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.

  by juancn
• 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.

  https://www.youtube.com/watch?v=npw4s1QTmPg

  by northisup
• 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 << 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.
  by amiga386