Найти минимум/максимум можно, используя один линейный алгоритм для разных типов ввода: как для списков с числами, так и для строк, так и для списка пар итд:
def min_item(items, *, key=lambda x: x):
min_, *items = items
for item in items:
if key(item) < key(min_):
min_ = item
return min_
Пример:
>>> min_item([2, 1, 3])
1
>>> min_item("aBc")
'B'
>>> min_item([[1,2], [3, 4], [9, 0]], key=lambda x: x[1])
[9, 0]
где синтаксис со звёдочкой, используется, чтобы первый элемент из коллекции достать:
>>> a, *b = [1, 2, 3]
>>> print(a, b)
1 [2, 3]
sorted(items, key=key)[0]
сработало бы для всех представленных случаев, но сортировка, основанная на сравнениях, требует O(n * log n)
операций, поэтому показан простой цикл как пример реализации min()
, используя линейный (O(n)
) алгоритм.
Стандартные min/max функции сложнее представленной min_item()
:
можно передавать несколько аргументов:
>>> min(1, 2, 3)
1
если ввод пустой, то может быть возвращено значение по умолчанию:
>>> min([], default=1)
1
потребляемая память не зависит от количества переданных элементов (в то время как реализация выше, использует O(n)
дополнительной памяти—чем больше ввод, тем больше памяти требуется)
- можно оптимизировать алгоритм, чтобы избежать вызова
key()
несколько раз для одного и того же элемента.
Легко адаптировать min_item()
функцию, чтобы она несколько аргументов поддерживала:
def min_item(first, *args, key=lambda x: x):
if not args: # first is an iterable
first, *args = first
for arg in args:
if key(arg) < key(first):
first = arg
return first
В этом случае, если передан один аргумент (len(args) == 0
и поэтому not args
ветка выполняется), то поведение идентично первому примеру. Если передано несколько позиционных аргументов, то ищется минимум среди них:
>>> min_item(2, 1, 3)
1
>>> min_item([2, 1, 3])
1
>>> min_item("aBc", key=str.lower)
'a'
Чтобы удовлетворить требования к памяти, можно использовать итераторы:
_sentinel = object()
def min(first, *args, key=lambda x: x, default=_sentinel):
if not args: # first is an iterable
args = iter(first)
try:
first = next(args)
except StopIteration: # empty
if default is _sentinel:
raise ValueError("min() arg is an empty sequence") from None
return default
elif default is not _sentinel:
raise TypeError("Cannot specify a default for min() with multiple positional arguments")
min_key = key(first)
for arg in args:
k = key(arg)
if k < min_key:
min_key = k
first = arg
return first
Эта функция ведёт себя как стандартная min()
функция.
_sentinel
используется, чтобы определить был ли передан default
параметр при вызове функции.
key()
функция вызывается только один раз для каждого элемента на входе.
Эта реализация функции min()
поддерживает произвольное (конечное) число входных элементов, не увеличивая потребляемую дополнительную память с ростом ввода.
Пример:
>>> min_(map(len, file)) # длина самой короткой строки в (возможно большом) файле
>>> min_(1, 2, 3)
1
>>> min_(x*x for x in range(-10, 3))
0
>>> min([])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: min() arg is an empty sequence
>>> min([], default=1)
1
Реализация max()
крайне похожа—достаточно <
на >
поменять.