Является ли starmap быстрее, чем понимание вложенного списка? - PullRequest
Новая
       6

Является ли starmap быстрее, чем понимание вложенного списка?

0 голосов
/ 19 ноября 2018

Вот код, решающий задачу из здесь : 

def maximizingXor(l, r):
    return max([i^j for i in range(l, r+1) for j in range(i, r+1)])

А вот мое уродливое решение: 

from itertools import combinations, starmap
from operator import xor

# Complete the maximizingXor function below.
def maximizingXor(l, r):
    return max(starmap(xor, combinations(range(l,r+1),2)))

это не так красиво, как этоодин, но действительно быстрее при l = 10, r = 15:
% timeit показывает 3,81 мкс ± 156 нс для моего решения и 8,67 мкс ± 1,1 мкс на цикл для решения без вызова функций.
Так что вот вопрос- почему быстрее?И в более общем плане: в каких случаях вызов функций, подобных itertools, происходит быстрее, чем прямой цикл?Спасибо.

Ответы [ 2 ]

0 голосов
/ 20 ноября 2018

Ранее я отправил это с неправильным кодом. Быстрее найти максимум списка, чем максимум генератора. Если диапазон достаточно мал, чтобы поместиться в памяти, вы получите более быстрые результаты, создав список и найдя максимум, чем нет. 

def maximizingXor_lst(l, r):
    return max(list(starmap(xor, combinations(range(l, r+1), 2))))
0 голосов
/ 19 ноября 2018

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

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

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

# run 1 inputs
l, r = 10000, 15000

# run 2 inputs
l, r = 1000, 1500

%timeit maximizingXor_lc(l, r)   # 2.83 s per loop, 18.2 ms per loop
%timeit maximizingXor_ge(l, r)   # 2.48 s per loop, 21.5 ms per loop
%timeit maximizingXor(l, r)      # 1.53 s per loop, 15.2 ms per loop
%timeit maximizingXor_zip(l, r)  # 6.52 s per loop, 51.7 ms per loop

Код сравнения 

from itertools import combinations, starmap
from operator import xor

def maximizingXor_lc(l, r):
    return max([i^j for i in range(l, r+1) for j in range(i, r+1)])

def maximizingXor_ge(l, r):
    return max(i^j for i in range(l, r+1) for j in range(i, r+1))

def maximizingXor(l, r):
    return max(starmap(xor, combinations(range(l,r+1), 2)))

def maximizingXor_zip(l, r):
    return max(map(xor, *zip(*combinations(range(l,r+1), 2))))

assert maximizingXor_lc(l, r) == maximizingXor(l, r)
assert maximizingXor_lc(l, r) == maximizingXor_ge(l, r)
assert maximizingXor_lc(l, r) == maximizingXor_zip(l, r)
...