#algorithm #search
Вопрос:
Каков наилучший подход к поиску одного символа в строке из миллиона символов? Это больше с алгоритмической точки зрения, чем как это сделать с помощью определенного языка программирования?
Является ли бинарный поиск хорошим подходом?
Комментарии:
1. Пожалуйста, поделитесь более подробной информацией. Как двоичный поиск должен помочь в этом случае? Отсортирована ли более длинная строка, чтобы в конце концов можно было использовать двоичный поиск?
2. Если предварительная обработка не разрешена, есть только один способ: грубая сила (попробуйте все символы).
3. @NicoHaase: если я правильно прочитал, там всего одна строка.
4. @YvesDaoust да, я тоже так понимаю. И именно поэтому я спросил о более подробной информации об этой строке
5. @NicoHaase: Меня ввела в заблуждение ваша «длинная строка».
Ответ №1:
Без предварительной обработки сканируйте строку до тех пор, пока не встретите целевой символ. Если вам нужно только проверить наличие или местоположение первого экземпляра, вы закончили. В противном случае вам нужно сканировать до конца.
С предварительной обработкой
- если вам нужно сообщить о наличии или количестве, сформируйте гистограмму (количество экземпляров для каждого возможного значения); это можно сделать за один проход (с возможным досрочным прекращением, если количество не требуется). Затем запрос выполняется в постоянное время.
- если вам нужно сообщить о первом экземпляре (или некоторых), заполните таблицу индексов первого появления для каждого значения символа; это можно сделать за один проход (с возможным досрочным завершением). Затем запрос выполняется в постоянное время.
- если вам нужно сообщить обо всех экземплярах, вы можете предварительно заполнить связанные списки всех экземпляров каждого символа; это можно сделать за один проход, но стоимость хранения высока (одна ссылка на символ). Затем запрос выполняется за время, пропорциональное количеству вхождений.
Обратите внимание, что сортировка с помощью общей сортировки, а затем ответы на запросы с помощью двоичного поиска-это, вероятно, худшее, что вы можете сделать. Общая сортировка будет более дорогостоящей, чем необходимо (N Log(N) вместо N), а запросы будут дорогостоящими (Log(N) вместо 1). Не считая того, что если вам нужна информация о местоположении, вам придется дополнить строку дополнительным полем перед сортировкой.
Если известно, что символы в строке расположены в отсортированном порядке (довольно маловероятная ситуация!), ответ будет другим:
- если вам нужно выполнить запрос только один раз, используйте дихотомический поиск (два, если вас спрашивают количество или диапазон, в котором найден символ).
- если вам нужно выполнить больше запросов (по крайней мере, S Log(S), где S-размер алфавита), вы можете разделить диапазоны равных символов серией дихотомических поисков.
Ответ №2:
Пусть L — длина строки, а S — размер алфавита.
Без предварительной обработки вам нужен последовательный поиск. Потребуется несколько сравнений, равных позиции первого вхождения целевого символа (или L, если он отсутствует). Наилучший случай 1, наихудший случай L, средний случай LS/K (для равномерного и сбалансированного распределения с K вхождениями целевого символа).
При предварительной обработке вы заполняете таблицу присутствия путем последовательного сканирования строки. Количество сравнений символов будет равно «последнему» первому вхождению любого символа (или L, если он отсутствует). В лучшем случае S, в худшем случае L. Требуется дополнительное хранение S-битов. Последующие запросы выполняются в постоянное время.