2

As this popular question explains, range objects in Python 3 are clever enough to be able to test efficiently for membership:

In [1]: 1000000000000000 in range(1000000000000001)
Out[1]: True    # answer returned very quickly

However, the same is not true for the evaluation of a range's maximum and minimum values with max and min, which seems to iterate over the entire sequence to find these values:

In [2]: max(range(1000000000000001))   # don't do this
...

It would be trivial to implement these functions efficiently for range objects, so why hasn't it been done? Is there some implementation detail or edge case I am missing?

Improve this question
2
  • How does max know that the sequence is sorted? max does not defer to dunder methods, it is a dumb O(n) algorithm that simply iterates over the sequence as given. Commented Mar 5, 2019 at 10:19
  • 1
    Then that would seem to be the answer: in and len defer to dunder methods that can be overridden, max and min do not (and I suppose making them so would be an implementation change too far for this use-case). Commented Mar 5, 2019 at 10:21

1 Answer 1

Reset to default
2

max is takes the sequence as given, making no assumptions about the type. The sequence is simply iterated over in O(n) time, regardless of whether it is a range object, a list, or a generator.

Some other operators and functions defer to dunder methods which then compute the result. In the case of range, in calls the __contains__ dunder method, which then computes whether low <= item < high, basically. So it is O(1) in python3.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.