Escribimos la búsqueda de subcadenas mejor que en los libros de texto

//   String.repeat  JDK 11  :
final var needle = "A".repeat(500000) + "B";
final var haystack = "A".repeat(1000000) + "B";
System.out.println(haystack.indexOf(needle));

Este es el comienzo de una serie de varios artículos por cortesía de su autor, Linas Medžiūnas , y originalmente publicados en el blog de Ingeniería de WiX .

val needle = "A" * 500000 + "B"
val haystack = "A" * 1000000 + "B"
println(haystack.indexOfSlice(needle))

Knut-Morris-Pratt (algoritmo KMP)

Algoritmo de búsqueda de subcadena binaria

  def computeBitMasks(needle: Array[Byte]): Array[Long] = {
    require(needle.length <= 64, "Maximum supported search pattern length is 64.")
    val bitMasks = Array.ofDim[Long](256)
    var bit = 1L
    for (c <- needle) {
      bitMasks(toUnsignedInt(c)) |= bit
      bit <<= 1
    }
    bitMasks
  }

  def computeSuccessBitMask(needle: Array[Byte]): Long = {
    1L << (needle.length - 1)
  }

  def process(value: Byte): Boolean = {
    currentMask = ((currentMask << 1) | 1) & bitMasks(toUnsignedInt(value))
    (currentMask & successBitMask) == 0
  }

Aho korasik

Puntos de referencia

A sugerencia de Vladimir Sitnikov , agregué resultados de referencia para java.util.regex.Pattern; él usa el algoritmo Boyer-Moore bajo el capó.

Resultados de referencia

• Para los datos ordinarios, domina javaIndexOf, porque utiliza intrínsecos de alto rendimiento en su interior, por lo que la parte constante es pequeña;
• , : , (O(nm)) javaIndexOf, — , shiftingBitMask ( ) .
• guavaIndexOf , javaIndexOf; , 2 , shiftingBitMask;
• scalaIndexOfSlice - , knuthMorrisPratt, , — , ;
• el rendimiento no es la característica más fuerte ahoCorasic(o al menos de su implementación; debo admitir que realmente no intenté hacer microoptimizaciones en él, porque lo agregué solo por su característica distintiva: la capacidad de buscar en varias líneas a la vez, y esto similar al tema para un artículo separado);
• los datos de entrada (y la longitud needle) no afectaron el rendimiento shiftingBitMasky ahoCorasic.

recomendaciones

• String- , , String.indexOf ( java.util.regex.Pattern — );
• , needle 64 , ;
• , --;
• Scala - ( ), indexOfSlice — ;
• , -.