Недавно меня заинтересовала такая задача: как лучше всего определить, что в строке есть гласная?
Казалось бы, тривиальный вопрос, правда?
Но начав разбираться, я осознал, что задача гораздо глубже. Я бросил себе вызов: придумать как можно больше способов обнаружения гласной. Я даже попросил присоединиться ко мне нескольких друзей. Какой способ самый быстрый? Каким никогда не стоит пользоваться? Какой самый умный? Какой самый удобочитаемый?
В этом посте я рассмотрю 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 |
0.001219 |
regex |
0.002039 |
any_gen |
0.002735 |
regex_replace |
0.003047 |
map_lambda |
0.003179 |
recursion |
0.004066 |
filter_lambda |
0.004234 |
set_intersection |
0.004465 |
loop_or |
0.008870 |
nested_loop |
0.010895 |
prime |
0.016482 |
Хм, выглядит логично. При такой длине все способы кажутся быстрыми. Можно сделать следующие наблюдения: простая loop_in победила, но очень похожая loop_or довольно медленная. Поиск регулярным выражением быстр, намного быстрее, чем я ожидал изначально. Моё любимое пересечение множеств довольно быстрое в реальных сценариях, но в рейтинге выглядит не очень хорошо, его побеждает даже рекурсия. И совершенно неудивительно, что шутка с простыми числами медленная. Но не такая уж медленная
С увеличением длины строк разброс становится гораздо очевиднее. Вот результаты при длине строки 100:
Функция |
Время (секунды) |
|---|---|
regex |
0.003778 |
regex_replace |
0.005480 |
loop_in |
0.008526 |
any_gen |
0.015479 |
set_intersection |
0.015495 |
map_lambda |
0.021085 |
filter_lambda |
0.026546 |
recursion |
0.040774 |
prime |
0.077477 |
loop_or |
0.082003 |
nested_loop |
0.104956 |
Оба способа с регулярными выражениями вырвались вперёд! Хм, простые числа теперь не последние? Самыми медленными оказались цикл с or и вложенные циклы. Ого!
Вот полная таблица для длин 10, 100, 1000 и 10000.
Функция |
Длина 10 |
Длина 100 |
Длина 1000 |
Длина 10000 |
|---|---|---|---|---|
regex |
0.002079 |
0.003778 |
0.020088 |
0.181247 |
regex_replace |
0.003012 |
0.005480 |
0.027443 |
0.245306 |
set_intersection |
0.004241 |
0.015495 |
0.082475 |
0.601355 |
loop_in |
0.001170 |
0.008526 |
0.076880 |
0.763442 |
any_gen |
0.002662 |
0.015479 |
0.137218 |
1.356772 |
map_lambda |
0.003090 |
0.021085 |
0.192258 |
1.915244 |
filter_lambda |
0.004305 |
0.026546 |
0.244302 |
2.424177 |
loop_or |
0.007713 |
0.082003 |
0.769124 |
7.814960 |
nested_loop |
0.008718 |
0.104956 |
0.797087 |
8.455867 |
prime |
0.016113 |
0.077477 |
2.619118 |
203.579320 |
recursion |
0.004064 |
0.040774 |
Не работает |
Не работает |
График тех же данных:
Способы с регулярными выражениями невероятно быстры для любой длины строк. Циклы в стиле C очень медленные. Лично я ожидал, что regex будут с ними сравнимы по скорости! Время способа с простыми числами резко возрастает, а всё остальное работает вполне неплохо.
Но меня интересовало и то, как на результаты повлияет то, что в строках будут редко встречаться гласные. Я снова провёл бенчмарк со строками, в которых гласные всегда располагались в последних 10% символов.
Функция |
Длина 10 |
Длина 100 |
Длина 1000 |
Длина 10000 |
|---|---|---|---|---|
regex |
0.002083 |
0.004288 |
0.025301 |
0.235313 |
regex_replace |
0.002950 |
0.005264 |
0.027415 |
0.244298 |
set_intersection |
0.004346 |
0.015110 |
0.080171 |
0.660243 |
loop_in |
0.001444 |
0.011158 |
0.100641 |
0.989452 |
any_gen |
0.003282 |
0.019758 |
0.179111 |
1.770298 |
map_lambda |
0.003757 |
0.026654 |
0.252468 |
2.528173 |
filter_lambda |
0.004106 |
0.026335 |
0.244043 |
2.424267 |
loop_or |
0.011777 |
0.123697 |
1.029399 |
10.184211 |
nested_loop |
0.010682 |
0.106838 |
1.046352 |
10.762563 |
prime |
0.016026 |
0.076423 |
2.605674 |
205.035926 |
recursion |
0.005025 |
0.053011 |
Не работает |
Не работает |
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")Комментарии (84)
Jijiki
23.06.2025 13:22но тут нюанс что это в строке(тоесть варианта 2 учесть все случаи regex, или писать самому поиск чото такое - я для себя так понял), перемена местами логически выглядит как пока есть строка сравнение с буквы с гласной, и далее конечная проверка на вхождение в строку типо что-то такое - (так понял, может ошибаюсь), тоесть это ближайшая опора к кмп
еще нюанс может быть при 1000000 символов, строк может быть 100 000Алгоритм_Кнута_—_Морриса_—_Пратта
дальше пойдёт(или не пойдёт, ну я задавался таким вопросом )) сравнение что лучше хэш, лист, дабл лист, или дерево с авто сортировкой) или ничего ну тоесть результаты делаются при проходе (что регекс, что выбранный), ну потомучто конверсия при прогонке поидее тоже ест производительность наверно(регекс кароче более требователен к тонкой настройке, своё разбитие может быть просто читаемее - понятнее)
тема интересная, спасибо, тоже столкнулся
п.с. поиск гласного частный случай поиска кмп вобщем-то ну или чего-то похожего по поиску слов, например какая-нибудь маска битовая слова или буквы(тоесть приводящая к симд наверно косвенно)
Jijiki
23.06.2025 13:22пойду от обратного, только что придумал, если имеем полу кмп поиск первого вхождения), то если иметь угадыватель - разбиватель строк по принципу по 1 вхождению, то полу кмп будет еффективнее)(хотя вроде спорно, но интересно), но тут на букву и слово будут разные угадыватели-разбиватели)
cupraer
23.06.2025 13:22Naïve, Moët, половина немецкого языка и три четверти французского и испанского смотрят на список гласных с недоумением.
ImagineTables
23.06.2025 13:22Naïve и Moët не самые удачные примеры. Алгоритм сработает на “a” и “o”.
Но есть простое английское слово pâté. И его можно записать четырьмя кодепоинтами (второй — ʟᴀᴛɪɴ ꜱᴍᴀʟʟ ʟᴇᴛᴛᴇʀ ᴀ ᴡɪᴛʜ ᴄɪʀᴄᴜᴍꜰʟᴇx,
U+00E2, четвёртый — ʟᴀᴛɪɴ ꜱᴍᴀʟʟ ʟᴇᴛᴛᴇʀ ᴇ ᴡɪᴛʜ ᴀᴄᴜᴛᴇ,U+00E9). И на нём функция скажет: «Бдзынь!», а мы скажем: «Вот то-то же».cupraer
23.06.2025 13:22«Naïve» — английское слово, записанное по правилам английского языка (диерезис ломает дифтонг, иначе читалось бы «найв»). Его можно записать пятью кодпоинтами в NFC (Normalization Form Canonical Composition).
Слово «pâté» — заимствование из французского и пишется по правилам французского языка, как практически всё, что заимствуется в английский из языков с тем же алфавитом.
Зачем, интересно, вам потребовалась фраза про «неудачный пример»?
Neusser
23.06.2025 13:22Так и naïve точно такое же заимствование из французского, написанное по-французски. Naive тоже правильно.
cupraer
23.06.2025 13:22Откуда вы все такие полиглоты берётесь-то, а?
Французское слово — «naïf», и в английский именно оно напрямую заимствовано не было.
Как я написал выше, две точки в английском «naïve» — это диерезис. Приличные английские издания до сих пор «coöperation» с тремой пишут — тоже заимствование?
Naive тоже правильно.
Кому и кобыла невеста.
Neusser
23.06.2025 13:22coöperation» с тремой пишут — тоже заимствование?
Вы сейчас серьезно спрашиваете, является ли слово cooperation в английском языке заимствованием? Ваша квалификация ясна.
Кому и кобыла невеста
Напишите это в издательства словарей Cambridge, Merriam-Webster, Collins.
ImagineTables
23.06.2025 13:22Зачем, интересно, вам потребовалась фраза про «неудачный пример»?
Повторяю:
Алгоритм сработает на “a” и “o”
ImagineTables
23.06.2025 13:22P.S. Первоначально мой комментарий содержал не одну, а две причины считать это неудачными примерами. От одной я отказался сразу же, отредактировав комментарий через минуту. Видимо, Хабр успел отправить уведомление с первоначальным текстом комментария.
От второй причины («алгоритм сработает на “a” и “o”») я не отказываюсь.
MaxAkaAltmer
23.06.2025 13:22Наивно ожидал здесь увидеть решение для всего юникода )
cupraer
23.06.2025 13:22Там всё просто: надо распарсить последнюю спецификацию консорциума, выкусить оттуда гласные… Ах да, консорциум же не озаботился добавить ни в названия, ни в мету информацию гласная/согласная :)
Консорциум не в курсе, что такое гласная/согласная Так что нет, Хрюша сегодня не придёт.
Maccimo
23.06.2025 13:22Ах да, консорциум же не озаботился добавить ни в названия, ни в мету информацию гласная/согласная
«Любая, даже самая сложная, проблема обязательно имеет простое, легкое для понимания, неправильное решение.»
Возьмём, для примера, простую букву «Ъ». Ну явно же она не гласная, это и дураку понятно. Потом идём в Википедию и, упс:
в болгарском языке буква ъ (болг. ер голям) имеет собственную своеобразную фонему, под ударением реализующуюся как неогублённый гласный звук заднего ряда средне-верхнего подъёма.
Что в метаинформацию для этой кириллической буквы писать будем?
MaxAkaAltmer
23.06.2025 13:22Если кому интересно - есть такая библиотека ICU, с помощью нее можно проверять гласность на уровне всего юникода.
cupraer
23.06.2025 13:22Таких библиотек полно́, проблема в том, что они все до единой созданы вручную.
MaxAkaAltmer
23.06.2025 13:22А как иначе-то? Сама должна появиться? )
cupraer
23.06.2025 13:22В спецификации консорциума есть даже такие мелочи, как правильный casing (чтобы в турецком
"istanbul".to_upperпревращался в"İstanbul").Грамотно спроектированные языки — парсят эту спецификацию. Но с гласными/согласными — это не проходит, приходится размечать руками.
S_gray
23.06.2025 13:22Деление звуков на гласные/согласные существует не во всех языках. В некоторых такое разделение просто бессмысленно...
MaxAkaAltmer
23.06.2025 13:22Деление звуков (подчеркиваю - звуков) на гласные и согласные так или иначе есть во всех языках согласно международному фонетическому алфавиту, а вот в плане письменности - да, бывает бессмысленно, но в таком случае символ просто не гласная и не согласная. Кстати гласным символ может быть или не быть в зависимости от диакритических знаков в некоторых языках. Так что все очень неоднозначно, всем надо переходить на фонетический алфавит - а то развели тут зоопарк понимаешь )
S_gray
23.06.2025 13:22Ну в статье идёт речь именно о письменности, а не о фонетике, поскольку мы имеем здесь дело не с языками, а с изображением текстов.
Не всякий письменный язык - фонетический. Насчёт перехода на фонетическую письменность: а вы когда-нибудь задавались вопросом, почему этого не происходит? Это же не просто так всё... Я, когда начинал изучать иврит, тоже думал - "ну, на кой это всё?" А сейчас вот повзрослел, особенно, когда про китайский кое-что понял... Кстати, реформа русского языка после революции очень здорово порубила его базовые смыслы, превратив живой, довольно, правда, сложный, но построенный на определенной логике и имеющий свою историю язык в упрощённый набор звуков...
MaxAkaAltmer
23.06.2025 13:22Это вы сказали про звуки, в статье понятно о чем речь идет.
Не происходит потому, что всем не угодишь, мне например не нравится фонетический алфавит на основе латиницы. Живой язык, на то и живой, чтобы эволюционировать. Иногда нужно избавляться и от архаики, это полезно, вот например зачем нам Ш и Щ? Ведь Щ - это мягкая Ш, там и пресловутые ЧА ЩА и другие правила нормализовать можно, да и нормальное место на клавиатуре для Ё (кстати гораздо более нужной в качестве отдельного символа) нашлось бы сразу. Но это конечно имхо, имеем все равно то что имеем.
Jijiki
23.06.2025 13:22самое классное это получить все ключи - то для чего и создано программирование например из слов
你好ведь их можно сравнивать и как просто конечное слово и как 2 слова, и как составные ключи. другой пример не пришел мне, ну или как в Корейском языке падчим найти все составные падчима, собственно это то решение которое в дополнении для ввода такого рода символов, но наоборот. Типо дано конечное состояние, его надо проанализировать и вывести все ключи.если посмотреть на Хирагану-Катакану, то там тоже есть мягкость и твёрдость
czz
23.06.2025 13:22Шявель?
cupraer
23.06.2025 13:22Немцы же как-то справляются: Tschyawell.
Maccimo
23.06.2025 13:22Tschyawell
Что это?
Звук, похожий на русское «Й» в немецком передаётся буквой «J». Даже не учившие немецкий наверняка знают восклицание «Ja-ja!».Группа «Tsch» обозначает звук «Ч». Далеко ходить не надо, «Deutsch», «Дойч» — «немецкий».
А щавель это «Sauerampfer».
ManulVRN
23.06.2025 13:22Насколько я знаю, идею перевода китайского на латиницу (то есть фонетическую запись) зарубили по политическим соображениям - стало ясно, что фонетическая запись продемонстрирует наличие в Китае нескольких даже не диалектов, а языков.
Quintanar
23.06.2025 13:22Нет. Если посмотреть на фонетическую запись, сразу видно какое это убожество. Как геометрическую задачу решать алгеброй.
ManulVRN
23.06.2025 13:22Тащить многовековой давности легаси в правилах орфографии не очень осмысленно. Разницы между "ять" и "е" русскоговорящие люди не слышали уже в 18 веке, не говоря уж про 20-й, ну и зачем было учить наизусть список слов, где положено писать "ять"? "Ер" (твердый знак) в конце слова когда-то был гласным - потому что в древнерусском языке существительное не могло заканчиваться согласным звуком, вот он и выполнял роль такой фиктивной гласной, соответствуя специфическому слабому е. Но такого произношения, наверное, уже при Борисе Годунове не существовало.
S_gray
23.06.2025 13:22Проблема в том, что во всём ищется логический смысл с желанием всё упростить. Культура - она не про упрощение. Это в математике нужно всё сокращать с целью упрощения. Но язык - это не математика. Язык - это не просто передача информации с помощью звуков. Это огромный пласт культуры, в том числе и визуальной... Рассуждая о культуре и истории с точки зрения логики, можно выбросить, в итоге, всё, что отличает человека от животного - а чего там - пить-есть-размножаться - какая там Культура, История, Мысль? А животному зачем язык? Можно обойтись рычанием, воем, потявкиванием - десяток-другой сигналов и всё. Вот к этому и ведёт Великое Логичное Упрощение.
Сумбурно, но нет у меня ни желания ни сил переубеждать великих Логиков...
Заглавные буквы использовал намеренно, для усиления, так сказать... Кстати, в иврите нет заглавных букв, зато есть, так сказать "конечные" - ну, не было в языке когда-то давно пробелов между словами (а, кстати, на древнеславянские тексты посмотрите). Тоже архаизм...
S_gray
23.06.2025 13:22Недавно совсем узнал:
Аз буки веди - я знаю буквы,
Глаголь добро есть - слово - это добро (достояние)
Живѣте зело и иже како люди - живите усердно, как подобает людям...
Вот в нашей абэвэгэдэйке кто про это сейчас помнит?
Neusser
23.06.2025 13:22Молодцы древние греки! Сразу так алфавит придумали, что он на древнерусском стал какой-то текст (нет!).
Можете эту фоменковщину спокойно забыть.
cupraer
23.06.2025 13:22Какую еще фоменковщину? Вы отрицаете названия букв кириллицы?
Neusser
23.06.2025 13:22Нет, я не отрицаю названия букв кириллицы. Я (и даже не я, а научный мир) отрицаю то, что эти названия несут какой-то сакральный смысл (и, как мне кажется, довольно ясно об этом написал).
Да в принципе и в исходном комметарии понятно, что речь не о названиях букв, а о тексте, который они якобы образуют.
cupraer
23.06.2025 13:22Какой еще нафиг сакральный смысл? Вы там белены объелись? Это названия букв на старославянском, выбранные так, чтобы их было проще запомнить.
«Аз» — это буквально «я», «буки» — буквы, «веде» — глагол знать/изучать в первом лице.
Neusser
23.06.2025 13:22Когда пишут названия букв на старославянском, то их просто пишут - аз, буки, веди, глагол, добро и тд. А когда их вот так разделяют на фразы, да еще и с комметариями, как здесь
Аз буки веди - я знаю буквы,
Глаголь добро есть - слово - это добро (достояние)
Живѣте зело и иже како люди - живите усердно, как подобает людям...
то это явный маркер, что речь идет вот об этой фоменковщине: Русская Азбука – Послание к славянам
cupraer
23.06.2025 13:22Кстати, к вашему сведению, буквы финикийского алфавита тоже имели свои названия, только они были даны по схожести глифа с предметом (чаще всего через базовую древнеегипетскую иероглифику).
Jijiki
23.06.2025 13:22это же зависит от ввода, загруженного языка, тоесть это загрузили язык, храним строку определенного веса, в статье рассматривается просто работа со строкой, тоесть придётся делать больше проверок на соответствие шрифта к набору на ПК(или не делать, но размер строки будет влиять на то какие строки и какое количество символов рисуется, например Китайский 1000 000 символов и 100 000 строк это будет не такой размер как с аски), на дефолтовом уровне проще поддерживать решение с аски, а далее уже смотреть с языками, потомучто решение с Юникодом в купе с отрисовкой будет сьедать ресурс
и придём в итоге к локализации и прописи локали в локализации, если писать свой движок на юникодах(из точек через ttf)
на аски проще если это консоль и/или фреймворк уже имеет в себе все эти проверки
например свинг поидее имеет эти проверки, соотв я просто работаю со строкой, а как она будет рисоваться пока не волнует пока нет такого вопроса
mynameco
23.06.2025 13:22можно собрать статистику по языку и словам. для каждого индекса в слове свой массив букв в порядки частоты вхожления. таким массов будет немного, по слову с макимальным число согласных в начале. так же, возможно, некоторые проверки, заменить больше меньше, чем по всему массиву прлходить.
так же можно собрать статистику слов и найти минимальное по длине слово без гласной. и проверять длинну слова, если оно больше, гласная есть.
чем дальше индекс тем меньше или нулевая вероятность встретить конкретную гласную, если до этого индекса были все согласные
Jijiki
23.06.2025 13:22там обычно чаще суть в том чтобы знать где буква-слово в исходном тексте, соотв нужны они все
Скрытый текст
class kvlist { private Integer k; private String v; public kvlist(int ka,String ve){ this.k=ka; this.v=ve; } public Integer getKa(){ return k; } public String getVe(){ return v; } } public class example { public static void main(String[] args) { String text = "你好 早上好 你好 晚上好 你好吗? 你好 谢谢 你好 不客气 你好 你好 请 你好 对不起 没关系 你好 我叫 你好 再见 你好 我"; String[] parts = text.split(" ");//\n String search = "你好"; List<kvlist> sortedByKeyMap = new ArrayList<>(); int searchStartIndex = 0; for (String word : parts) { String[] parts1 = word.split("(?U)(?<=\\s)(?=\\S)|(?<=\\S)(?=\\s)|(?<=\\w)(?=\\W)|(?<=\\W)");// for(String r:parts1){ int indexInText = text.indexOf(r, searchStartIndex); if (indexInText >= 0) { sortedByKeyMap.add(new kvlist(indexInText,new String(r))); searchStartIndex = indexInText + r.length(); } } } for (kvlist entry: sortedByKeyMap) { if(entry.getVe().equals(search)){ System.out.println(entry.getKa()+" "+entry.getVe()); } } } }
mynameco
23.06.2025 13:22еще можно попробовать поиграться с масками, там буквы гласные в таблице в ряд стоят...
navferty
23.06.2025 13:22Нет, в ASCII буквы идут по алфавиту. Но удачно получилось, что все гласные на нечётных позициях
Так что самый младший бит всегда 1. Дальше можно смотреть на пятый с конца бит, который для всех кроме U равен 0.
mynameco
23.06.2025 13:22я имел ввиду, если по 16 сделать столбцы, так чаще и отображают, то там не только буквы гласные в линию разного регистра, но и многие другие гласные в одну линию. посмотрите таблицы, где в столбике 16 символов
mynameco
23.06.2025 13:22я погуглил, максимальное колличество согласных в начале 3 штуки. значит 32 битная маска покроет все случаи. маски нужно две штуки, и накладывать сразу на начало слова, если символов от 3. учитывая 0 в конце. если символов меньше чем 3, то 16 битные маски. если меньшн чем 1 то гласных точно нет.
zuek
23.06.2025 13:22я погуглил, максимальное колличество согласных в начале 3 штуки
Извините, если не совсем правильно Вас понял, но про что данная сентенция? Если про количество согласных в начале слова, то не только сакраментальное "взбзднуть", но и банальное "всплакнуть" нарушают данное правило (не забываем про финальное буквосочетание в слове "длинношеее"). Или Вы имели в виду какой-то конкретный язык с конкретным алфавитом? Мне в этом плане арабская письменность нравится - там всего одна "гласная" буква =)
mynameco
23.06.2025 13:22В итоге получается 3 маски
if ((index & 0b_1101_0111) == 0b_0100_0001 || // A I (index & 0b_1100_1111) == 0b_0100_0101 || // E U (index & 0b_1101_1111) == 0b_0100_1111) // O { Debug.LogError(ch); }mynameco
23.06.2025 13:22в коде указал коментарии заглавными, но сам код конечно и с прописными работает.
думаю такой код хорошо будет работать на совремнных процах. там оптимизации такие же как и у clamp и min и max. т.е. короткие независимые ветки, исполняемые одновременно и потом выкидывание ненужных результатов без сброса конвеера.
ciuafm
23.06.2025 13:22Как минимум на х86 вы ничего не выиграете. Можно побороть большие/маленькие буквы сбросом "case" бита, а потом проверять xor cо значениями сохраненными в байтовых регистрах - на английский должно хватить. Это даст существенный прирост.
Проверяемый текст можно загружать в ммх регистр или 64 бит регистр и постепенно сдвигать вправо проверяя младший байт, насколько я помню можно загрузить левые в памяти байты в младшие регистры. Жаль что в Питоне нельзя ассемблерных вставки.
programania
23.06.2025 13:22Python уже забыл, поэтому попросил qwen2.5-coder-32b-instruct-q4_k_m
написать так, как представляю максимально быстрый способ:"Напиши на python функцию any_gen(s), которая возвращает true,
если в строке s есть гласные буквы: aeiouAEIOU.
При этом для скорости вначале создай массив, в котором в элементе с
номером равным коду гласной буквы стоит true и затем
в цикле по строке s определять гласную букву по этому массиву."LLM эти путанные объяснения правильно поняла и написала
и с русскими комментариями и всё объяснила и тесты написала и всё работает.
Это потрясающе!Jijiki
23.06.2025 13:22скорость упадёт как только добавится к этой задаче "все вхождения сделать все засечки за 1 проход, учитывая все открывания закрывания и весь синтаксис", там будет выбор регекс не 1 проход или не регекс 1 проход с проверками, при этом на больших данных регекс будет поидее не маленький уже, невозможно проверять только гласные(гласные это частный случай)
в этом ребусе ловушка, кажется что можно обойтись без разбития(и даже если просто разбивать неудобно без итераторов передвигаться, но с итераторами как раз можно потерять позицию)), но лучше еврестически связать всю проверку последовательно чем мучаться с регекспом(или отсутствии удобств в виде итератора), там на самом деле не хилый ребус(выбор как удобнее поддерживать будет идею поиска и связи синтаксиса типо, потомучто такое ощущение что гласная это частный случай поиска слова) под капотом
и ИИ будет предлагать именно из-за страха потери символа - эвристики, будет всё делать на регеспе и за несколько проходов
kuza2000
23.06.2025 13:22Да, результаты LLM впечатляют. Такие задачи делает на ура.
Я хочу начат pet-проект с бэком на питоне и фронтом на vue. С питоном я дружу хорошо, а вот во фронтовой части опыта нет, не знаю ни vue, ни js. Попробовал использовать для фронтовой части LLM. В общем, вполне можно работать. Прошу написать компонент, ставлю задачу. На vue делает достаточно хорошо. Потом я вычитываю, проверяю. Что не понятно, спрашиваю. Например, "а вот что означает эта конструкция на js?". LLM подробно объясняет. Что-то немного переделываю. Иногда бывают косяки - в основном, из-за нечеткой постановки. Но вполне можно работать и делать фронт на языке, которого я не знаю) Но опыт разработки должен быть обязательно. Условная "домохозяйка" проект не сделает.В начале просил LLM сделать полностью заготовку проекта (бэк+фронт). Она не справилась. Это сложно. А вот компоненты на vue клепает очень годно)
Sly_tom_cat
23.06.2025 13:22Почему регэксп в питоне быстрее всего другого написанного на питоне? Просто потому что он (в отличии от всего остального) написан на C.
Возьмите C или что-то посвежее, компилируемое в машинный код и там регулярки уже не такие быстрые по факту даже пред-компилированные.
rrran7
23.06.2025 13:22Для ASCII быстрее всего будет завести массив a[255] где каждый элемент 1, если код соответствует гласной и 0 если нет. А дальше просто цикл
CTAJlUH
23.06.2025 13:22Не факт. Массив размером 255 — относительно большой. Если у процессора кеш-линия длиной 256 байт и больше, то к нему требуется только выравнивание, чтобы массив не делился на 2 кеш-линии. Но у большинства процессоров кеш-линия короче 256 байт, что подразумевает априори 2/4/8 запросов в память по сравнению с тем же способом с бит-масками, оперирующими с регистрами и immediate при соответствующем соглашении о вызовах (вне рамок питона). Но это ничего не доказывает само по себе: правда в benchmark'ах. Если вам интересно, можете проверить
vityo
23.06.2025 13:22Y чего нигде нет
Короче зависит от входных данных. Если например гласная редкая, то можно завести массив целых чисел с 26 элементами, использовать очередную букву из строки как индекс элемента массива, и добавлять к элементу 1. А уже в самом конце проверить, что там по индексам 1 5 9 15 21.. это избавит от проверок но зависит от частоты гласных, входных данных
Zara6502
23.06.2025 13:22мне кажется для решения нужно брать статистику по появлению гласных в английском тексте и условия выстраивать по нисходящей. там где это можно - проверять по битовой маске.
а вообще можно в 100% случаев просто возращать true, так как в английском тексте нет слов без гласных ) (во всяком случае я такие не вспомнил)
ИИ:
Да, в английском языке существуют слова, состоящие исключительно из согласных букв. Примеры таких слов включают:
hmm — междометие, выражающее сомнение или размышление ("хмм").
psst — звукоподражательное слово, используемое для привлечения внимания ("псст").
shhh — звукоподражательное слово, означающее призыв к тишине ("ш-ш-ш").
brrr — звукоподражательное слово, выражающее холод ("бр-р-р").
Эти слова часто используются в разговорной речи и письменной форме для передачи звуков или эмоций.
speshuric
23.06.2025 13:22Хм. Если посмотреть на скорость в символах в секунду, то самый быстрый вариант оригинала статьи в его замерах ищет со скоростью порядка 100к симв/сек. Про улучшенный вариант Kranar/a_e_k пишут, что они "быстрее в 10 раз". Миллион символов строк в секунду (если я нигде множитель не пропустил).
Это ж, блин, соревнование улиток какое-то. Скорее всего почти всё время уходит на интерпретатор и движок Python, потому что на C/C++/Rust/C#/Java я бы ожидал скорости порядка 100М-1G симв/сек на реализациях без SIMD и 1-10G для SIMD.
MrFlanker
23.06.2025 13:22Вы искали решение в довольно узкой области, ограничиваясь функциями конкретного языка и ничего не сказали о формате входных данных. Неплохо было бы изучить проблему без привязок к языку в потом уже реализовывать с имеющимися ограничениями.
Даже если предположить что формат входных данных это 8-битовый набор символов ASCII то тема не до конца раскрыта. Нужно изучить положение битов влияющих на требуемый признак символа и подумать можно ли как то более быстро определять гласный он или нет.
Можно задаться вопрос о смене формата данных для более быстрого получения признаков символа изменив кодировку. Но это ещё более широкая задача. Это похоже на построение индексов в БД.
Тем не менее статья интересная.
kuza2000
23.06.2025 13:22Не хватает:
1. Варианта на numpy
2. Варианта с numba
3. Варианта с torch на cpu
4. Варианта с torch на gpu
Возможно, вечером сделаю. Если никто не опередит))kuza2000
23.06.2025 13:22Попробовал 1 и 2. Лидера побить не могут. Основная причина - эти варианты не работают с нативными строками питон, и преобразование съедает весь выигрыш распараллеливания.
- Преобразование в массивы numpy, даже np.frombuffer(b"aeiouAEIOU", dtype=np.uint8) - долго
- Нумба умеет работать сразу с байтовыми массивами. Но с ограничениями, она не может распараллелить операции с ними (
- Ну а учитывая предыдущее, torch пробовать смысла нет
mynameco
23.06.2025 13:22Вот что вычитал. В английском языке буква Y может отвечать как за гласный, так и согласный звук. Все зависит от того, в каком месте слова она находится.
funca
23.06.2025 13:22В английском употребление артиклей a/an зависит от первого звука при произношении, а не буквы: a man, a unicorn/an apple, an honest.
kuza2000
23.06.2025 13:22Кстати, результатами теста не удивляен. Изначально бы ставил на решение от a_e_k . Операция in в питоне наверняка в итоге сводится на машинном коде в инстукцию ассемблера rep scasb. Вряд ли есть что либо более эффективное для одного ядра. Потери тут только в том, что идет отдельный вызов через медленный интерпретатор для каждой гласной.
Но... все предложенные мной варианты в комментарии выше могут использовать несколько ядер cpu или gpu, поэтому у них есть шанс вырваться вперед на больших строках. Вопрос лишь в стоимости накладных расходов при подготовки данных.Jijiki
23.06.2025 13:22стоимость просто замерить и увидеть, надо открыть vulkan_core.h и запустить скан гласных
Sergei_Erjemin
23.06.2025 13:22А еще есть
frozensetНо не думаю, что он будет сильно быстрее обычного ...
Daddy_Cool
23.06.2025 13:22Какие-то не модные решения. Надо было обучить нейросеть-классификатор. Берем датасет строк с гласными, берем датасет без гласных... обучаем ночь на нескольких 4090...
IisNuINu
23.06.2025 13:22самого быстрого способа нахождения гласной в строке - ЗДЕСЬ НЕТ! самый быстрый способ это использование массива, где индексом будет код буквы(ну или его смещение относительно первой буквы алфавита), а элементами логические значения, на месте гласных истина, согласных ложь.
tea_cher
23.06.2025 13:22А в чем смысл продолжения поиска до конца строки после первой встретившейся гласной?
kasthack_phoenix
tl;dr: регулярки в сишном движке быстрее любого кода, написанного на интерпретируемом недоязыке.
Скорее всего, даже не биткарта, а какой-нибудь трюк с avx512, чтобы сканировать 64 байта за такт. SIMDJSON это для парсинга JSON использует.