Самый быстрый способ нахождения гласной в строке

Недавно меня заинтересовала такая задача: как лучше всего определить, что в строке есть гласная?

Казалось бы, тривиальный вопрос, правда?

Но начав разбираться, я осознал, что задача гораздо глубже. Я бросил себе вызов: придумать как можно больше способов обнаружения гласной. Я даже попросил присоединиться ко мне нескольких друзей. Какой способ самый быстрый? Каким никогда не стоит пользоваться? Какой самый умный? Какой самый удобочитаемый?

В этом посте я рассмотрю 11 способов обнаружения гласных, алгоритмический анализ, дизассемблирование байт-кода Python, реализацию CPython и даже исследую опкоды скомпилированного регулярного выражения. Поехали!

def has_vowels(s: str) -> bool:     ...

Это каркас функции, который я буду заполнять. Если во входящей строке есть хотя бы одна гласная, возвращаем True, в противном случае — False. Код из этого поста выложен на GitHub.

Способ 1: цикл For

Я начал с самого наивного решения:

def loop_in(s):     for c in s.lower():         if c in "aeiou":             return True      return False 

Оно логично, понятно и, предположительно, не вызывает проблем с производительностью.

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

def loop_in(s):     for c in s:         if c in "aeiouAEIOU":             return True      return False 

Способ 2: цикл For в стиле C

Менее Pythonic-вариация нашего цикла for:

def loop_or(s):     for c in s.lower():         if c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u':             return True      return False 

Способ 3: вложенный цикл for

И если мы хотим охватить все варианты, то стоит попробовать и вложенный цикл for:

def nested_loop(s):     vowels = "aeiouAEIOU"     for c in s:         for v in vowels:             if c == v:                 return True     return False

Способ 4: пересечение множеств

А это уже интереснее. Вот моё любимое решение из тех, которые мне удалось придумать:

def set_intersection(s):     return set(s) & set("aeiouAEIOU")

Оно короткое, чистое и чуть более умное.

Помещаем входящую строку в множество, гласные — в другое множество и выполняем пересечение множеств. Множества достаточно эффективны. Вставка в первое множество выполняется за O(n), второе множество имеет постоянную длину, поэтому для его создания требуется O(1), а операция нахождения пересечения множеств пропорциональна наименьшему из двух множеств, имеющему постоянную длину, поэтому O(1), и общая временная сложность составляет O(n).

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

Способ 5: выражение-генератор

def any_gen(s):     return any(c in "aeiouAEIOU" for c in s)

Программисты любят однострочники. Я установил канал связи со своим внутренним пайтонистом и придумал такое выражение-генератор. Думаю, производительность будет эквивалентна показателям первого способа плюс немного оверхеда на объект-генератор.

Способ 6: рекурсия

Теперь, когда мы начинаем мыслить функционально, пришла пора попробовать рекурсию:

def recursion(s):     if not s:         return False     return s[0] in "aeiouAEIOU" or recursion(s[1:])

Это не придётся по душе CPython. Код создаст по новой строке для каждого символа входящей строки и вылетит, если длина строки превысит 1000 (максимальный предел рекурсии).

Способ 7: поиск регулярным выражением

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

import re def regex(s):     return bool(re.search(r'[aeiouAEIOU]', s))

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

Способ 8: удаление регулярным выражением

import re def regex_replace(s):     return len(re.sub(r'[aeiouAEIOU]', '', s)) != len(s)

Функция удаляет все гласные, а затем сравнивает длины строк, чтобы проверить, пропало ли что-то. Она неэффективна, потому что не выполняет ранний выход и создаёт копию строки.

Способ 9: фильтр

Все очевидные решения закончились. Что делать дальше?

def filter_lambda(s):     return bool(list(filter(lambda x: x in "aeiouAEIOU", s)))

Это сработает, но будет затратно и не обеспечит раннего выхода.

Способ 10: map

Похожее решение, но, возможно, чуть получше:

def map_lambda(s):     return any(map(lambda x: x in "aeiouAEIOU", s))

Использование лямбда-выражений делает вас круче, но будет ли производительность лучше того, что мы придумали раньше? В книге «Effective Python» говорится следующее: «списковые включения (list comprehension) чище, чем map и встроенные функции фильтров, потому что они не требуют лямбда-выражений». Поэтому код менее читаем и, вероятно, менее эффективен, чем в некоторых из предыдущих способов.

Способ 11: простые числа

Один из моих бывших студентов Грегори Кройсдейл придумал очень творческое и неожиданное решение:

primes = [i for i in range(2, 1000) if factorial(i - 1) % i == (i - 1)] def prime(s: str) -> bool:     vowels = "aeiouAEIOU"     vowel_primes_dict = {c: primes[ord(c)] for c in vowels}     try:         s_num = reduce(lambda acc, v: acc * primes[ord(v)], s, 1)         v_num = reduce(lambda acc, v: acc * vowel_primes_dict[v], vowels, 1)         return gcd(s_num, v_num) != 1     except Exception:         return False

Оно сопоставляет каждый символ входящей строки и каждую гласную с уникальным простым числом, кодирует входящую строку как произведение простых чисел её символов и возвращает True, если наибольший общий делитель этого произведения с произведением простых чисел гласных больше 1 (то есть у них есть хотя бы одно общее простое число гласной). 🤯

Способ 12: потоки

А может, нам распараллелить поиск при помощи потоков? Разбить строку на n подстроки и использовать один из приведённых выше способов со всеми подстроками. Я попробовал так сделать. Это оказалось о-о-очень медленно. Возможно, мы бы что-то выиграли, если бы строки были огромными (например, больше 1 ГБ) и я бы отключил GIL.

---

Бенчмарк

Итак, 11 способов — это весь спектр решений, которые мне удалось придумать. Настало время провести их бенчмаркинг!

Я сравнивал все эти функции при помощи случайных строк, с гласными и без них, разной длины. Бенчмарк генерировал 2000 случайных строк (половина из них не содержала гласных) и выполнял каждый из способов для строки пять раз. Выполнялось три таких прогона и фиксировалось наименьшее среди них общее время.

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

Хм, выглядит логично. При такой длине все способы кажутся быстрыми. Можно сделать следующие наблюдения: простая loop_in победила, но очень похожая loop_or довольно медленная. Поиск регулярным выражением быстр, намного быстрее, чем я ожидал изначально. Моё любимое пересечение множеств довольно быстрое в реальных сценариях, но в рейтинге выглядит не очень хорошо, его побеждает даже рекурсия. И совершенно неудивительно, что шутка с простыми числами медленная. Но не такая уж медленная

С увеличением длины строк разброс становится гораздо очевиднее. Вот результаты при длине строки 100:

Оба способа с регулярными выражениями вырвались вперёд! Хм, простые числа теперь не последние? Самыми медленными оказались цикл с or и вложенные циклы. Ого!

Вот полная таблица для длин 10, 100, 1000 и 10000.

График тех же данных:

Способы с регулярными выражениями невероятно быстры для любой длины строк. Циклы в стиле C очень медленные. Лично я ожидал, что regex будут с ними сравнимы по скорости! Время способа с простыми числами резко возрастает, а всё остальное работает вполне неплохо.

Но меня интересовало и то, как на результаты повлияет то, что в строках будут редко встречаться гласные. Я снова провёл бенчмарк со строками, в которых гласные всегда располагались в последних 10% символов.

Regex по-прежнему доминируют, но моё любимое пересечение множеств проявило себя гораздо лучше.

Также я сравнил способ re.search с предварительно скомпилированным регулярным выражением (re.compile). Для коротких строк разница достаточно велика (0,009 с против 0,2 с для 100000 вызовов при длине строк 10), но для длинных строк несущественна (0,234 с против 0,235 с для 10000 вызовов при длине строк 1000). На самом деле, CPython всегда компилирует регулярные выражения и кэширует их, даже если мы не вызываем компиляцию в явном виде. [См. логику в re/__init__.py.] Разница в том, включаем ли мы во время бенчмарка работу по компиляции и поиск в кэше.

Подведём итог: для очень коротких строк loop_in самая быстрая. При длине 25 она на одном уровне с регулярными выражениями. При более длинных строках regex вырываются вперёд. При сравнении loop_in с set_intersection, когда гласные встречаются в начале строк, loop_in побеждает. Если строки длинные (>500 символов) или гласные в них встречаются редко, то set_intersection побеждает.

Весь код можно найти на GitHub.

---

Почему регулярные выражения настолько быстрые?

Меня очень удивило, что регулярки настолько быстрее остальных способов. Я ожидал затрат на оверхед, из-за чего они сравнятся по скорости с простым циклом. Мне обязательно нужно было это исследовать.

Что здесь происходит? Давайте исследуем байт-код Python этих способов.

def has_vowel(s):     for c in s:         if c in "aeiouAEIOU":             return True      return False 

import re def has_vowel(s):     return bool(re.search(r'[aeiouAEIOU]', s))

Байт-код способа с циклом:

   LOAD_FAST          s    GET_ITER L1 FOR_ITER          STORE_FAST         c     LOAD_FAST          c    LOAD_CONST         'aeiouAEIOU'    CONTAINS_OP        0         POP_JUMP_IF_TRUE   L2      JUMP_BACKWARD      L1      L2 LOAD_FAST          c    SWAP    POP_TOP    RETURN_VALUE  L3 END_FOR    POP_TOP    RETURN_CONST      None 

«Мясо» алгоритма состоит из 7 опкодов, начинающихся с метки L1. Давайте разберём их один за другим. FOR_ITER извлекает итератор из стека и пытается получить следующий символ (если его нет, то выполняется переход к L3). STORE_FAST сохраняет текущий символ в локальную переменную. LOAD_FAST помещает символ обратно в стек. LOAD_CONST записывает строку гласных в стек. CONTAINS_OP извлекает из стека два элемента, выполняет проверку in и записывает в стек True или False. POP_JUMP_IF_TRUE выполняет переход к L2, если символ был гласной, а в противном случае продолжает выполнение. JUMP_BACKWARD переходит обратно к L1 для повторения процесса.

Эти 7 опкодов выполняются для каждого символа. Они просты (за исключением, возможно, CONTAINS_OP), хотя избыточная работа и определённо выполняется (например, запись каждый раз строки гласных в стек).

Сравним это с байт-кодом регулярного выражения:

  LOAD_GLOBAL        re   LOAD_ATTR          search   PUSH_NULL         LOAD_CONST         '[aeiouAEIOU]'   LOAD_FAST          s   CALL               2   RETURN_VALUE

Он просто вызывает функцию C. Изучив реализацию движка регулярных выражений CPython (sre.c и sre_lib.h), можно увидеть, что она создаёт внутреннее представление регулярного выражения, итерирует при помощи единственного цикла for и использует поиск по таблице (не вложенный цикл). Соответствующий код находится в блоке if строки 1825 в sre_lib.h:

Я хотел понять, как выглядит внутреннее представление регулярного выражения, поэтому выполнил re.compile("[aeiouAEIOU]", re.DEBUG). Вывод был таким:

IN     LITERAL 97     LITERAL 101     LITERAL 105     LITERAL 111     LITERAL 117     LITERAL 65     LITERAL 69     LITERAL 73     LITERAL 79     LITERAL 85  0: INFO    14 0b100 1 1    (to 15)     in 5: CHARSET [0x00000000, 0x00000000, 0x00208222, 0x00208222,             0x00000000, 0x00000000, 0x00000000, 0x00000000] 14: FAILURE 15: IN      11             (to 27) 17: CHARSET [0x00000000, 0x00000000, 0x00208222, 0x00208222,             0x00000000, 0x00000000, 0x00000000, 0x00000000] 26: FAILURE 27: SUCCESS

Литералы — это отдельные гласные в верхнем и нижнем регистре. CHARSET выполняет единственную операцию поиска, чтобы при помощи битовой карты проверить, является ли текущий символ гласной. Очень умное решение! (Я не знаю, зачем производится вторая проверка, а не просто продолжается выполнение.)

Огромная разница в производительности вызвана сочетанием оверхеда интерпретатора и оптимизированным движком регулярных выражений.

---

Это было очень интересное исследование. Результаты оказались неожиданными для меня. Регулярные выражения очень быстры, а не-Pythonic код по сравнению с ними может показаться медленным. В конечном итоге, должно ли это повлиять на то, как вы выполняете поиск по строкам? Не обязательно. Пишите код так, как вам проще будет поддерживать, если только вы не работаете с миллионами строк и вам не важны миллисекунды. Но всё равно было очень увлекательно узнать, как это работает.

Теперь я могу ответить на вопрос: как же быстрее всего обнаружить гласную в строке? Похоже, при помощи битовой карты на C.

---

Дополнение 1: Kranar выяснил, что find(), языка Python, реализованная в fastsearch.h на C, существенно обгоняет регулярные выражения. Это ещё раз подтверждает тот факт, что причиной большой разницы в производительности оказывается интерпретатор CPython.

def vowel_find(s):     for c in "aeiouAEIOU":         if s.find(c) != -1:             return True     return False

Дополнение 2: a_e_k нашёл ещё более совершенное решение, оказавшееся простым и изящным! Если просто поменять местами циклы, то код будет гораздо быстрее, чем в решениях с regex и find:

def loop_in_perm(s):         for c in "aeiouAEIOU":             if c in s:                 return True         return False

В два с лишним раза быстрее, чем find для коротких строк и в 16 раз быстрее, чем регулярки для длинных строк.

Перемена местами циклов улучшает любое решение, делая их сравнимыми по скорости с find:

  def any_gen_perm(s):       return any(c in s for c in "aeiouAEIOU")