#python #python-3.x #list #function #performance
Вопрос:
Давайте воспользуемся простым примером: скажем, у меня есть список списков
ll = [[1, 2], [1, 3], [2, 3], [1, 2, 3], [2, 3, 4]]
и я хочу найти все самые длинные списки, что означает все списки, которые максимизируют len функцию. Конечно, мы можем это сделать
def func(x):
return len(x)
maxlen = func(max(ll, key=lambda x: func(x)))
res = [l for l in ll if func(l) == maxlen]
print(res)
Выход
[[1, 2, 3], [2, 3, 4]]
Но мне интересно, есть ли более эффективный способ сделать это, особенно когда функция очень дорогая или список очень длинный. Есть какие-нибудь предложения?
Комментарии:
1. это
O(n)значит , что лучше уже быть не может. Возможно, есть немного более быстрая альтернатива, например , вам она не нужнаfunc(x), просто замените ее прямоlen(x)сейчас, но в остальном я так не думаю.2. @Mahrkeenerh, не так
O(2n)ли ?3. Вы должны проанализировать каждый элемент в списке, чтобы убедиться, что вы не пропустите потенциальный maximum_element, поэтому, как сказал @Mahrkeenerh, это не может быть лучше, чем
O(n)4. Константы игнорируются в обозначении O. Вы могли бы сделать это немного быстрее, если создадите свой выходной список, найдя максимальное значение, но это почти то же самое
5. как предлагается в ответах ниже, да — создайте свой список, найдя максимальный элемент, или кэшируйте результаты, поэтому, даже если это дорого, второй проход будет НАМНОГО быстрее.
Ответ №1:
С точки зрения компьютерных наук/алгоритмов, это очень классическая проблема «сокращения».
итак, псевдокод. Честно говоря, это очень просто.
metric():= a mapping from elements to non-negative numbers
winner = []
maxmetric = 0
for element in ll:
if metric(element) larger than maxmetric:
winner = [ element ]
maxmetric = metric(element)
else if metric(element) equal to maxmetric:
append element to winner
Комментарии:
1. Еще более универсальным решением является установка
maxmetric = metric(first element of ll), на всякий случай, если метрика способна возвращать отрицательные числа.2. это зависит от того, насколько дорог этот показатель, но да, это один из способов сделать это. (показатели в математическом смысле этого слова: неотрицательные по определению)
Ответ №2:
когда функция очень дорогая
Обратите внимание, что вы выполняете вычисления func(x) для каждого элемента дважды, сначала там
maxlen = func(max(ll, key=lambda x: func(x)))
тогда там
res = [l for l in ll if func(l) == maxlen]
поэтому было бы полезно сохранить то, что уже было вычислено. functools.lru_cache позвольте этому легко просто заменить
def func(x):
return len(x)
с помощью
import functools
@functools.lru_cache(maxsize=None)
def func(x):
return len(x)
Однако будьте осторожны, поскольку из-за способа хранения данных аргументы(ы) должны быть хэшируемыми, поэтому в вашем примере вам сначала потребуется преобразовать список, например, в tuple s, т. е.
ll = [(1, 2), (1, 3), (2, 3), (1, 2, 3), (2, 3, 4)]
См. Описание в документах для дальнейшего обсуждения
Ответ №3:
Не нормально использовать dictionary , как показано ниже, (это O(n) )
ll = [[1, 2], [1, 3], [2, 3], [1, 2, 3], [2, 3, 4]]
from collections import defaultdict
dct = defaultdict(list)
for l in ll:
dct[len(l)].append(l)
dct[max(dct)]
Выход:
[[1, 2, 3], [2, 3, 4]]
>>> dct
defaultdict(list, {2: [[1, 2], [1, 3], [2, 3]], 3: [[1, 2, 3], [2, 3, 4]]})
ИЛИ используйте setdefault и без defaultdict , как показано ниже:
ll = [[1, 2], [1, 3], [2, 3], [1, 2, 3], [2, 3, 4]]
dct = {}
for l in ll:
dct.setdefault(len(l), []).append(l)
Выход:
>>> dct
{2: [[1, 2], [1, 3], [2, 3]], 3: [[1, 2, 3], [2, 3, 4]]}