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?

xnx
  • 24,509
  • 11
  • 70
  • 109
  • 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. – cs95 Mar 05 '19 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). – xnx Mar 05 '19 at 10:21

1 Answers1

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.

cs95
  • 379,657
  • 97
  • 704
  • 746