6 ms·
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 benchm
by jldugger 6d 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?
- brody_hamer 6d 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 6d 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.