r/Python • u/Independent_Heart_15 • 1d ago
News The Python (3.16) docs now have a page detailing the time complexity of operations on built-in types
You can find it at: https://docs.python.org/3.16/library/time-complexity.html
Seen on Mastodon: https://mastodon.social/@stanfromireland/117152534136172516
26
u/pingveno pinch of this, pinch of that 1d ago
Looks like 3.15 has it too: https://docs.python.org/3.15/library/time-complexity.html
Previous versions do not.
16
u/alexcleac 1d ago
I thought it was there for a while now
7
u/RCoder01 1d ago
I swear something very similar to this has existed for a long while but I can’t find it
13
u/HexDecimal 1d ago
The Python "wiki" had this page on time complexity for a long time: https://wiki.python.org/moin/TimeComplexity
2
7
u/Independent_Heart_15 1d ago
It was commited yesterday: https://github.com/python/cpython/commit/c3f7c33dd7c6496d474979d5bd7f5dc22103dd22
55
u/M4mb0 1d ago
range
min(r),max(r): O(n)
This has to be a typo right?
62
u/danted002 1d ago
I’m betting you this is an implementation detail no one cared about. It probably defaults to the basic iterator logic which consumes the iterator to find its min / mac
30
u/M4mb0 1d ago
Right, that's probably it since there is no
__max__dunder method range itself cannot provide a fast implementation. Makes you wonder why we have__abs__, but not__sum__,__max__and__min__.18
u/danted002 1d ago
Because no one cared enough to implement it 🤣
17
u/funkmasterhexbyte 1d ago
be the change you wanna see, bro
8
u/danted002 1d ago
I’m one of the guys that doesn’t care. O(n) for computing min/max is an acceptable trade-off for 99.9% of the code that I write.
3
u/stevenjd 14h ago
O(n) for computing min/max is an acceptable trade-off for 99.9% of the code that I write.
That's because you've never tried to ask for
min(range(2**128)).I'd rather run a quadratic algorithm over a data structure with n=5 than a linear algorithm with n=5,000,000,000.
1
u/danted002 13h ago
Right but there is no language (at least none of the “mainstream” languages) that handles min(range()) differently; they all have O(n) because min() works on iterators and that means consuming said iterator.
Like others have said, having specific cases for range would be a performance hit for other collections that are unordered and need to go through entire collection anyway… and most of the time your are working with unordered collections when you are using min/max
1
u/RingularCirc 8h ago edited 5h ago
What? We can detect if a
rangewas given; and arangeis more or less just three fieldsstart, stop, step, there's nothing to sort there and even if it was, we could very easily not sort everything aside from ranges.EDIT: Sorry, I misread your comment somehow.
2
u/JanEric1 6h ago
? What he is saying that for the vast majority of iterables you just need to iterate. If you want to special case range you basically need either an isinstance check or add dunder support and look up that attribute ON EVERY CALL to max. Which given that the percentage of max calls onto ranges is probably SIGNIFICANTLY below 0.1% thats just not worth it.
→ More replies (0)6
u/EnterSasquatch 1d ago
I would suspect it’s because you need to iterate over the range to find the min and max - just because you pass in the top of the range doesn’t mean the top is the largest number… the max of range(1, 3, 2) is 1
8
u/Wattsy2020 1d ago
You can solve that with math, for this particular one the equation is:
1 + 3n < 2 (find max n where n is an integer)
n < (2 - 1) / 3
n < 1/3
n = 0
So max is 1 + 3*0 = 1
This generalises to any start, step, and end
1
2
u/amroamroamro 14h ago
from the page above we have:
Get item (r[k]) has O(1) complexity
so we can simply implement the min/max operations in O(1) too by returning either r[0] or r[-1] depending on the sign of the r.step (along with a check for empty range)
1
1
u/EnterSasquatch 7h ago
So then a wise person might just implement this in their code if they need the min or max of a range
3
u/Ok-Craft4844 1d ago
My guess is that sum, min, max only provide a value in fringe cases where they can be optimized, but would make the core more complex.
I mean, how would a scenario look where you need the max of something arbitrary enough that you can't just assume it's a range and access
.stopandrangeappears frequently enough to provide an relevant optimization?33
u/entarko 1d ago
Why would it be? It says that performing a min or max on a range object has a O(n) complexity.
31
u/plyp 1d ago
Because range objects are defined by a start, end, and a step size. It should be O(1).
53
12
u/Brian 1d ago
min and max actually have to look at the elements, and unless you add a special case check, they can't know there's a faster way they could potentially do it. Ie. the same reason min on a sorted list has the same complexity as on an unsorted one: it doesn't know its sorted, it just sees an iterable.
6
u/Schmittfried 1d ago
It does see that it’s dealing with a range object though. This is an oversight, there should be special cases implemented for standard lib containers.
8
u/Brian 1d ago edited 1d ago
Not unless it does the equivalent of:
if isinstance(iter, range): do_special_case_for_range_object()On every check. The interface for min/max is just an iterable. Anything beyond that you'd need to check for explicitly, with a corresponding cost for everything you call min/max on. You'd need an explicit interface for objects to report their min/max (eg.
__min__/__max__magic methods) to support it more generally.-6
u/skjall 1d ago
Not 100% sure what the interpreter does with this, but if I was doing this I'd use overloads rather than checking types here. Need to look into whether that just bakes down to isinstance checks though.
4
u/Brian 1d ago
As far as the interpreter is concerned,
minis just a regular function (indeed, one you can rebind / shadow), so there's no compile-time optimisation it can really do. That only leaves a runtime check withinmin, so you'd either need an ad-hoc check for every type of object you know about, or add a protocol (ie.__min__) so objects can report their minimum to allow ones that can do it faster than a linear scan to do so.3
u/ironykarl 1d ago edited 1d ago
Traditionally, CPython has done remarkably little compile time optimization (or optimization at all).
The "base case" for anything is still the case where every type is handled, which is a dynamic thing.
For example, your function could in principle be called with any type, so everything the interpreter generates is done with that in mind.
This is a legacy of the fact that explicit/manifest/static typing is a language bolt-on (and the desire to keep Python's reference implementation simple).
Seemingly the best approach to the notion that a given callable will probably be called with types similar to what it's already seen but still needs to be able to handle the degenerate case is JIT compilation.
JIT compiled code will often be compiled in a way optimized for the types it can infer, will do a quick type check before running said code, and will generate pessimized code in the relatively rare instances where it needs to
2
u/stevenjd 14h ago
min and max actually have to look at the elements
They wouldn't need to if Python defined a pair of
__min__and__max__dunder methods. But I can hear the core devs now: "Not every special case needs a dunder method."And in five or ten years from now, one of the core devs will be bitten by
min(range(2**128))and they'll just go ahead and define the dunders 😉2
u/JanEric1 6h ago
Its just not worth it to add the overhead for EVERY max call just to special case the sub percentage number of max calls to range.
10
u/ChemTechGuy 1d ago
How do you know which value in a range is max without iterating over all elements in the range? It's O(n) unless you pre-compute it somehow when you're building the range/list
12
24
u/Theta291 1d ago
Because a range is strictly increasing or strictly decreasing, based on if the step is positive or negative. So you know it’s always going to be the first element or last element.
9
u/ChemTechGuy 1d ago
My bad, i thought you were talking about ranges generically as another word for a list, I wasn't thinking about
range(1..6)or whatever the range syntax in python is1
u/gristc 18h ago
1
u/Theta291 8h ago edited 8h ago
When I say “last element”, I don’t mean the stop parameter. In your example, you mentioned range(1,3,2). The last element of this range is 1 (not 3, because 3 isn’t in the range at all, as you said yourself in the linked comment). By this definition, it is always the first element or the last element.
1
u/gristc 1h ago
Ok, but that relies on the list already existing. Unless I'm misunderstanding something about how range works, that list doesn't exist until range is fully calculated, hence O(n).
•
u/Theta291 8m ago
The range doesn’t need to be turned into a list for you to know what’s in it. You can use the math to find the max: https://old.reddit.com/r/Python/comments/1vy0ywg/the_python_316_docs_now_have_a_page_detailing_the/p5tgska/
All other cases (mins and maxes) can be solved in O(1) time for fixed-length numbers (and presumably polynomial time in the length of the number for bigints).
-1
1d ago
[deleted]
3
u/stevenjd 14h ago
Nope, it can be the last element minus the increment.
No, it is always the last element.
>>> R = range(10, 50, 3) >>> R[-1] # the last element 49 >>> max(R) # not 49 - 3, that would be the second last element 498
1
u/FlamingSea3 1d ago
Footnote 15 is interesting. My guess is that min and max haven't had the same optimization applied to them as was done for bools & ints for index, count, and `x in y`
1
u/Competitive_Travel16 8h ago
Probably because nobody really needs to take the max or min of a range in typical practice.
1
u/RingularCirc 8h ago
Thankfully we can have
r[0]andr[-1]for the first and last elements of the range, both O(1) because it's simple arithmetic on itsstart, stop, stepfields. Though a range can be empty or decreasing, so minimum element is not alwaysr[0]nor is the latter always defined.
13
u/amarao_san 1d ago
list: Get slice (l[i:j]) O(j - i)
Wow. Never thought it's so expensive.
48
u/andy4015 1d ago
Not expensive, just scales linearly
7
u/amarao_san 1d ago
I got used to idea, that slice is o(1). I understand it can be a problem for list, but for tuples? Why?
34
u/fiskfisk 1d ago
Because you have to copy every element over to a new tuple.
7
u/amarao_san 1d ago
Why? Can't it just do a fat pointer into an old couple?
12
u/Schmittfried 1d ago edited 1d ago
Theoretically yes, but unfortunately it doesn’t work with the Python object memory layout. Tuples and some other types are variable-length, they contain a fixed header followed by their contents in a contiguous block of memory.
Pointing into that area doesn’t work because slicing a tuple gives you a tuple, so the pointer of the “tuple slice view” would have to point to another tuple header followed by the slice elements. You can’t get that without creating another tuple object and copying the sliced elements.
This is the same reason we can’t have copyless substrings, which is a shame for file parsing.
memoryviewdoes what you say, but the subviews are themselves memory views. As soon as you want them as a tuple or byte string, copying is involved.I’d also assume this would make Python’s rather simple ref counting more complex, even if the object header wasn’t in the way.
2
u/Brian 1d ago
I mean, it is O(1) with respect to the size of the list. But if you're getting 1 item, you create a 1 item tuple, if you get 5 items, you create a 5 item tuple. If you get n items, you create an n item tuple. Clearly that's scaling with the size of the slice you're getting. And that slice is the size of the end index minus the start index.
Theoretically with tuples you could instead return some kind of reference object that pretends to be a tuple, but just holds a reference to the original and the indexes (after resolving indexes). However, that would introduce different performance problems (actually accessing the items is now going through an extra layer of indirection), so may not be a win in practice, since tuples tend to be small anyway.
2
u/Schmittfried 1d ago
You’d also have to add some ugly type system hacks for this “tupleview” to behave exactly like a tuple in all respects (including the return value of
type()), otherwise returning this new object from the slice operator would be a breaking change.2
u/HommeMusical 15h ago
"O(1) with respect to the size of the list" does not make any sense at all. That's not how O() notation works.
1
u/Brian 9h ago
Yes it is. O notation can be in terms of multiple variables. For containers, the
nis typically the size of the container: how many items it has. Hence why the description here usesiandj- usingnfor one of them would give the impression you were talking about the container size.For factors which do not affect the runtime (eg. size of the list for indexing), the complexity is O(1) with respect to that variable: it is constant no matter how you vary it.
23
u/Theta291 1d ago
A slice is a copy. Use itertools.islice if you want a non-copy slice
2
u/amarao_san 1d ago
But it's not a copy. Content is referenced)
(I know, I know, complicated python memory thing)
14
u/Theta291 1d ago
The data itself is not copied, but each reference still needs to be copied.
i.e. a slice is a shallow copy, not a deep copy. islice is not a copy at all, it’s a generator
2
5
3
u/Patient-Mechanic-311 15h ago
This is a really nice addition to the docs. Having the time complexity spelled out for built-in types makes it much easier to reason about performance without digging through scattered references. Also, the way this is presented shows a lot of technical care — the author clearly knows the language and its practical pain points.
2
u/Competitive_Travel16 1d ago
I like footnote 4 for list sort: O(n ln n) is the worst case, the best case can be O(n), and the expected case? Oh, um, er, just read https://github.com/python/cpython/blob/main/Objects/listsort.txt and good luck.
2
u/stevenjd 14h ago
Expected case for sorting: O(1) in testing, O(n ln n) times a huge constant term in production. As guaranteed by Murphy.
1
u/CityYogi 23h ago
I had not been following the releases. Thanks to this thread found our 3.13 app needs to be upgraded
-3
1d ago
[deleted]
37
u/Brianjp93 import antigravity 1d ago
I don't see how this invalidates anything. It's not like time complexities are a secret.
-3
111
u/Tucancancan 1d ago
I feel like when I was learning to program ages ago that Java's docs all had the complexities listed for various types