Elección del algoritmo para el método .indexOf en Java

Question

Estaba viendo la implementación del método de la clase String de Java .indexOf() y parece que el autor del código utiliza el algoritmo de fuerza bruta para buscar la subcadena en una cadena dada. Es decir, el enfoque se ejecuta en O (mn), donde m y n son la longitud de las cadenas fuente y destino, respectivamente.

¿Por qué el autor no utilizó un algoritmo más eficiente como Rabin-Karp, que tiene una complejidad de tiempo de ejecución de O (m + n) si se proporciona una buena función de hash?

Podría estar perdiendo todo el conocimiento detrás del motivo de esta implementación y, por lo tanto, quería entender.

Answer 1

No sé con certeza por qué se tomó esta decisión, pero si puedo adivinar es probablemente porque para cadenas de patrones pequeños (un caso de uso muy común) el ingenuo algoritmo de fuerza bruta es probablemente tan rápido o más rápido que algunos de los algoritmos asintóticamente más rápidos como Rabin-Karp, Boyer-Moore o Knuth-Morris-Pratt. Esto parece ser un algoritmo predeterminado razonable, ya que en muchos casos buscará cadenas pequeñas para patrones pequeños, y la sobrecarga de una configuración de gran alcance probablemente sea comparable al tiempo de ejecución del enfoque ingenuo.

Dicho esto, en ninguna parte de las especificaciones de Java exige el uso de este algoritmo. Podrían haber elegido Rabin-Karp como el algoritmo predeterminado.

Otra razón por la que pueden haber optado por este enfoque es porque si desea realizar búsquedas rápidas de texto, la biblioteca de expresiones regulares proporciona una correspondencia de cadenas más rápida con capacidades de búsqueda más potentes. Proporcionar a los usuarios el algoritmo simple de fuerza bruta de forma predeterminada y la opción de cambiar a un conjunto de herramientas más potente cuando sea necesario parece una buena manera de equilibrar la eficiencia asintótica con la eficacia práctica.

Answer 2

Supongo que quiere decir indexOf o contains en vez de subserver. La subcadena es O (1)

A menudo el código simple se ejecuta más rápido. Código que crea objetos, por ejemplo, a menudo se ejecuta mucho más lento.

¿Por qué no intentas implementarlo por ti mismo y ver si es más rápido? Si es así, puedes sugerir que mejoren el método.

Answer 3

Supongo que no pensaron que la gente lo usaría para cadenas muy grandes. Con una longitud de cuerda inferior a 100, no será muy diferente.

Answer 4

Solo supongo, pero recuerde que Java String se almacenan como UTF-16 por razones i18n, no como 8 bits ASCII. Podría ser que el soporte de algunos algorthims en UTF-16 (y el más difícil UTF-8) podría ser problemático. Sólo una suposición, sin embargo.