Выбор алгоритма для метода .indexOf в Java

Question

Я только что посмотрел на реализацию метода .indexOf() класса Java String, и кажется, что автор кода использует алгоритм перебора для поиска подстроки в данной строке. То есть подход выполняется в O (mn), где m и n - длина исходной и целевой строк соответственно.

Почему автор не использовал более эффективный алгоритм, такой как Рабин-Карп, который имеет сложность времени выполнения O (m + n), если предоставляется хорошая хеш-функция?

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

Answer 1

Я не знаю наверняка, почему было принято это решение, но, если предположить, возможно, это потому, что для небольших строк шаблонов (очень распространенный случай использования) алгоритм наивной грубой силы, вероятно, такой же быстрый, если не быстрее, чем некоторыеиз асимптотически более быстрых алгоритмов, таких как Рабин-Карп, Бойер-Мур или Кнут-Моррис-Пратт.Это похоже на разумный алгоритм по умолчанию, так как во многих случаях вы будете искать небольшие шаблоны для небольших шаблонов, и издержки от мощной согласованной установки, вероятно, будут сопоставимы с временем выполнения наивного подхода.

Это сказалонигде в спецификации Java не предусмотрено использование этого алгоритма.Они могли бы так же легко выбрать Рабина-Карпа, как алгоритм по умолчанию.

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

Answer 2

Я предполагаю, что вы имеете в виду indexOf или содержит вместо подстроки. Подстрока O (1)

Часто простой код работает быстрее. Например, код, который создает объекты, часто работает намного медленнее.

Почему бы вам не попробовать реализовать это для себя и посмотреть, быстрее ли это. Если это так, вы можете предложить, чтобы они улучшили метод.

Answer 3

Просто предположение, но помните, что Java String хранится как UTF-16 по причинам i18n, а не просто 8-битным ASCII.Вполне возможно, что поддержка некоторых алгоритмов на UTF-16 (и на более сложных UTF-8) может быть проблематичной.Просто предположение, хотя.

Answer 4

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