نكتب البحث في السلاسل الفرعية أفضل من الكتب المدرسية

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

هذه هي بداية سلسلة من عدة مقالات مجاملة من مؤلفها ، Linas Medžiūnas ، ونشرت في الأصل على مدونة WiX Engineering .

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

كنوت موريس برات (خوارزمية KMP)

خوارزمية بحث سلسلة فرعية ثنائية

  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

المعايير

بناء على اقتراح فلاديمير سيتنيكوف ، أضفت نتائج مرجعية لـ java.util.regex.Pattern؛ يستخدم خوارزمية Boyer-Moore تحت غطاء المحرك.

نتائج قياس الأداء

• بالنسبة للبيانات العادية ، فهي تهيمن javaIndexOf، لأنها تستخدم الجوهر الداخلي عالي الأداء ، حيث يكون الجزء الثابت صغيرًا ؛
• , : , (O(nm)) javaIndexOf, — , shiftingBitMask ( ) .
• guavaIndexOf , javaIndexOf; , 2 , shiftingBitMask;
• scalaIndexOfSlice - , knuthMorrisPratt, , — , ;
• الأداء ليس أقوى ميزة ahoCorasic(أو على الأقل تنفيذه ؛ يجب أن أعترف بأنني لم أحاول فعلًا إجراء التحسينات الدقيقة فيه ، لأنني أضفته فقط بسبب ميزته المميزة: القدرة على البحث عبر عدة أسطر في وقت واحد ، وهذا على غرار موضوع مقال منفصل) ؛
• بيانات الإدخال (والطول needle) لم تؤثر على الأداء shiftingBitMaskو ahoCorasic.

الموجودات

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