Czy składanie list i funkcje funkcjonalne są szybsze niż „pętle for”?

Pod względem wydajności w Pythonie jest lista-zrozumienie, czy funkcje podoba map(), filter()i reduce()szybciej niż pętli for? Dlaczego, technicznie rzecz biorąc, działają z prędkością C , podczas gdy pętla for działa z prędkością maszyny wirtualnej Pythona ?

Załóżmy, że w grze, którą tworzę, muszę narysować złożone i ogromne mapy, używając pętli. To pytanie byłoby zdecydowanie istotne, ponieważ jeśli na przykład rozumienie listy jest rzeczywiście szybsze, byłoby to znacznie lepszą opcją, aby uniknąć opóźnień (pomimo wizualnej złożoności kodu).

Poniżej znajdują się przybliżone wskazówki i oparte na doświadczeniu domysły. Powinieneś timeitlub profilować swój konkretny przypadek użycia, aby uzyskać twarde liczby, a te liczby mogą czasami nie zgadzać się z poniższymi.

Zrozumienie listy jest zwykle odrobinę szybsze niż dokładnie równoważna forpętla (która faktycznie buduje listę), najprawdopodobniej dlatego, że nie musi sprawdzać listy i jej appendmetody w każdej iteracji. Jednak składanie list nadal wykonuje pętlę na poziomie kodu bajtowego:

>>> 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

Używanie funkcji rozumienia listy zamiast pętli, która nie tworzy listy, bezsensowne gromadzenie listy bezsensownych wartości, a następnie odrzucanie listy, jest często wolniejsze ze względu na obciążenie związane z tworzeniem i rozszerzaniem listy. Listy składane nie są magią, która jest z natury szybsza niż stara dobra pętla.

Co do funkcjonalnej funkcji przetwarzania listy: Chociaż te są napisane w C i prawdopodobnie lepszych od równoważne funkcje napisane w Pythonie, są one nie koniecznie najszybszym rozwiązaniem. Oczekuje się pewnego przyspieszenia, jeśli funkcja jest napisana również w C. Jednak w większości przypadków przy użyciu lambda(lub innej funkcji Pythona) obciążenie związane z wielokrotnym konfigurowaniem ramek stosu Pythona itp. Pochłania wszelkie oszczędności. Zwykłe wykonywanie tej samej pracy w linii, bez wywołań funkcji (np. Rozumienie listy zamiast maplub filter) jest często nieco szybsze.

Załóżmy, że w grze, którą tworzę, muszę narysować złożone i ogromne mapy, używając pętli. To pytanie byłoby zdecydowanie istotne, ponieważ jeśli na przykład rozumienie listy jest rzeczywiście szybsze, byłoby to znacznie lepszą opcją, aby uniknąć opóźnień (pomimo wizualnej złożoności kodu).

Są szanse, że jeśli taki kod nie jest już wystarczająco szybki, gdy jest napisany w dobrym, niezoptymalizowanym Pythonie, żadna ilość mikrooptymalizacji na poziomie Pythona nie sprawi, że będzie on wystarczająco szybki i powinieneś zacząć myśleć o przejściu do C. Chociaż obszerny mikrooptymalizacje mogą często znacznie przyspieszyć kod Pythona, jest to niski (w kategoriach bezwzględnych) limit. Co więcej, nawet zanim osiągniesz ten pułap, staje się po prostu bardziej opłacalne (przyspieszenie o 15% w porównaniu z przyspieszeniem o 300% przy tym samym wysiłku), aby ugryźć pocisk i napisać trochę C.

Jeśli sprawdzisz informacje na python.org , możesz zobaczyć to podsumowanie:

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

Ale naprawdę powinieneś szczegółowo przeczytać powyższy artykuł, aby zrozumieć przyczynę różnicy w wydajności.

Zdecydowanie sugeruję również, abyś czas swojego kodu wykorzystał timeit . Pod koniec dnia może zaistnieć sytuacja, w której na przykład może zajść potrzeba wyrwania się z forpętli, gdy warunek zostanie spełniony. Potencjalnie może to być szybsze niż sprawdzenie wyniku przez telefon map.

Pytasz konkretnie o map(), filter()a reduce(), ale zakładam, że chcesz wiedzieć na temat programowania funkcjonalnego w ogóle. Po przetestowaniu tego samodzielnie na problemie obliczania odległości między wszystkimi punktami w zestawie punktów, programowanie funkcjonalne (z wykorzystaniem starmapfunkcji z wbudowanego itertoolsmodułu) okazało się nieco wolniejsze niż pętle for (zajmujące 1,25 razy dłuższe w fakt). Oto przykładowy kod, którego użyłem:

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

Czy wersja funkcjonalna jest szybsza niż wersja proceduralna?

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')

Napisałem prosty skrypt, który testuje szybkość i oto co się dowiedziałem. Właściwie pętla for była w moim przypadku najszybsza. To naprawdę mnie zaskoczyło, sprawdź poniżej (obliczałem sumę kwadratów).

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

Zmodyfikowałem kod @ Alisa i cProfilepokazałem, dlaczego rozumienie listy jest szybsze:

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()

Oto wyniki:

=========================
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}

MOIM ZDANIEM:

• reducei mapgeneralnie są dość powolne. Co więcej, używanie zwróconych sumiteratorów mapjest powolne w porównaniu z sumlistą
• for_loop używa dołączania, co oczywiście jest do pewnego stopnia powolne
• Zrozumienie listy nie tylko spędzało najmniej czasu na tworzeniu listy, ale sumw przeciwieństwie domap

Dodając zwrot akcji do odpowiedzi Alphii , w rzeczywistości pętla for byłaby druga najlepsza i około 6 razy wolniejsza niż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])

Główne zmiany polegały na wyeliminowaniu powolnych sumpołączeń, a także prawdopodobnie niepotrzebnych int()w ostatnim przypadku. Umieszczenie pętli for i mapy w tych samych warunkach czyni to właściwie. Pamiętaj, że lambdy to koncepcje funkcjonalne i teoretycznie nie powinny mieć skutków ubocznych, ale cóż, mogą mieć efekty uboczne, takie jak dodawanie a. Wyniki w tym przypadku z Pythonem 3.6.1, Ubuntu 14.04, Intel (R) Core (TM) i7-4770 CPU @ 3,40 GHz

0:00:00.257703 #Reduce
0:00:00.184898 #For loop
0:00:00.031718 #Map
0:00:00.212699 #List comprehension

Udało mi się zmodyfikować część kodu @ alpiii i odkryłem, że rozumienie list jest trochę szybsze niż pętla for. Może to być spowodowane przez int(), nie jest sprawiedliwe między zrozumieniem listy a pętlą 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