starmap быстрее операции в цикле?

#python #modules

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

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 µs ± 156 ns  на моем решении и  8.67 µs ± 1.1 µs per loop for solution
without functions callingна решении без модулей.      

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

Меня смущает тот факт, что конкретно здесь "в лоб" используется как бы встроенная
операция i^j, что по идее должно было быть быстрее, чем делать то же, но с использыванием
функции - оператора XOR. А поди ж ты )     

P.S.: как выяснилось, моен решение оказалось немного "разумнее" прямолинейного и
считает меньше элементов.
Более честно было бы сравнивать с вариантом i+1 вместо i

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


однако улучшение оказалось не решающим, а именно %timeit дает 6.62 µs ± 83.4 ns 

P.P.S.:  Ну и для полноты картины - tuple просто добавим скобок:

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


здесь %timeit дает 4.11 µs ± 77.2 ns. То есть генератор при засовывании в тупль -
замедляется ...
    

Ответы

Ответ 1

Меня смущает кое-что... А именно то, что результат combinations(range(l,r+1),2) и
for i in range(l, r+1) for j in range(i, r+1) разный. А конкретнее, вариант с двойным
range выдает больше элементов.

Переписал алгоритм и запустил:

from itertools import combinations

l=10
r=15

print(list(combinations(range(l,r+1),2)))
print([x for x in combinations(range(l,r+1),2)])
print([(i, j) for i in range(l, r+1) for j in range(i, r+1)])


Результат:

[(10, 11), (10, 12), (10, 13), (10, 14), (10, 15), (11, 12), (11, 13), (11, 14),
(11, 15), (12, 13), (12, 14), (12, 15), (13, 14), (13, 15), (14, 15)]
[(10, 11), (10, 12), (10, 13), (10, 14), (10, 15), (11, 12), (11, 13), (11, 14),
(11, 15), (12, 13), (12, 14), (12, 15), (13, 14), (13, 15), (14, 15)]
[(10, 10), (10, 11), (10, 12), (10, 13), (10, 14), (10, 15), (11, 11), (11, 12),
(11, 13), (11, 14), (11, 15), (12, 12), (12, 13), (12, 14), (12, 15), (13, 13), (13,
14), (13, 15), (14, 14), (14, 15), (15, 15)]




Давайте сравним производительность combinations, combinations_with_replacement и
вложенного цикла:

from timeit import timeit
NUMBER = 10000

elapsed = timeit("""\
list(combinations(range(l,r+1),2))
""", setup="""
from itertools import combinations
l=10
r=15
""", number=NUMBER)
print(elapsed)

elapsed = timeit("""\
list(combinations_with_replacement(range(l,r+1),2))
""", setup="""
from itertools import combinations_with_replacement
l=10
r=15
""", number=NUMBER)
print(elapsed)

elapsed = timeit("""\
[x for x in combinations(range(l,r+1),2)]
""", setup="""
from itertools import combinations
l=10
r=15
""", number=NUMBER)
print(elapsed)

elapsed = timeit("""\
[x for x in combinations_with_replacement(range(l,r+1),2)]
""", setup="""
from itertools import combinations_with_replacement
l=10
r=15
""", number=NUMBER)
print(elapsed)

elapsed = timeit("""\
[(i, j) for i in range(l, r+1) for j in range(i, r+1)]
""", setup="""
l=10
r=15
""", number=NUMBER)
print(elapsed)


Результат:

0.015679950736771395 : list(combinations(range(l,r+1),2))
0.019574358240705608 : [x for x in combinations(range(l,r+1),2)]
0.017971126274343937 : list(combinations_with_replacement(range(l,r+1),2))
0.023044554609408532 : [x for x in combinations_with_replacement(range(l,r+1),2)]
0.04071618284619548  : [(i, j) for i in range(l, r+1) for j in range(i, r+1)]




Как видно:


combinations генерирует меньше элементов и быстрее combinations_with_replacement.
combinations_with_replacement при таком же результате быстрее выполняется относительно
генератора списка с вложенным циклами
Код с генератором списка медленнее, чем такой же, но получаемый через вызов list:
list(...) быстрее [x for x in ...]. Впрочем, тут пример не совсем подходящий -- в таких
случаях в генераторе списка выполняются дополнительные действия, а не просто перекладывание
значения.


Ответ 2

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

В частности, есть такая вещь в numpy как type coercion - приведение элементов списка
при создании их него numpy array к одному типу, причем тип выбирается из типов элементов
списка самый "неудобный" (то есть, например, если есть среди целочисленных элементов
хотя бы один float, все элементы при создании массива приводятся к типу float). Я как-то
ради эксперимента решил сравнить следующие варианты превращения списка целочисленных
значений в строковые:

import numpy as np

lst=list(range(1000))

a=np.array(lst+[' '])[:-1]               #1
b=(np.array(lst+[' ']).tolist())[:-1]    #2 то же, что и №1, но приведенное к каноническому
списку
c=list(map(str, lst))                    #3
d=[str(x) for x in lst]                  #4
print(b==c==d)   #-> True
                 # для чистоты эксперимента сравниваем результаты (все,
                 # кроме №1,потому что №1 - это numpy array)


А теперь самое интересное:

import timeit
import numpy as np

vals=[]
codes=['a=list(range(1000));a=np.array(a+[' '])[:-1]',
       'a=list(range(1000));a=(np.array(a+[' ']).tolist())[:-1]',       
       'a=list(range(1000));a=list(map(str, a))',
       'a=list(range(1000));a=[str(x) for x in a]']

for code in codes:
    if 'np' in code:
        setup='import numpy as np'
    else:
        setup=''
    t = timeit.Timer(code, setup=setup)
    elapsed = t.timeit(number=10000)
    vals.append(elapsed)


И получаем интересную картину:



То есть, numpy type coercion у меня в два раза (а без преобразования в список - в
три) быстрее встроенной map.


Ответ 3

Скорее всего причина в быстрой реализации функции combinations() по сравнению с вложенными
циклами:

In [19]: items = list(range(1000))

In [20]: %timeit [(i, j) for i in items for j in items]
110 ms ± 5.3 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [21]: %timeit list(combinations(items, 2))
43.9 ms ± 961 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [22]: %timeit list(combinations_with_replacement(items, 2))
46 ms ± 4.4 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)