Kami menulis pencarian substring lebih baik daripada di buku teks

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

Ini adalah awal dari serangkaian beberapa artikel milik penulis mereka, Linas Medžiūnas , dan awalnya diterbitkan di blog WiX Engineering .

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

Knut-Morris-Pratt (Algoritma KMP)

Algoritma pencarian biner substring

  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

Tolak ukur

Atas saran Vladimir Sitnikov , saya menambahkan hasil benchmark untuk java.util.regex.Pattern, ia menggunakan algoritma Boyer-Moore di bawah tenda.

Hasil benchmark

• Untuk data biasa, ia mendominasi javaIndexOf, karena ia menggunakan intrinsik berkinerja tinggi di dalamnya, karena bagian konstannya kecil;
• , : , (O(nm)) javaIndexOf, — , shiftingBitMask ( ) .
• guavaIndexOf , javaIndexOf; , 2 , shiftingBitMask;
• scalaIndexOfSlice - , knuthMorrisPratt, , — , ;
• kinerja bukan fitur terkuat ahoCorasic(atau setidaknya implementasinya; saya harus mengakui bahwa saya tidak benar-benar mencoba membuat optimasi mikro di dalamnya, karena saya menambahkannya hanya karena fitur yang membedakan: kemampuan untuk mencari di beberapa baris sekaligus, dan ini mirip dengan topik untuk artikel terpisah);
• input data (dan panjang needle) tidak mempengaruhi kinerja shiftingBitMaskdan ahoCorasic.

temuan

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