Оптимизация времени выполнения, чтобы проверить, есть ли символы слова в списке Python

Question

Я пишу код python2.7.15 для доступа к символам внутри слова.Как я могу оптимизировать этот процесс, чтобы также проверить, содержится ли каждое слово во внешнем списке?

Я пробовал две версии кода python2: версия (1) - это расширенная версия того, что должен делать мой код, тогда как в версии (2) я пробовал компактную версию того же кода.

chars_array = ['a','b','c']

VERSION (1)
def version1(word):
    chars =[x for x in word]
    count = 0

    for c in chars:
        if not c in chars_array:
            count+=1

    return count

VERSION (2)
def version2(word):
    return sum([1 for c in [x for x in word] if not c in chars_array])

Я анализирую большой корпус и для версии 1 получаю время выполнения 8,56 с, тогда как для версии 2 оно составляет 8,12 с.

Answer 1

С chars_array = ['a', 'e', 'i', 'o', 'u', 'y'] и words, равными списку из 56048 английских слов я измерил несколько вариантов с помощью команды, аналогичной следующей в приглашении IPython:

%timeit n = [version1(word) for word in words]

В каждом случае сообщалось «10 циклов, лучшее из 3», и я показал время на цикл в комментариях рядом с каждым определением функции ниже:

# OP's originals:

def version1(word):  # 163 ms
    chars =[x for x in word]
    count = 0
    for c in chars:
        if not c in chars_array:
            count+=1
    return count

def version2(word):  # 173 ms
    return sum([1 for c in [x for x in word] if not c in chars_array])

Теперь давайте нажмем version1 и version2 с тремя оптимизациями:

• удалить избыточное понимание списка и вместо этого перебрать word;
• используйте оператор not in вместо отрицания результата оператора in;
• проверка на (не) членство в set, а не list.

_

chars_set = set(chars_array)

def version1a(word):  # 95.5 ms
    count = 0
    for c in word:
        if c not in chars_set:
            count+=1
    return count

def version2a(word):  # 104 ms
    return sum([1 for c in word if c not in chars_set])

Так что на самом деле многострочный код имеет преимущество перед пониманием списка. Это может зависеть от длины слова, хотя: version2a должен выделить новый список такой же длины, что и слово, тогда как version1a - нет. Давайте уточним version2a далее, чтобы дать ему то же преимущество, суммируя по выражению генератора, а не по списку:

def version2b(word):  # 111 ms
    return sum(1 for c in word if c not in chars_set)

К моему удивлению, это было на самом деле немного контрпродуктивно, но опять же, этот эффект может зависеть от длины слова.

Наконец, давайте почувствуем силу .translate():

chars_str = ''.join(chars_set)

def version3(word):  # 40.7 ms
    return len(word.translate(None, chars_str))

У нас явный победитель.

Answer 2

Самое быстрое решение (может быть до 100 раз быстрее для очень длинной строки):

joined = ''.join(chars_array)
def version3(word):
    return len(word.translate(None, joined))

Еще одно более медленное решение, примерно такое же быстродействие, как и ваш код:

from itertools import ifilterfalse
def version4(word):
    return sum(1 for _ in ifilterfalse(set(chars_array).__contains__, word))

Время (s - случайная строка):

In [17]: %timeit version1(s)
1000 loops, best of 3: 79.9 µs per loop

In [18]: %timeit version2(s)
10000 loops, best of 3: 98.1 µs per loop

In [19]: %timeit version3(s)
100000 loops, best of 3: 4.12 µs per loop # <- fastest

In [20]: %timeit version4(s)
10000 loops, best of 3: 84.3 µs per loop