Когда мне нужно проверить предыдущее появление какого-либо элемента, я использую словарь. В большинстве случаев. Но в процессе проверки кода я обнаружил, что товарищи по команде используют строку для хранения данных и просто используют «если X в строке» для проверки предыдущего вхождения.
Я уже начал чесаться, мне нужно было знать разницу в терминах сложности. После исследования я обнаружил, что строковый модуль Python использует комбинацию алгоритмов Boyer-Moore и Horspool для поиска подстроки. Просто хорошо, теперь я знал названия алгоритмов. Вы можете увидеть код здесь.
Давайте попробуем сравнить строковый и словарный оператор «in» Python для нашего случая.
Я написал это просто для удовольствия, и рассматриваю только мой практический случай. Буду рад, если вы расскажете мне о моих ошибках.
Ввод, у нас есть длинная строка и короткая строка.
len(длинная строка)/5 = len(короткая строка)
Мы попробуем найти персонажа. Также мы создадим словарь из наших длинных строк, каждый символ является ключевым, а значение равно 0. Словарь будет кратчайшим, чем строка. Например:
long_string='Привет всем'
dict = {'H': 0, 'e': 0, 'l': 0, 'o': 0, ' ': 0, 'v': 0, 'r': 0, 'y': 0, 'н': 0}
В лучшем случае попробуем найти первую букву Н. Это должен быть более быстрый случай для поиска строки и, как правило, 0 (1) случай в словаре. Найти первую букву не должно зависеть от длины строки. Код можно посмотреть здесь
Ага. Все работает, как я и ожидал.
Худший случай. Попробуем найти последний символ из строки, время работы должно зависеть от длины строки. А как мы знаем, операция доступа к словарю не зависит от количества элементов. Но Питон умнее меня. Я должен выбрать уникальный символ и поместить его в конец строки. Я использовал заглавные буквы для строки. Код здесь
Сначала я пытался использовать «#» в качестве уникального символа, это работает очень хорошо:
И я не обнаружил строковый «тяжелый» алгоритм поиска. Длинная струна в 5 раз длиннее короткой, но время работы было таким же.
Когда я выбрал экзотический символ UTF-16 «ы», время работы стало таким, как я ожидал:
Мое резюме:
В моей работе инженером по инфраструктуре, когда мы создаем внутренние инструменты, нет большой разницы, какой поиск используется. Поиск в словаре или в строке. Мы работаем только с символами ASCII и короткими строками.
P.S: да, я понимаю разницу, если мы будем работать с более длинными строками, чем строки символов.
Я свободен для обсуждения и буду бороться за правду. :)
