Являются ли списки и функциональные функции быстрее, чем «для циклов»?

156

С точки зрения производительности в Python, список постижение, или функции , такие как map(), filter()и reduce()быстрее , чем цикл? Почему, технически, они работают на скорости C , а цикл for работает на скорости виртуальной машины python ?

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

Эриксон Виллианс
источник

Ответы:

147

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

Понимание списка обычно немного быстрее, чем точно эквивалентный forцикл (который фактически строит список), скорее всего потому, что ему не нужно искать список и его appendметод на каждой итерации. Однако, понимание списка все еще делает цикл уровня байт-кода:

>>> dis.dis(<the code object for `[x for x in range(10)]`>)
 1           0 BUILD_LIST               0
             3 LOAD_FAST                0 (.0)
       >>    6 FOR_ITER                12 (to 21)
             9 STORE_FAST               1 (x)
            12 LOAD_FAST                1 (x)
            15 LIST_APPEND              2
            18 JUMP_ABSOLUTE            6
       >>   21 RETURN_VALUE

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

Что касается функций обработки функциональных списков: хотя они написаны на C и, вероятно, превосходят эквивалентные функции, написанные на Python, они не обязательно являются самым быстрым вариантом. Некоторое ускорение ожидается, если функция также написана на C. Но в большинстве случаев с использованием lambda(или другой функции Python) затрат на повторную настройку стековых фреймов Python и т. Д. Расходуется любая экономия. Простое выполнение той же самой работы in-line, без вызовов функций (например, понимание списка вместо mapили filter) часто немного быстрее.

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

Скорее всего, если подобный код недостаточно быстр, когда он написан на хорошем неоптимизированном Python, никакая микрооптимизация на уровне Python не сделает его достаточно быстрым, и вы должны начать думать о переходе на С. Микрооптимизации часто могут значительно ускорить код Python, для этого существует низкий (в абсолютном выражении) предел. Более того, даже до того, как вы достигнете этого потолка, становится просто более экономически эффективным (ускорение на 15% против ускорения на 300% с тем же усилием), чтобы прикусить пулю и написать немного C.


источник
25

Если вы проверите информацию на python.org , вы можете увидеть это резюме:

Version Time (seconds)
Basic loop 3.47
Eliminate dots 2.45
Local variable & no dots 1.79
Using map function 0.54

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

Я также настоятельно рекомендую вам рассчитать время, используя timeit . В конце дня может возникнуть ситуация, когда, например, вам может понадобиться выйти из forцикла при выполнении условия. Потенциально это может быть быстрее, чем узнать результат по телефону map.

Энтони Конг
источник
17
Хотя эта страница хорошо читается и частично связана, просто цитирование этих цифр не помогает, возможно, даже вводит в заблуждение.
1
Это не указывает на то, что вы выбрали. Относительная производительность сильно зависит от того, что находится в цикле / listcomp / map.
user2357112 поддерживает Monica
@delnan Я согласен. Я изменил свой ответ, чтобы убедить OP прочитать документацию, чтобы понять разницу в производительности.
Энтони Конг
@ user2357112 Вы должны прочитать вики-страницу, на которую я ссылался для контекста. Я разместил это для справки OP.
Энтони Конг
13

Вы спрашиваете конкретно о map(), filter()и reduce(), но я предполагаю, что вы хотите знать о функциональном программировании в целом. Испытав это сам на проблеме вычисления расстояний между всеми точками в наборе точек, функциональное программирование (с использованием starmapфункции из встроенного itertoolsмодуля) оказалось немного медленнее, чем циклы for (занимая в 1,25 раза больше времени, в факт). Вот пример кода, который я использовал:

import itertools, time, math, random

class Point:
    def __init__(self,x,y):
        self.x, self.y = x, y

point_set = (Point(0, 0), Point(0, 1), Point(0, 2), Point(0, 3))
n_points = 100
pick_val = lambda : 10 * random.random() - 5
large_set = [Point(pick_val(), pick_val()) for _ in range(n_points)]
    # the distance function
f_dist = lambda x0, x1, y0, y1: math.sqrt((x0 - x1) ** 2 + (y0 - y1) ** 2)
    # go through each point, get its distance from all remaining points 
f_pos = lambda p1, p2: (p1.x, p2.x, p1.y, p2.y)

extract_dists = lambda x: itertools.starmap(f_dist, 
                          itertools.starmap(f_pos, 
                          itertools.combinations(x, 2)))

print('Distances:', list(extract_dists(point_set)))

t0_f = time.time()
list(extract_dists(large_set))
dt_f = time.time() - t0_f

Функциональная версия быстрее процедурной?

def extract_dists_procedural(pts):
    n_pts = len(pts)
    l = []    
    for k_p1 in range(n_pts - 1):
        for k_p2 in range(k_p1, n_pts):
            l.append((pts[k_p1].x - pts[k_p2].x) ** 2 +
                     (pts[k_p1].y - pts[k_p2].y) ** 2)
    return l

t0_p = time.time()
list(extract_dists_procedural(large_set)) 
    # using list() on the assumption that
    # it eats up as much time as in the functional version

dt_p = time.time() - t0_p

f_vs_p = dt_p / dt_f
if f_vs_p >= 1.0:
    print('Time benefit of functional progamming:', f_vs_p, 
          'times as fast for', n_points, 'points')
else:
    print('Time penalty of functional programming:', 1 / f_vs_p, 
          'times as slow for', n_points, 'points')
andreipmbcn
источник
2
Похоже, довольно запутанный способ ответить на этот вопрос. Вы можете сократить это так, чтобы это имело смысл?
Аарон Холл
2
@AaronHall Я нахожу ответ andreipmbcn довольно интересным, потому что это нетривиальный пример. Код, с которым мы можем играть.
Энтони Конг
@AaronHall, вы хотите, чтобы я отредактировал текстовый абзац, чтобы он звучал более четко и понятно, или вы хотите, чтобы я отредактировал код?
andreipmbcn
9

Я написал простой скрипт, который проверяет скорость, и вот что я узнал. На самом деле для цикла было самым быстрым в моем случае. Это действительно удивило меня, посмотрите ниже (вычислялась сумма квадратов).

from functools import reduce
import datetime


def time_it(func, numbers, *args):
    start_t = datetime.datetime.now()
    for i in range(numbers):
        func(args[0])
    print (datetime.datetime.now()-start_t)

def square_sum1(numbers):
    return reduce(lambda sum, next: sum+next**2, numbers, 0)


def square_sum2(numbers):
    a = 0
    for i in numbers:
        i = i**2
        a += i
    return a

def square_sum3(numbers):
    sqrt = lambda x: x**2
    return sum(map(sqrt, numbers))

def square_sum4(numbers):
    return(sum([int(i)**2 for i in numbers]))


time_it(square_sum1, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum2, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum3, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum4, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
0:00:00.302000 #Reduce
0:00:00.144000 #For loop
0:00:00.318000 #Map
0:00:00.390000 #List comprehension
alphiii
источник
С питоном 3.6.1 различия не так велики; Сократить и Карта снизится до 0,24 и список понимания до 0,29. Для выше, на 0,18.
jjmerelo
Устранение intin square_sum4также делает его немного быстрее и чуть медленнее, чем цикл for.
jjmerelo
6

Я изменил код @ Алисы и использовал, cProfileчтобы показать, почему понимание списка происходит быстрее:

from functools import reduce
import datetime

def reduce_(numbers):
    return reduce(lambda sum, next: sum + next * next, numbers, 0)

def for_loop(numbers):
    a = []
    for i in numbers:
        a.append(i*2)
    a = sum(a)
    return a

def map_(numbers):
    sqrt = lambda x: x*x
    return sum(map(sqrt, numbers))

def list_comp(numbers):
    return(sum([i*i for i in numbers]))

funcs = [
        reduce_,
        for_loop,
        map_,
        list_comp
        ]

if __name__ == "__main__":
    # [1, 2, 5, 3, 1, 2, 5, 3]
    import cProfile
    for f in funcs:
        print('=' * 25)
        print("Profiling:", f.__name__)
        print('=' * 25)
        pr = cProfile.Profile()
        for i in range(10**6):
            pr.runcall(f, [1, 2, 5, 3, 1, 2, 5, 3])
        pr.create_stats()
        pr.print_stats()

Вот результаты:

=========================
Profiling: reduce_
=========================
         11000000 function calls in 1.501 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1000000    0.162    0.000    1.473    0.000 profiling.py:4(reduce_)
  8000000    0.461    0.000    0.461    0.000 profiling.py:5(<lambda>)
  1000000    0.850    0.000    1.311    0.000 {built-in method _functools.reduce}
  1000000    0.028    0.000    0.028    0.000 {method 'disable' of '_lsprof.Profiler' objects}


=========================
Profiling: for_loop
=========================
         11000000 function calls in 1.372 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1000000    0.879    0.000    1.344    0.000 profiling.py:7(for_loop)
  1000000    0.145    0.000    0.145    0.000 {built-in method builtins.sum}
  8000000    0.320    0.000    0.320    0.000 {method 'append' of 'list' objects}
  1000000    0.027    0.000    0.027    0.000 {method 'disable' of '_lsprof.Profiler' objects}


=========================
Profiling: map_
=========================
         11000000 function calls in 1.470 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1000000    0.264    0.000    1.442    0.000 profiling.py:14(map_)
  8000000    0.387    0.000    0.387    0.000 profiling.py:15(<lambda>)
  1000000    0.791    0.000    1.178    0.000 {built-in method builtins.sum}
  1000000    0.028    0.000    0.028    0.000 {method 'disable' of '_lsprof.Profiler' objects}


=========================
Profiling: list_comp
=========================
         4000000 function calls in 0.737 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1000000    0.318    0.000    0.709    0.000 profiling.py:18(list_comp)
  1000000    0.261    0.000    0.261    0.000 profiling.py:19(<listcomp>)
  1000000    0.131    0.000    0.131    0.000 {built-in method builtins.sum}
  1000000    0.027    0.000    0.027    0.000 {method 'disable' of '_lsprof.Profiler' objects}

ПО МОЕМУ МНЕНИЮ:

  • reduceи mapв целом довольно медленно. Мало того, что использование возвращаемых sumитераторов mapявляется медленным, по сравнению sumсо списком
  • for_loop использует append, который, конечно, в некоторой степени медленный
  • понимание списка не только потратило меньше времени на создание списка, но и делает его sumнамного быстрее, в отличие отmap
tjysdsg
источник
5

Добавив поворот к ответу Alphii , фактически цикл for будет вторым лучшим и примерно в 6 раз медленнее, чемmap

from functools import reduce
import datetime


def time_it(func, numbers, *args):
    start_t = datetime.datetime.now()
    for i in range(numbers):
        func(args[0])
    print (datetime.datetime.now()-start_t)

def square_sum1(numbers):
    return reduce(lambda sum, next: sum+next**2, numbers, 0)


def square_sum2(numbers):
    a = 0
    for i in numbers:
        a += i**2
    return a

def square_sum3(numbers):
    a = 0
    map(lambda x: a+x**2, numbers)
    return a

def square_sum4(numbers):
    a = 0
    return [a+i**2 for i in numbers]

time_it(square_sum1, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum2, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum3, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum4, 100000, [1, 2, 5, 3, 1, 2, 5, 3])

Основные изменения были направлены на устранение медленных sumзвонков, а также, возможно, ненужных int()в последнем случае. Помещение цикла for и map в одни и те же термины делает это фактически фактом. Помните, что лямбды являются функциональными концепциями и теоретически не должны иметь побочных эффектов, но, ну, у них могут быть побочные эффекты, такие как добавление к a. Результаты в этом случае с Python 3.6.1, Ubuntu 14.04, Intel® Core Core ™ TM i7-4770 CPU @ 3.40 ГГц

0:00:00.257703 #Reduce
0:00:00.184898 #For loop
0:00:00.031718 #Map
0:00:00.212699 #List comprehension
jjmerelo
источник
2
square_sum3 и square_sum4 неверны. Они не дадут сумму. Ответ ниже от @alisca chen на самом деле правильный.
ШихарДуа
3

Мне удалось изменить часть кода @ alpiii и обнаружил, что понимание списка немного быстрее, чем для цикла. Это может быть вызвано тем int(), что это несправедливо между пониманием списка и циклом for.

from functools import reduce
import datetime

def time_it(func, numbers, *args):
    start_t = datetime.datetime.now()
    for i in range(numbers):
        func(args[0])
    print (datetime.datetime.now()-start_t)

def square_sum1(numbers):
    return reduce(lambda sum, next: sum+next*next, numbers, 0)

def square_sum2(numbers):
    a = []
    for i in numbers:
        a.append(i*2)
    a = sum(a)
    return a

def square_sum3(numbers):
    sqrt = lambda x: x*x
    return sum(map(sqrt, numbers))

def square_sum4(numbers):
    return(sum([i*i for i in numbers]))

time_it(square_sum1, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum2, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum3, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum4, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
0:00:00.101122 #Reduce

0:00:00.089216 #For loop

0:00:00.101532 #Map

0:00:00.068916 #List comprehension
Алиска Чен
источник