Time complexity of operations on Python's built-in types(docs.python.org) |
Time complexity of operations on Python's built-in types(docs.python.org) |
As a meta note, I've used many of these builtins over the years but, due to LLMs, have been using them less and less. Re-watching the video almost felt like watching bushcrafters make a chair using just a knife and saw...
However, I'm surprised to see no data structures at all with O(log(N)) complexity. Surely there are some use cases for which that's desirable?
Set/Delete/Lookup are all O(log(n))
See also: https://github.com/MagicStack/immutables (for something you can actually use)
p.s. I think the reason heapq isn't a type is that it's ancient code that's hung around from the early days of python.
Making the functions into methods wouldn't make them easier to use, it would just make the abstraction feel more familiar to those from a Java tradition rather than a C++ one.
I thought min and max where constants stored in the object. Basically you are just asking for one of the parameters it was created with.
It's a stronger claim than just saying O(n), because in the latter case you wouldn't be able to conclude that popping something 5 from the end has bounded time as the list grows.
- s[i:j] is O(j - i) because it creates a copy instead of a view
- max(range(n)) is O(n)
- substring search is O(n), which is good, but rfind is O(n m)
- iterative string concatenation (for c in ...: s += c) can be O(n^2) due to string immutability according to footnote 10, although it is O(n) in most cases due to an implementation detail of CPython: https://stackoverflow.com/a/34008199
> This is the worst case. Reverse searches are O(n) on typical input.
However, if the GC is, say, quadratic time, then this breaks the linearity of your algorithm.
This was indeed something that happened in recent releases og Python.
Seems like a bit of a stretch to me but possible?
https://github.com/python/cpython/issues/135824#issuecomment...
`x in range(n)` is already optimized, but that was easier since the `__contains__` method already existed, but an equivalent `__min__` or `__max__` does not.
Another idea[1] that I won't get official credit for, I guess. Which, you know, I was raised in the "ideas are nothing, implementation is everything" era of code, but it still hurts.
(Edit: I confused myself into thinking they were actually implementing the optimization in 3.16; they are not, or at least there's no evidence of it at present. Regardless, the hesitancy to implement this sort of improvement is rather irritating to me. See also https://github.com/python/cpython/issues/90716 .)
By the way, `x in range(n)` is only optimized for integer `x`. Not for nonconvertible types (where the answer should obviously just be False) and not for floating-point (values equal to an integer have to get converted and checked O(N) times, and other values can't be immediately rejected). That's been proposed and poorly received before too: https://discuss.python.org/t/_/18248 [2].
[0]: and I'd first thought of it long before that and didn't know where to propose it, plus it kept slipping my mind
[1]: like https://zahlman.github.io/posts/a-brief-annotation/
[2]: see also my later post there, which went ignored
See, you already made a mistake:
>>> min(range(10, 1, -3))
4
Of course, the actual implementation of constant time min/max on range would be trivial.
With the current implementation you can accidentally use first heapify_max and then heappop (forgetting the _max), accidentally append something through the normal list append method, change the priority of something unknowing that that breaks the invariant, or run into problems with "Tuple comparison breaks for (priority, task) pairs if the priorities are equal and the tasks do not have a default comparison order".
These headaches could have been mostly removed if these were in a class. And the option to use a custom sequence type could have surely been preserved.
Edit: Another example of that is the complexity of convolutional filtering, which is O(n min(log n, k)) for a signal of length n and a kernel of size k.
> neither the min or max of the range (their actual names are start and stop)
The point of the parenthetical is that GP is deliberately using the terms non-standardly, meaning the arguments of the `range` call, which makes sense in the context of engaging with GGP.
(allocation happens in the mutator, GC happens in the collector -- there is a symmetry)
The constant factor could be 500 or 50,000, but it's still proportional.
And allocations are some subset of the operations of the algorithm itself.
So then GC can't increase the overall time by more than a constant factor. So the big-O is the same.
(You could have some nuance on how to match GC operations to mutator operations, but the overall point is still true)
Lemma 16.43
Let ε > 0. For every n and k ≤ n there exists a (k, ε)-extractor Ext : {0, 1}^n × {0, 1}^t → {0, 1}^n
where t = O(n − k + log 1/ε).
Admittedly, they never define Big-Oh notation for functions with multiple inputs or for non-integers like ε, but it's definitely standard notation, not something they or the Python developers idiosyncratically invented.
Worst-case O(n-k) complexity in general implies worst-case O(1) complexity for the set of cases where k=n-<constant>. There are still multiple cases, just a subset of those that don't include worst of the general case.
O(f(n)) = O(g(n))
if and only if
sup_n∈N ‖f(n)‖/‖g(n)‖ < ∞.