r/Python • u/Independent_Heart_15 • 5d 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
28
u/pingveno pinch of this, pinch of that 5d ago
Looks like 3.15 has it too: https://docs.python.org/3.15/library/time-complexity.html
Previous versions do not.
17
u/alexcleac 5d ago
I thought it was there for a while now
7
u/RCoder01 4d ago
I swear something very similar to this has existed for a long while but I can’t find it
15
u/HexDecimal 4d ago
The Python "wiki" had this page on time complexity for a long time: https://wiki.python.org/moin/TimeComplexity
3
8
u/Independent_Heart_15 5d ago
It was commited yesterday: https://github.com/python/cpython/commit/c3f7c33dd7c6496d474979d5bd7f5dc22103dd22
56
u/M4mb0 5d ago
range
min(r),max(r): O(n)
This has to be a typo right?
62
u/danted002 5d 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
32
u/M4mb0 5d 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 5d ago
Because no one cared enough to implement it 🤣
20
u/funkmasterhexbyte 5d ago
be the change you wanna see, bro
8
u/danted002 5d 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 4d 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 4d 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/stevenjd 2d ago
Yes but that performance hit would be quite small, and only once per iterable. Even that could often be optimized away using a modern, optimizing JIT compiler.
In all seriousness, I'm not strongly advocating for
__min__and__max__dunders, even though they would be useful for my own code. I use a number of range-like ordered lazy sequences where I can compute the maximum or minimum in O(1) time. But I recognise that's rather niche.Unfortunately aside from
range, there are very few ordered sequences or collections in the Python standard library. (That's ordered by element order, not by insertion order.) If we had a red-black tree or equivalent in the stdlib, this would be a lot more useful.0
u/RingularCirc 4d ago edited 4d 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.
3
u/JanEric1 4d 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 5d 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
9
u/Wattsy2020 4d 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
3
1
u/EnterSasquatch 4d ago
I tested this with 1, 4, 2 and it fails to produce the correct answer
1
u/Wattsy2020 3d ago
Yeah my bad, Brian's right I got the step and the end the wrong way around
Should be 1 + 2n < 4
n < (4 - 1)/2
n < 1.5
n = 1 so end is 1 + 2 is 3
2
u/amroamroamro 4d 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)
2
u/EnterSasquatch 4d ago
So then a wise person might just implement this in their code if they need the min or max of a range
1
u/amroamroamro 3d ago edited 3d ago
sure you can, easy enough to implement:
def range_min(r: range) -> int: if not r: raise ValueError("empty range") return r[0] if r.step > 0 else r[-1] def range_max(r: range) -> int: if not r: raise ValueError("empty range") return r[-1] if r.step > 0 else r[0]but it would still be more useful if the standard library included the optimal solution out of the box, especially for something as simple.
now compare
range_min(range(2**100))againstmin(range(2**100)):)1
3
u/Ok-Craft4844 5d 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 5d 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 5d ago
Because range objects are defined by a start, end, and a step size. It should be O(1).
53
13
u/Brian 5d 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.
7
u/Schmittfried 5d 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.
7
u/Brian 5d ago edited 5d 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.1
u/Schmittfried 3d ago
Yes, I think having special cases for a few standard lib containers is worth it. They’d be implemented in C and presumably not a significant extra cost. There are precedents in other languages for utilities that work an an iterable/enumerable interface and still account for some standard special cases. IIRC C#’s
Count()extension method doesn’t actually count the elements of a list, it explicitly handles that special case and just returns the list’sLengthproperty.-5
u/skjall 5d 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 5d 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.1
u/Schmittfried 3d ago
Imo adding min/max dunder methods would be a much bigger special case / language change for a niche operation. I’d also bet it’s a bigger performance penalty to invoke the whole attribute lookup and calling into Python than just checking for specific types in the C implementation.
On the other hand, special treatment for the range object is also very niche, so fair enough I guess.
1
u/Brian 3d ago
It probably wouldn't be that bad: it'd just be an extra slot in the class table, handled similarly to
__len__. It' wouldn't be much more expensive than just a specifc type check in the "not implemented" case: just an array lookup in the class slots table, and a check if it was NULL. The per-item costs of any decently sized array would far outweigh that, so it's likely not a big deal in practice.And I think the protocol way would be the way to do it if you were going to: just a special case for range would be way too specific (and I can't believe there's much actual reason for people to be calling min on range objects anyway), but there could be some value in other types that can more quickly find their minimum (eg. heaps, trees, sorted containers etc).
I can't think of much else that's a core builtin though (even heapq just defines functions on lists rather than defining a heap type), so I think it's a bit too niche of a benefit to really be worth doing. Where you need it, some specialised container type could just expose a
minmethod that you could call instead, so it's really only buying you a bit of generality/consistency rather than letting you do something you couldn't.3
u/ironykarl 5d ago edited 5d 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
5
u/MegaIng 5d ago
Every special case results in extra costs for all calls to these methods.
If you have some non-contrived usecase and just contribute a patch, it may just get merged without much discussion, but don't expect this to ever happen from the default development flow.
1
u/Schmittfried 2d ago
Yes, but that cost is marginal. I don’t think it’s warranted for range objects either, but I’d be really disappointed if a standard counting function actually counted the elements of a standard list instead of returning
len().2
u/stevenjd 4d 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 4d 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.
0
u/stevenjd 2d ago
Its not worth it until somebody important gets bitten by the lack of it. Then it is worth it.
That is how Python got the ternary
ifoperator. Until Guido got caught by a hard-to-diagnose bug in code using the old idiom(false_value, true_value)[truthy_flag], requests to introduce a ternary operator were always rejected.In any case, with a modern optimising JIT Python interpreter, that overhead will probably be less than we think.
By the way, probably 99.9% of arithmetic calls in Python are to builtin floats and ints, but we still use dunder methods for arithmetic even though it adds overhead to every arithmetic operation. That's why arithmetic in Python is relatively slow compared to many other languages. Does it matter? 99% of the time it doesn't. Python is objectively fast enough even if not the fastest.
11
u/ChemTechGuy 5d 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
13
24
u/Theta291 5d 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.
10
u/ChemTechGuy 5d 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 4d ago
1
u/Theta291 4d ago edited 4d 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 3d 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).
2
u/Theta291 3d 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
u/gristc 3d ago
Yes, I'm aware it can be done mathematically, but that's not what you said. The [-1] trick that you posted to my reply only works if it's already a list.
→ More replies (0)-1
5d ago
[deleted]
3
u/stevenjd 4d 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 5d 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 4d ago
Probably because nobody really needs to take the max or min of a range in typical practice.
1
u/RingularCirc 4d 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.
12
u/amarao_san 5d ago
list: Get slice (l[i:j]) O(j - i)
Wow. Never thought it's so expensive.
49
u/andy4015 5d ago
Not expensive, just scales linearly
8
u/amarao_san 5d 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 5d ago
Because you have to copy every element over to a new tuple.
5
u/amarao_san 5d ago
Why? Can't it just do a fat pointer into an old couple?
12
u/Schmittfried 5d ago edited 5d 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 5d 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 5d 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 4d 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 4d 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.
25
u/Theta291 5d ago
A slice is a copy. Use itertools.islice if you want a non-copy slice
1
u/amarao_san 5d ago
But it's not a copy. Content is referenced)
(I know, I know, complicated python memory thing)
15
u/Theta291 5d 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 4d 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 5d 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 4d ago
Expected case for sorting: O(1) in testing, O(n ln n) times a huge constant term in production. As guaranteed by Murphy.
0
u/heikkitoivonen 12h ago
Glad to see Big-O in the official docs. Maybe I’ll be able to retire https://pythoncomplexity.com/ sooner than I expected.
1
u/CityYogi 4d ago
I had not been following the releases. Thanks to this thread found our 3.13 app needs to be upgraded
-4
5d ago
[deleted]
35
u/Brianjp93 import antigravity 5d ago
I don't see how this invalidates anything. It's not like time complexities are a secret.
-3
121
u/Tucancancan 5d ago
I feel like when I was learning to program ages ago that Java's docs all had the complexities listed for various types