Python sets, frozensets, and literals

Posted Jan 20, 2022 4:29 UTC (Thu) by foom (subscriber, #14868)
In reply to: Python sets, frozensets, and literals by NYKevin
Parent article: Python sets, frozensets, and literals

You cannot have a map of "n" elements, unless the size of the keys are at least log(n), since keys must be unique.

As such, if you say your keys are 32-bit integers, the number of elements, "n", in your map cannot possibly exceed 2**32. Thus, performance "as n goes to infinity" is meaningless, unless you make the approximation that your 32-bit integer keys can actually represent an infinite number of distinct values.

Python sets, frozensets, and literals

Posted Jan 20, 2022 12:34 UTC (Thu) by anselm (subscriber, #2796) [Link] (2 responses)

Thus, performance "as n goes to infinity" is meaningless

2³² may not technically be “infinity”, but if you're looking at O(1) vs. O(n), in the real world n=2³² is pretty likely to make itself noticeable, performance-wise, somehow.

Python sets, frozensets, and literals

Posted Jan 20, 2022 21:20 UTC (Thu) by ballombe (subscriber, #9523) [Link] (1 responses)

Not if the implied constant in the first O is 2^32 and 1 in the second O...
Just do not use the O notation when you do not mean it!

Python sets, frozensets, and literals

Posted Jan 20, 2022 22:50 UTC (Thu) by anselm (subscriber, #2796) [Link]

That's what the “in real life” bit was about. In real life, even with big-but-certainly-not-infinite n, O(n log n) heap sort usually performs better than O(n²) bubble sort.