Понимание списка в Python: эффективный выбор в списке

Question

Предположим, у меня есть список элементов, и я хочу выбрать только некоторые из них в соответствии с определенной функцией (например, расстояние до другого элемента).

Я хочу получить в результате список кортежей с указанием расстояния и элемента. Итак, я написал следующий код

result = [ ( myFunction(C), C) for C in originalList if myFunction(C) < limit ]

Но myFunction - это очень трудоемкая функция, а originalList довольно большая. Таким образом, myFunction будет вызываться дважды для каждого выбранного элемента.

Итак, есть ли способ избежать этого?

У меня есть две другие возможности, но они не так хороши:

1. первый, это создать нефильтрованный список

   unfiltered = [ (myFunction(C),C) for C in originalList ]
   

   и затем сортировать

   result = [ (dist,C) for dist,C in unfiltered if dist < limit ]
   

   но в этом случае я дублирую свой originalList и тратить немного памяти (список может быть довольно большим - больше 10 000 элементов)

2. второй хитрый и не очень питонический, но эффективный (лучшее, что мы можем сделать, так как функция должна оцениваться один раз для каждого элемента). myFunction хранит последний
   привести к глобальной переменной (например, lastResult), и это значение повторно используется в Понимание списка

   result = [ (lastResult,C) for C in originalList if myFunction(C) < limit ]
   

У вас есть идея получше, эффективным и питонским способом ??

Спасибо за ваши ответы.

Answer 1

Конечно, разница между следующими двумя:

[f(x) for x in list]

и это:

(f(x) for x in list)

заключается в том, что первый сгенерирует список в памяти, а второй - новый генератор с отложенной оценкой.

Итак, вместо этого просто напишите «нефильтрованный» список как генератор. Вот ваш код с встроенным генератором:

def myFunction(x):
    print("called for: " + str(x))
    return x * x

originalList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
limit = 10
result =   [C2 for C2 in ((myFunction(C), C) for C in originalList) if C2[0] < limit]
# result = [C2 for C2 in [(myFunction(C), C) for C in originalList] if C2[0] < limit]

Обратите внимание, что вы не увидите отличий в распечатке от двух, но если посмотреть на использование памяти, второе закомментированное утверждение будет использовать больше памяти.

Чтобы внести простые изменения в свой код в своем вопросе, перепишите нефильтрованное, как это:

unfiltered = [ (myFunction(C),C) for C in originalList ]
             ^                                         ^
             +---------- change these to (..) ---------+
                                 |
                                 v
unfiltered = ( (myFunction(C),C) for C in originalList )

Answer 2

Просто заранее вычислите расстояния и затем отфильтруйте результаты:

with_distances = ((myFunction(C), C) for C in originalList)
result = [C for C in with_distances if C[0] < limit]

Примечание: вместо создания нового списка я использую выражение генератора для построения пар расстояние / элемент.

Answer 3

Не используйте понимание списка; нормальный цикл в порядке здесь.

Answer 4

У Лассе В. Карлсена отличный ответ на ваш вопрос.

Если ваше расстояние вычисляется медленно, я думаю, ваши элементы - это полилинии или что-то в этом роде, верно?

Есть много способов сделать это быстрее:

• Если расстояние между ограничивающими прямоугольниками объектов> X, то из этого следует, что расстояние между этими объектами> X. Поэтому вам нужно только вычислить расстояние между ограничивающими прямоугольниками.

• Если вы хотите, чтобы все объекты, которые находятся на расстоянии меньше X от объекта А, потенциальные совпадения есть только те объекты, чья ограничительная рамка пересекает ограничивающую рамку А, увеличенную на X.

Используя вторую точку, вы, вероятно, можете отбросить множество совпадений кандидатов и выполнять медленные вычисления только при необходимости.

Ограничивающие рамки должны быть кэшированы заранее.

Если у вас действительно много объектов, вы также можете использовать разбиение пространства ...

Или выпуклые огибающие, если вы находитесь в 3D

Answer 5

Некоторые опции:

• Использование памятка
• Используйте нормаль для цикла
• Создайте нефильтрованный список, затем отфильтруйте его (ваш вариант 1). «Потраченная впустую» память будет быстро восстановлена ​​GC - вам не о чем беспокоиться.

Answer 6

Что не так с вариантом 1?

"продублируйте мой оригинальный список и потратьте немного памяти (список может быть довольно большим - более 10000 элементов)"

10 000 элементов - это всего лишь 10 000 указателей на кортежи, которые указывают на существующие объекты. Подумайте 160К или около того памяти. Вряд ли стоит говорить.

Answer 7

Вместо того, чтобы использовать глобальную переменную, как в вашем варианте 2, вы можете полагаться на тот факт, что в Python параметры передаются объектом, то есть объект, который передается в вашу функцию myFunction, является тем же объект как тот, что в списке (это не то же самое, что вызов по ссылке, но он достаточно близок).

Итак, если ваша функция myFunction установила атрибут для объекта, скажем, _result, вы можете выполнить фильтрацию по этому атрибуту:

result = [(_result, C) for C in originalList if myFunction(C) < limit]

и ваша функция myFunction может выглядеть следующим образом:

def myFunction(obj):
    obj._result = ... calculation ....
    return obj._result