4 ms·

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

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 1mo ago
Because the use case is very niche and nobody optimized it yet. https://github.com/python/cpython/issues/135824#issuecomment-2994405973 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.
- zahlman 1mo 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 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 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 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/ https://zahlman.github.io/posts/a-brief-annotation/ [2]: see also my later post there, which went ignored
  - jonathrg 1mo ago
    It's not an optimization if it pessimizes almost all usage by adding a check for the dunder
    - zahlman 1mo 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 1mo 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 1mo ago
  4 is the min of the range (stop (1 here) is never included (by definition. Ask Dijkstra why))
  - zahlman 1mo 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.

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 1mo ago

Because the use case is very niche and nobody optimized it yet. https://github.com/python/cpython/issues/135824#issuecomment-2994405973 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.

zahlman 1mo 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 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 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 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/ https://zahlman.github.io/posts/a-brief-annotation/ [2]: see also my later post there, which went ignored
- jonathrg 1mo ago
  It's not an optimization if it pessimizes almost all usage by adding a check for the dunder
  - zahlman 1mo 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 1mo 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 1mo ago
4 is the min of the range (stop (1 here) is never included (by definition. Ask Dijkstra why))
- zahlman 1mo 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.