Почему "any()" работает медленнее, чем использование циклов?

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

Наконец, я решил задать вопрос, потому что возможно, что я делаю что-то неправильно. Следующий код попытается проверить производительность функции any() в сравнении с использованием циклов.

#!/usr/bin/python3
#

import time
from unicodedata import normalize


file_path='./tests'


start=time.time()
with open(file_path, encoding='utf-8', mode='rt') as f:
    tests_list=f.read()
print('File reading done in {} seconds'.format(time.time() - start))

start=time.time()
tests_list=[line.strip() for line in normalize('NFC',tests_list).splitlines()]
print('String formalization, and list strip done in {} seconds'.format(time.time()-start))
print('{} strings'.format(len(tests_list)))


unallowed_combinations=['ab','ac','ad','ae','af','ag','ah','ai','af','ax',
                        'ae','rt','rz','bt','du','iz','ip','uy','io','ik',
                        'il','iw','ww','wp']


def combination_is_valid(string):
    if any(combination in string for combination in unallowed_combinations):
        return False

    return True


def combination_is_valid2(string):
    for combination in unallowed_combinations:
        if combination in string:
            return False

    return True


print('Testing the performance of any()')

start=time.time()
for string in tests_list:
    combination_is_valid(string)
print('combination_is_valid ended in {} seconds'.format(time.time()-start))


start=time.time()
for string in tests_list:
    combination_is_valid2(string)
print('combination_is_valid2 ended in {} seconds'.format(time.time()-start))

Предыдущий код довольно типичен для моих тестов, и если мы посмотрим на результаты:

File reading done in 0.22988605499267578 seconds
String formalization, and list strip done in 6.803032875061035 seconds
38709922 strings
Testing the performance of any()
combination_is_valid ended in 80.74802565574646 seconds
combination_is_valid2 ended in 41.69514226913452 seconds


File reading done in 0.24268722534179688 seconds
String formalization, and list strip done in 6.720442771911621 seconds
38709922 strings
Testing the performance of any()
combination_is_valid ended in 79.05265760421753 seconds
combination_is_valid2 ended in 42.24800777435303 seconds

Мне кажется удивительным, что использование циклов наполовину быстрее, чем использование any(). Каким будет объяснение этому? Я что-то делаю неправильно?

(я использовал python3.4 в GNU-Linux)

Ответ 1

На самом деле функция any() равна следующей функции:

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

который похож на вашу вторую функцию, но так как any() возвращает логическое значение самостоятельно, вам не нужно проверять результат и затем возвращать новое значение. Таким образом, разница в производительности связана с тем, что вы на самом деле используют избыточные условия возврата и if, также вызывающие any внутри другой функции.

Таким образом, преимущество any заключается в том, что вам не нужно обертывать его другой функцией, потому что он делает все для вас.

Также как упоминается в комментарии @interjay, кажется, что самая важная причина, по которой я пропустил, заключается в том, что вы передаете выражение генератора в any(), которое не дает результатов сразу и поскольку оно дает результат по требованию выполняет дополнительную работу.

На основе PEP 0289 - выражения генератора

Семантика выражения генератора эквивалентна созданию анонимной функции генератора и ее вызову. Например:

g = (x**2 for x in range(10))
print g.next()

эквивалентно:

def __gen(exp):
    for x in exp:
        yield x**2
g = __gen(iter(range(10)))
print g.next()

Итак, как вы можете видеть каждый раз, когда python хочет получить доступ к следующему элементу, он вызывает функцию iter и метод next генератора. И, наконец, результат состоит в том, что он излишне использует any() в таких случаев.

Ответ 2

Поскольку ваш истинный вопрос отвечает, я сделаю снимок по предполагаемому вопросу:

Вы можете получить бесплатное ускорение, просто сделав unallowed_combinations = sorted(set(unallowed_combinations)), так как оно содержит дубликаты.

Учитывая, что самый быстрый способ, которым я знаю это,

valid3_re = re.compile("|".join(map(re.escape, unallowed_combinations)))

def combination_is_valid3(string):
    return not valid3_re.search(string)

С CPython 3.5 я получаю для некоторых тестовых данных с длиной строки 60 символов

combination_is_valid ended in 3.3051061630249023 seconds
combination_is_valid2 ended in 2.216959238052368 seconds
combination_is_valid3 ended in 1.4767844676971436 seconds

где третий является версией регулярного выражения, а на PyPy3 я получаю

combination_is_valid ended in 2.2926249504089355 seconds
combination_is_valid2 ended in 2.0935239791870117 seconds
combination_is_valid3 ended in 0.14300894737243652 seconds

FWIW, это конкурентноспособно с Rust (язык низкого уровня, например С++) и на самом деле заметно выигрывает на стороне регулярных выражений. Более короткие строки предпочитают PyPy над CPython намного больше (например, 4x CPython для длины строки 10), поскольку более важны более накладные расходы.

Так как только около трети времени выполнения CRython regex - это накладные расходы цикла, мы заключаем, что реализация регулярного выражения PyPy лучше оптимизирована для этого прецедента. Я бы порекомендовал посмотреть, есть ли реализация регулярного выражения CPython, которая делает эту конкуренцию с PyPy.