лямбда в сравнении со списком производительности - PullRequest
17 голосов
/ 27 октября 2009

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

import time

S=[x for x in range(1000000)]
T=[y**2 for y in range(300)]
#
#
time1 = time.time()
N=[x for x in S for y in T if x==y]
time2 = time.time()
print 'time diff [x for x in S for y in T if x==y]=', time2-time1
#print N
#
#
time1 = time.time()
N=filter(lambda x:x in S,T)
time2 = time.time()
print 'time diff filter(lambda x:x in S,T)=', time2-time1
#print N
#
#
#http://snipt.net/voyeg3r/python-intersect-lists/
time1 = time.time()
N = [val for val in S if val in T]
time2 = time.time()
print 'time diff [val for val in S if val in T]=', time2-time1
#print N
#
#
time1 = time.time()
N= list(set(S) & set(T))
time2 = time.time()
print 'time diff list(set(S) & set(T))=', time2-time1
#print N  #the results will be unordered as compared to the other ways!!!
#
#
time1 = time.time()
N=[]
for x in S:
    for y in T:
        if x==y:
            N.append(x)
time2 = time.time()
print 'time diff using traditional for loop', time2-time1
#print N

Они все печатают одно и то же N, поэтому я прокомментировал, что вывод stmt (кроме последнего способа, которым он неупорядочен), но результирующие различия во времени были интересны при повторных тестах, как видно в этом одном примере:

time diff [x for x in S for y in T if x==y]= 54.875
time diff filter(lambda x:x in S,T)= 0.391000032425
time diff [val for val in S if val in T]= 12.6089999676
time diff list(set(S) & set(T))= 0.125
time diff using traditional for loop 54.7970001698

Так что, хотя мне кажется, что списки в целом легче читать, в этом примере, похоже, есть некоторые проблемы с производительностью.

Итак, два вопроса:

  1. Почему лямбда и т. Д. Отталкиваются?

  2. Для способов понимания списка, есть ли более эффективная реализация и как вы ЗНАЕТЕ, что она более эффективна без тестирования? Я имею в виду, что лямбда / карта / фильтр должна была быть менее эффективной из-за дополнительных вызовов функций, но, похоже, она более эффективна.

Пол

Ответы [ 10 ]

30 голосов
/ 27 октября 2009

Ваши тесты делают очень разные вещи. С S = 1M элементов и T = 300:

[x for x in S for y in T if x==y]= 54.875

Эта опция делает 300M сравнения на равенство.

filter(lambda x:x in S,T)= 0.391000032425

Эта опция выполняет 300 линейных поисков по S.

[val for val in S if val in T]= 12.6089999676

Эта опция выполняет 1М линейный поиск по T.

list(set(S) & set(T))= 0.125

Эта опция делает две конструкции множеств и одно пересечение множеств.


Различия в производительности между этими параметрами гораздо больше связаны с алгоритмами, которые использует каждый из них, , а не , чем с любой разницей между списками и lambda.

23 голосов
/ 27 октября 2009

Когда я исправляю ваш код так, чтобы понимание списка и вызов filter фактически выполняли одну и ту же работу, вещи сильно менялись:

import time

S=[x for x in range(1000000)]
T=[y**2 for y in range(300)]
#
#
time1 = time.time()
N=[x for x in T if x in S]
time2 = time.time()
print 'time diff [x for x in T if x in S]=', time2-time1
#print N
#
#
time1 = time.time()
N=filter(lambda x:x in S,T)
time2 = time.time()
print 'time diff filter(lambda x:x in S,T)=', time2-time1
#print N

Тогда вывод больше похож на:

time diff [x for x in T if x in S]= 0.414485931396
time diff filter(lambda x:x in S,T)= 0.466315984726

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

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

18 голосов
/ 28 октября 2009

В: Почему лямбда и т. Д. Отталкиваются?

A: списочные выражения и выражения генератора обычно считаются хорошим сочетанием мощности и читабельности. Чистый стиль функционального программирования, в котором вы используете map(), reduce() и filter() с функциями (часто lambda функциями), считается не совсем понятным. Кроме того, в Python добавлены встроенные функции, которые прекрасно справляются со всеми основными видами использования reduce().

Предположим, вы хотите подвести итог списка. Вот два способа сделать это.

lst = range(10)
print reduce(lambda x, y: x + y, lst)

print sum(lst)

Зарегистрируйтесь, чтобы решить эту проблему как фанат sum(), а не фанат reduce(). Вот еще одна, похожая проблема:

lst = range(10)
print reduce(lambda x, y: bool(x or y), lst)

print any(lst)

Решение any() не только легче понять, но и намного быстрее; он имеет оценку короткого замыкания, так что он прекратит оценку, как только найдет какое-либо истинное значение. reduce() должен провернуть весь список. Эта разница в производительности была бы существенной, если бы список составлял миллион элементов, а первый элемент оценивался как истинный. Кстати, any() был добавлен в Python 2.5; если у вас его нет, вот версия для старых версий Python:

def any(iterable):
    for x in iterable:
        if x:
            return True
    return False

Предположим, вы хотите составить список квадратов четных чисел из некоторого списка.

lst = range(10)
print map(lambda x: x**2, filter(lambda x: x % 2 == 0, lst))

print [x**2 for x in lst if x % 2 == 0]

Теперь предположим, что вы хотите сложить этот список квадратов.

lst = range(10)
print sum(map(lambda x: x**2, filter(lambda x: x % 2 == 0, lst)))

# list comprehension version of the above
print sum([x**2 for x in lst if x % 2 == 0])

# generator expression version; note the lack of '[' and ']'
print sum(x**2 for x in lst if x % 2 == 0)

Генераторное выражение на самом деле просто возвращает итеративный объект. sum() берет итерируемое и извлекает из него значения, одно за другим, суммируя по ходу, пока все значения не будут использованы. Это самый эффективный способ решить эту проблему в Python. Напротив, решение map() и эквивалентное решение с пониманием списка внутри вызова sum() должны сначала создать список; этот список затем передается в sum(), используется один раз и отбрасывается. Время на создание списка и последующее его удаление просто напрасно. (РЕДАКТИРОВАТЬ: и обратите внимание, что версия с map и filter должна создавать два списка, один из которых filter, а другой - map; из обоих списков отбрасываются.) (РЕДАКТИРОВАТЬ: Но в Python 3.0 и новее, map () и filter () теперь оба «ленивые» и создают итератор вместо списка, поэтому эта точка менее верна, чем раньше. в Python 2.x вы могли использовать itertools.imap () и itertools.ifilter () для отображения и фильтра на основе итераторов. Но я продолжаю предпочитать решения для выражений генератора перед любыми решениями для карт / фильтров.)

Сочетая map(), filter() и reduce() в сочетании с lambda функциями, вы можете делать много мощных вещей. Но у Python есть идиоматические способы решения одних и тех же проблем, которые одновременно лучше работают и легче читаются и понимаются.

6 голосов
/ 27 октября 2009

Многие люди уже отмечали, что вы сравниваете яблоки с апельсинами и т. Д., И т. Д. Но я думаю, что никто не показал, как провести действительно простое сравнение - составление списков по сравнению с картой плюс лямбда, и ничто другое не мешает - - и это может быть:

$ python -mtimeit -s'L=range(1000)' 'map(lambda x: x+1, L)'
1000 loops, best of 3: 328 usec per loop
$ python -mtimeit -s'L=range(1000)' '[x+1 for x in L]'
10000 loops, best of 3: 129 usec per loop

Здесь вы очень четко видите стоимость лямбды - около 200 микросекунд, которая в случае достаточно простой операции, такой как эта, затопляет саму операцию.

Числа очень похожи на фильтр, конечно, поскольку проблема в не фильтре или карте, а в самой лямбде:

$ python -mtimeit -s'L=range(1000)' '[x for x in L if not x%7]'
10000 loops, best of 3: 162 usec per loop
$ python -mtimeit -s'L=range(1000)' 'filter(lambda x: not x%7, L)'
1000 loops, best of 3: 334 usec per loop

Без сомнения, тот факт, что лямбда может быть менее ясной, или ее странная связь со Спартой (у спартанцев была Лямбда, для «Lakedaimon», нарисованная на их щитах - это говорит о том, что лямбда довольно диктаторская и кровавая ;-) по крайней мере, столько же, что и его медленное выпадение из моды, так и его производительность. Но последние вполне реальны.

4 голосов
/ 27 октября 2009

Прежде всего, протестируйте так:

import timeit

S=[x for x in range(10000)]
T=[y**2 for y in range(30)]

print "v1", timeit.Timer('[x for x in S for y in T if x==y]',
             'from __main__ import S,T').timeit(100)
print "v2", timeit.Timer('filter(lambda x:x in S,T)',
             'from __main__ import S,T').timeit(100)
print "v3", timeit.Timer('[val for val in T if val in S]',
             'from __main__ import S,T').timeit(100)
print "v4", timeit.Timer('list(set(S) & set(T))',
             'from __main__ import S,T').timeit(100)

И каждый раз, когда вы тестируете, вы делаете разные вещи. Когда вы переписываете список-понимание, например, как

[val for val in T if val in S]

производительность будет на уровне конструкции 'лямбда / фильтр'.

2 голосов
/ 27 октября 2009

Наборы - правильное решение для этого. Однако попробуйте поменять местами S и T и посмотрите, сколько времени это займет!

filter(lambda x:x in T,S)

$ python -m timeit -s'S=[x for x in range(1000000)];T=[y**2 for y in range(300)]' 'filter(lambda x:x in S,T)'
10 loops, best of 3: 485 msec per loop
$ python -m timeit -r1 -n1 -s'S=[x for x in range(1000000)];T=[y**2 for y in range(300)]' 'filter(lambda x:x in T,S)'
1 loops, best of 1: 19.6 sec per loop

Итак, вы видите, что порядок S и T весьма важен

Изменение порядка понимания списка в соответствии с фильтром дает

$ python -m timeit  -s'S=[x for x in range(1000000)];T=[y**2 for y in range(300)]' '[x for x in T if x in S]'
10 loops, best of 3: 441 msec per loop

Так что, если на самом деле понимание списка немного быстрее, чем лямбда на моем компьютере

1 голос
/ 27 октября 2009

Ваше профилирование выполнено неправильно. Посмотрите модуль timeit и попробуйте снова.

lambda определяет анонимные функции. Их главная проблема заключается в том, что многие люди не знают всей библиотеки Python и используют их для повторной реализации функций, которые уже есть в модуле operator, functools и т. Д. (И намного быстрее).

Понимание списка не имеет ничего общего с lambda. Они эквивалентны стандартным filter и map функциям из функциональных языков. LC предпочтительны, потому что они также могут использоваться в качестве генераторов, не говоря уже о читабельности.

1 голос
/ 27 октября 2009

Ваше понимание списка и лямбда делают разные вещи, понимание списка, соответствующее лямбде, будет [val for val in T if val in S].

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

Попробуйте сделать это с меньшим телом цикла и большими циклами, например, сделайте T набором и итерируйте по S. В этом случае на моем компьютере понимание списка почти в два раза быстрее.

0 голосов
/ 27 октября 2009

Понимание списка может иметь большее значение, если вам придется обрабатывать отфильтрованные результаты. В вашем случае вы просто строите список, но если вам нужно было сделать что-то вроде этого:

n = [f(i) for i in S if some_condition(i)]

вы получите выгоду от оптимизации LC по этому:

n = map(f, filter(some_condition(i), S))

просто потому, что последний должен составить промежуточный список (или кортеж, или строку, в зависимости от природы S). Как следствие вы также заметите различное влияние на память, используемую каждым методом, LC будет оставаться ниже.

Лямбда сама по себе не имеет значения.

0 голосов
/ 27 октября 2009

Это довольно быстро:

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x: 
            hi = mid
        else:
            return mid
    return -1

time1 = time.time()
N = [x for x in T if binary_search(S, x) >= 0]
time2 = time.time()
print 'time diff binary search=', time2-time1

Просто: меньше сравнений, меньше времени.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...