Rendered at 23:05:17 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
alexpotato 1 days ago [-]
Dave Beazley has a great talk about using Python built ins [0] for data analysis and other quick operations.
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...
Python is famously built around hash tables. So much so that several versions ago they made an improvement to the hash table implementation, and the entire language became several percent faster.
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?
krautsauer 1 days ago [-]
One reason you don't see a data structure with O(log(n)) operations in this list is that priority queues/heaps are not a built-in type. Weirdly, there isn't a type for them at all, just a bunch of functions (good luck if you use them wrong). https://docs.python.org/3/library/heapq.html
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.
zahlman 1 days ago [-]
There isn't a type for them for the same kind of reasons that `join` is a method on the joining string. That is, it lets you reuse that code for multiple sequence types, including ones that don't exist yet. This is just something that happens with ad-hoc polymorphism, but it's also good to keep class interfaces small and implement other functionality in terms of them. Herb Sutter would approve.
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.
krautsauer 12 hours ago [-]
Easier I don't know, but safer for sure.
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.
This was one of the main inspirations when I started https://pythoncomplexity.com/. Glad to see Big-O in the official docs. Maybe one day my project will become obsolete.
wodenokoto 2 days ago [-]
Why are `min(r)` and `max(r)` for range objects o(n) ?
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.
gpugreg 1 days ago [-]
Because the use case is very niche and nobody optimized it yet.
`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.
zahlman 1 days ago [-]
Man, I proposed the idea of `__min__`/`__max__` (and a few others) in 2023[0], exactly because of this kind of big-O optimization potential, and it was poorly received: https://discuss.python.org/t/_/25095
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
[2]: see also my later post there, which went ignored
jonathrg 1 days ago [-]
It's not an optimization if it pessimizes almost all usage by adding a check for the dunder
zahlman 2 hours ago [-]
Plenty of people would naturally expect `if x in range(big_number, other_big_number)` to work efficiently rather than having to write the comparison logic (and modulo check, if a step is involved) explicitly. If the code has `if x in y:` where y is a duck-typed input, it's awkward to special-case that.
Who is making membership checks against trivially-sized collections in a hot loop?
dist-epoch 1 days ago [-]
> Basically you are just asking for one of the parameters it was created with.
See, you already made a mistake:
>>> min(range(10, 1, -3))
4
4 is neither the min or max of the range (their actual names are start and stop), and notice how the max is the first argument and the min is the second argument
Of course, the actual implementation of constant time min/max on range would be trivial.
d0mine 1 days ago [-]
4 is the min of the range (stop (1 here) is never included (by definition. Ask Dijkstra why))
zahlman 1 days ago [-]
Read it again:
> 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.
mwkaufma 1 days ago [-]
Isn't O(n - k) or O(len(l1) + len(l2)) just O(n)? Instead of blurring the line between complexity-analysis and cycle-counting, just print both the complexity and the est proportional cycle-count as separate measures.
bobmarleybiceps 23 hours ago [-]
I think it's not unreasonable or uncommon for big O to track separate variables without reducing them, just to highlight the (lack of) sensitivity of different parameters.
srcreigh 1 days ago [-]
Well, yes, but if k is for example Ω(n) then O(n-k) is also O(1).
IsTom 1 days ago [-]
If k = n - constant it comes out to O(1).
mwkaufma 1 days ago [-]
Every O(n) is O(1) if n = 1. Complexity measures worst-case by-definition, not all cases.
IsTom 1 days ago [-]
It has two parameters and depending on their relation it will act differently, it's reasonable to include this information. It is worst case O(1) when n and k don't differ much.
mwkaufma 1 days ago [-]
You've introduced an idiosyncratic definition of "worst-case" that nobody else uses to redefine proportional cycle-counting as "complexity", so yeah, I guess in your novel terminology that makes sense, but it isn't consistent with any CS textbook.
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/ε).
and of course the reason they do this is because later in Lemma 16.49, they have k = n − (s + 1) − log 1/ε, so that t = O(s + log 1/ε), canceling the n.
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.
jasomill 21 hours ago [-]
So long as f,g: N→M and we have a reasonable definition of the magnitude ‖·‖:M→ℝ, it shouldn't matter what N is, since we can just define
O(f(n)) = O(g(n))
if and only if
sup_n∈N ‖f(n)‖/‖g(n)‖ < ∞.
progval 1 days ago [-]
No, it's not just about cycle counting.
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.
IsTom 1 days ago [-]
What are you talking about? There's a lot of expressions like O(n + k), O(n * k) or O(n * log k) in typical algorithm books (CLRS certainly has them). There's nothing special about O(n - k).
matheist 1 days ago [-]
Saying that l.pop(k) has time complexity O(n-k) implies that popping something at position 5 from the end has bounded (amortized) time cost regardless of the length of the list l, ie even if we let the list grow arbitrarily.
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.
mwkaufma 1 days ago [-]
Complexity measures the worst-case, not the amortized case. If you want to report proportional cycles for more fine-grained per-feedback, fine, report proportional-cycles, but that's not Big-O, so don't use that notation.
jeremyscanvic 1 days ago [-]
Worst case can mean two things. For fixed n, worst list content and worst k, which gives you the less fine-grained O(n). For fixed n and fixed k, worst list content, which gives you the fine-grained O(n - k).
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.
xigoi 15 hours ago [-]
Big O notation has nothing to do with worst or best case. f = O(g) simply means that f is asymptotically bounded by a multiple of g.
gpugreg 2 days ago [-]
Notable pitfalls:
- 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
chronial 1 days ago [-]
Note the footnote for rfind:
> This is the worst case. Reverse searches are O(n) on typical input.
gpugreg 1 days ago [-]
I could have used more precise terminology. rfind is average case O(n + m), worst case O(n * m). Imho the worst case performance is more important than the average case performance, since it tells us whether there is any risk for attacks like Hash DoS, which is the reason why Python's dict hashing had to be changed. https://peps.python.org/pep-0456/
speedstyle 21 hours ago [-]
realloc is frequently O(n), ie CPython can avoid copying and immediately collecting the object but still copy the bytes. It's the same as calling reserve in a loop
emil-lp 1 days ago [-]
They forgot to include GC overhead.
feelamee 1 days ago [-]
how gc influence time complexity? elaborate, pks
emil-lp 1 days ago [-]
Say that you add and remove elements. Perhaps your data structure runs amortized constant time.
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.
slopinthebag 1 days ago [-]
Maybe you need to factor in the GC algorithm when determining big O, since an algorithm which implements some complexity but creates a lot of garbage actually ends up with a worse big O?
Seems like a bit of a stretch to me but possible?
chubot 1 days ago [-]
It seems like that's pretty easy to disprove -- GC time is proportional to allocation time.
(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)
emil-lp 1 days ago [-]
You are assuming GC runs in linear time.
chubot 1 days ago [-]
[dead]
jjgreen 1 days ago [-]
Nice page, but odd that they have O(...) in every row, surely that belongs in the column header
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...
0 - https://www.youtube.com/watch?v=lyDLAutA88s
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.
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.
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.
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
Who is making membership checks against trivially-sized collections in a hot loop?
See, you already made a mistake:
4 is neither the min or max of the range (their actual names are start and stop), and notice how the max is the first argument and the min is the second argumentOf course, the actual implementation of constant time min/max on range would be trivial.
> 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.
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.
O(f(n)) = O(g(n))
if and only if
sup_n∈N ‖f(n)‖/‖g(n)‖ < ∞.
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.
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.
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.
- 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?
(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)