TL;DR
If the input is a NumPy array, see here.
If the input is a sequence:
min() and max() is generally faster than manual looping (unless one uses the key parameter and then it depends on how fast the function call is)- manual looping can be made faster with Python, with performances outperforming two separate calls to
min() and max().
If the input is a non-sequence iterable:
min() and max() cannot be used to the same iterable
- iterable needs to be casted to
list() or tuple() (or one could use itertools.tee(), but as per its documentation, list()/tuple() casting is faster in this case), but has a large memory footprint
- one can use a single looping approach, which can again be accelerated with Cython.
The case with explicit key is not treated here in detail, but an effective adaptation of one of the efficient approaches that can be Cython-ized is reported below:
def extrema_for_with_key(items, key=None):
items = iter(items)
if callable(key):
try:
max_item = min_item = next(items)
max_val = min_val = key(item)
except StopIteration:
return None, None
else:
for item in items:
val = key(item)
if val > max_val:
max_val = val
max_item = item
elif val < min_val:
min_val = val
min_item = item
return max_item, min_item
else:
try:
max_item = min_item = next(items)
except StopIteration:
return None, None
else:
for item in items:
if item > max_item:
max_item = item
elif item < min_item:
min_item = item
return max_item, min_item
Full benchmark here.
Longer answer
While looping in pure Python may be your bottleneck, it is nevertheless true that the problem of finding both the maximum and the minimum can be solved with significantly less steps (less comparisons and less assignments) than two separate calls to max() and min() -- on a randomly distributed sequence of values, and more specifically by traversing the sequence (or iterable) only once.
This may be useful when using the functionality provided by the use of the key parameter, or when the input is an iterator and converting it to a tuple() or list() (or using itertools.tee()) would result in excessive memory consumption.
In addition, such approaches may result in faster execution if it is viable to accelerate the looping via Cython or Numba.
In case the input is not a NumPy array, Cython's acceleration is most effective, while if the input is a NumPy array then Numba's acceleration results in largest speed-up.
Typically, the cost of converting a generic input to a NumPy array is not offset by the speed gain of using Numba.
A discussion for the case of NumPy arrays can be found here.
The base implementation, ignoring the key parameter, is the following (where min_loops() and max_loops() are essentially re-implementation with loops of min() and max()):
def min_loops(seq):
iseq = iter(seq) # ensure iterator
try:
result = next(iseq)
except StopIteration:
return None
else:
for item in iseq:
if item < result:
result = item
return result
def max_loops(seq):
iseq = iter(seq) # ensure iterator
try:
result = next(iseq)
except StopIteration:
return None
else:
for item in iseq:
if item > result:
result = item
return result
def extrema_loops(items):
seq = tuple(items) # required if items is actually an iterable
return max_loops(seq), min_loops(seq)
These can be naïvely combined into a single loop, similarly to OP proposal:
def extrema_for(seq):
iseq = iter(seq)
try:
max_val = min_val = next(iseq)
except StopIteration:
return None, None
else:
for item in iseq:
if item > max_val:
max_val = item
elif item < min_val: # <-- reduces comparisons
min_val = item
return max_val, min_val
where the use of the elif effectively reduces the number of comparisons (and assignments) "on average" (on inputs with randomly distributed values) to 1.5 per element.
The number of assignments can be further decreased by considering two elements "at once" (the number of comparisons is on average 1.5 per element in both cases):
def extrema_for2(seq):
iseq = iter(seq)
try:
max_val = min_val = next(iseq)
except StopIteration:
return None, None
else:
for x, y in zip(iseq, iseq):
if x > y: # reduces assignments
x, y = y, x
if x < min_val:
min_val = x
if y > max_val:
max_val = y
try:
last = next(iseq)
except StopIteration:
pass
else:
if last < min_val:
min_val = x
if last > max_val:
max_val = y
return max_val, min_val
the relative speed of each method greatly depends on the relative speed of each instruction, and alternate implementations of extrema_for2() may be faster.
For example, if the main loop (for x, y in zip(iseq, iseq)) is replaced with a while True: x = next(iseq); y = next(iseq) construct, i.e.:
def extrema_while(seq):
iseq = iter(seq)
try:
max_val = min_val = x = next(iseq)
try:
while True:
x = next(iseq)
y = next(iseq)
if x > y:
x, y = y, x
if x < min_val:
min_val = x
if y > max_val:
max_val = y
except StopIteration:
if x < min_val:
min_val = x
if x > max_val:
max_val = x
return max_val, min_val
except StopIteration:
return None, None
this turns out to be slower in Python BUT faster with Cython acceleration.
These and the following implementations as baseline:
def extrema(seq):
return max(seq), min(seq)
def extrema_iter(items):
seq = tuple(items)
return max(seq), min(seq)
are compared below:
Note that in general:
extrema_while() > extrema_loops() > extrema_for() > extrema_for2() (this is due to the expensive calls to next())extrema_loops_cy() > extrema_for_cy() > extrema_for2_cy() > extrema_while_cy()extrema_loops_cy() is actually slower than extrema().
The functions have Cython counterpats (with _cy suffix) and are essentially the same code except for def replaced with cpdef, e.g.:
%%cython -c-O3 -c-march=native -a
#cython: language_level=3, boundscheck=False, wraparound=False, initializedcheck=False, cdivision=True, infer_types=True
cpdef extrema_while_cy(seq):
items = iter(seq)
try:
max_val = min_val = x = next(items)
try:
while True:
x = next(items)
y = next(items)
if x > y:
x, y = y, x
if x < min_val:
min_val = x
if y > max_val:
max_val = y
except StopIteration:
if x < min_val:
min_val = x
if x > max_val:
max_val = x
return max_val, min_val
except StopIteration:
return None, None
Full benchmark here.
