Get best of the week

Nous écrivons mieux la recherche de sous-chaînes que dans les manuels



La vie d'un ingénieur est pleine de surprises: surtout quand il faut faire face à la productivité. Par exemple, que se passe-t-il si vous essayez d'exécuter ce morceau de code Java? Cela semble assez innocent:

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

Nous attendons, attendons, attendons ... Au moins sur mon ordinateur portable OpenJDK 13 2015, trouver une aiguille dans une botte de foin prend environ une minute. Notre bonne vieille machine virtuelle Java a traversé des décennies de réglage des performances, elle a effectivement mis en œuvre des intrinsèques pour String.indexOfetc. Qu'est-ce qui aurait pu mal tourner?
C'est le début d'une série de plusieurs articles gracieuseté de leur auteur, Linas Medžiūnas , et initialement publiés sur le blog WiX Engineering .


Examinez de plus près ce qui est entré: les données sont spécialement sélectionnées de manière à obtenir des performances quadratiques dans le pire des cas ( O(nm)où nest la longueur haystacket mest la longueur needle) pour l'algorithme de recherche de sous-chaîne naïve. Nous parcourons tous les caractères dans haystack, et s'ils coïncident avec les premiers caractères needle, nous commençons à courir le long needlede la boucle intérieure - et ainsi de suite jusqu'au premier caractère incompatible.

Vous pouvez faire valoir que cet exemple est inutile, car ces données d'entrée ont été conçues et archivées spécialement, dans la pratique, vous ne rencontrerez pas cela. Réfléchissez bien. Que faire si vous travaillez sur un service Web dont les utilisateurs peuvent charger des chaînes arbitraires, et quelque part à l'arrière du service, il y a du code qui s'exécuteindexOfsur ces lignes? Ensuite, quelques requêtes malveillantes comme celle ci-dessus mettront votre service à genoux. Il vaut la peine de connaître, au moins, les pires cas pour les données d'entrée.

Heureusement, il existe des algorithmes de recherche de sous - chaînes ayant une complexité linéaire ( O(n+m)). Ils n'ont aucun problème avec les données de l'exemple ci-dessus. Par exemple, le code Scala suivant fait la même chose, mais s'exécute en millisecondes sur le même ordinateur, la même machine virtuelle Java et en utilisant exactement la même chose sous le capot java.lang.String:

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

Le secret de l'énorme différence réside dans la méthode indexOfSlice, qui fait partie de la bibliothèque standard de Scala . Il implémente l'algorithme linéaire intelligent Knut-Morris-Pratt . Et non, je ne dis pas que la langue X est meilleure que la langue Y. Malheureusement, tout est beaucoup plus compliqué ici! Par exemple, indexOfSlicedans Scala, il s'agit d'une méthode généralisée qui fonctionne non seulement avec des chaînes, mais également dans d'autres collections séquentielles, et peut comparer non seulement des caractères, mais également des éléments d'autres types. Cela devrait être beaucoup plus lent queString.indexOfde Java dans le cas du milieu (nous en parlerons plus tard). Ainsi, nous avons un algorithme efficace avec de bien meilleures performances dans le pire des cas, mais en moyenne, il est plus lent car il a une partie constante beaucoup plus grande. Des dilemmes comme celui-ci sont un problème typique de réglage des performances. Il n'y a pas de pilule magique qui résoudra tous les problèmes - vous devez analyser attentivement le problème et faire les bons micro-repères.


Es-tu encore avec moi Bien! Vous voyez, ce n'est qu'une introduction. Je voulais vous motiver à gérer la complexité théorique et les performances pratiques des algorithmes. Dans la suite de cet article, nous verrons quelques implémentations de plusieurs algorithmes de recherche de sous-chaînes et leurs benchmarks.

Nous allons explorer trois algorithmes de recherche de sous-chaîne. Tous fonctionnent en temps linéaire et nécessitent un prétraitement, linéairement dépendant de la longueur needle. Le calcul de la même chose needlen'est requis qu'une seule fois, puis il peut être réutilisé dans plusieurs tentatives de recherche. C'est raisonnable, car dans de nombreux cas, nous devons rechercher la même ligne encore et encore. Et même si nous ne le faisons pas, le précalcul n'est pas une opération particulièrement coûteuse.

Tous les algorithmes ci-dessous contournent chacun des caractères dehaystackune seule fois de suite (pas d'accès aléatoire par index), donc ils fonctionnent tous bien en mode streaming. Cet article est survenu au cours d'un travail réel sur un serveur proxy pour la production basé sur le cadre Netty , et cela a influencé certaines des décisions de conception d'API. De plus, comme nous avions besoin de faire une recherche sur les tampons d'octets, le code fonctionnera avec Byte, pas avec Char.


Knut-Morris-Pratt (algorithme KMP)


Il s'agit d'un algorithme de recherche de sous-chaîne bien connu datant des années 70 du siècle dernier. Il est bien décrit dans la littérature , donc je ne le décrirai pas ici en détail. L'ILC est basé sur des machines à états - pendant la phase de calcul préliminaire, un tableau d'indices de liens est construit sur la base de needle. Pendant la recherche, la machine accepte les caractères haystackun par un à l'entrée et met à jour son état interne en conséquence (et l'état il n'y a qu'un index dans la table des relations).

Voici une implémentation sur Scala .

Algorithme de recherche de sous-chaîne binaire


Au départ, j'ai dû inventer indépendamment le nom de cet algorithme: je n'ai jamais rien vu de tel nulle part dans la littérature. En conséquence, je suis venu au nom de "Shifting Bit Mask". Plus tard, il s'est avéré que cet algorithme et ses variations étaient connus depuis 1964 sous divers noms anglais comme «Bitap», «Shift-or», «Shift-and», «Baeza-Yates - Gonnet». Merci aux lecteurs qui l'ont trouvé pour moi. Cet article a été écrit bien avant cette nouvelle.

Cet algorithme est basé sur une idée très simple et fonctionne très bien, car il n'y a presque pas de sauts, et il est basé sur plusieurs opérations binaires primitives. De ce fait, il a une limite sur la longueur que needlenous allons rechercher: il ne peut pas dépasser 64 octets. Ce nombre a été pris simplement par le nombre de bitsLongdans la JVM. Cette limitation est suffisamment généreuse pour un grand nombre de tâches réelles.

Comme j'ai développé moi-même cet algorithme à l'origine, je vais essayer d'en parler plus en détail. Tout d'abord, nous pré-calculons le contexte de recherche pour celui souhaité needle:

  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
  }

Nous pré-calculons bitMask(64 bits Long) pour chaque valeur d'octet possible (256 pièces bitMask). Pour une valeur d'octet X, il bitmaskcontient contient des unités à tous les endroits où il se Xtrouve needle. Par exemple, voici un petit masque pour la chaîne "abracadabra": De plus, vous devez pré-calculer , ce qui aidera à comprendre que nous avons trouvé une correspondance exacte. Cela ressemble à une valeur , avec un peu en position :



successBitMaskLong1needle.length — 1

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

Et enfin, vous devez faire, en fait, une recherche. Le seul état mutable que nous voulons stocker est currentMask( Long). Pour chaque octet, haystacknous décalons currentMaskd'un 1bit vers la gauche , définissons son bit le moins significatif 1et faisons un bit andentre le résultat et bitMask, calculé pour la valeur d'octet traitée actuelle de haystack(cela andefface tous les bits aux endroits currentMaskqui ne correspondent pas à l'octet traité actuel).

Ainsi, après le traitement de chaque octet, seuls les bits qui se trouvent dans des positions appropriées survivront. Et avec chaque octet traité, tous les bits sont décalés vers la gauche d'une position. Si le bit "survit" pendant le nombre d'itérations égal à la longueurneedle- nous avons trouvé un match! Et nous pouvons le vérifier avec successBitMask:

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

Remarque: la méthode décrite ci-dessus renvoie falsesi quelque chose est trouvé, et cela semble contre-intuitif. Cela peut être compris de sorte que la valeur truesignifie la nécessité de poursuivre la recherche, mais l' falsearrête - cela est dû au fait que, comme je l'ai écrit ci-dessus, l' API a été rendue compatible avec Netty. Si vous vous demandez comment exécuter une recherche, voici un exemple.

En conséquence, toute la logique se résume à quelques instructions simples du processeur. Malheureusement, il reste une vérification complètement inutile des limites des index du tableau bitMasks, qu'aucun JDK ne peut supprimer (et j'ai regardé l'assembleur généré par plusieurs JDK différents).

Voici l' implémentation complète sur Scala .

Aho korasik


Il s'agit d'un autre algorithme populaire connu depuis 1975. Sa caractéristique distinctive (et parfois très utile) est la possibilité d'en rechercher plusieurs needleen même temps, tandis que tous les caractères de haystacksont contournés une seule fois (je pense que c'est tout simplement génial!). L'idée que tout cela fonctionne est une extension de l'algorithme KMP, une machine à états finis utilisant un arbre de préfixe (qui est construit sur la base de plusieurs needle), contenant des liens vers des liens (comparer avec un tableau unidimensionnel du KMP). Sur la base de ces liens, l'état interne de l'automate est commuté entre les nœuds de l'arbre de préfixe après chaque symbole traité, et certains des nœuds indiquent un résultat de recherche positif pour un particulierneedle. La phase de précalcul ici est assez compliquée, mais la phase de recherche est d'une simplicité inattendue.

Voici un lien vers une implémentation de travail sur Scala .


Il s'agissait d'une liste complètement incomplète d'algorithmes de recherche de sous-chaîne. Nous avons également essayé l' algorithme Rabin-Karp et l'algorithme Boyer-Moore . De ces deux, Boyer-Moore a montré des performances comparables, mais ils ne sont pas tous deux compatibles avec le streaming (en utilisant un accès aléatoire haystackpar index), et je les ai donc supprimés de cette enquête.


Repères


Nous comparerons les trois algorithmes décrits ci-dessus et, en outre, examinerons les résultats des méthodes String.indexOf(Java) et indexOfSlice(Scala). Pour être honnête, ce n'est pas une comparaison complètement correcte, car cela String.indexOffonctionne avec des chaînes, et toutes les autres méthodes sont sur des tableaux d'octets. Mais cela ne semble pas invalider les résultats d'une telle comparaison. De plus, j'ai également inclus les résultats Bytes.indexOfde Guava (v.28.1). Cette méthode fonctionne sur des tableaux d'octets. Et ils l'ont écrit sur Google - tout ce qu'ils y écrivent fonctionne très vite, non?

L'écriture de repères est toujours difficile, car vous pouvez envoyer des données complètement différentes à l'entrée, les modifier de différentes manières - non seulement en longueur needleethaystack, mais aussi par le contenu interne de ces lignes (qui peut grandement affecter certains algorithmes). En pratique, il vaut toujours la peine de vérifier les données d'entrée qui sont les plus similaires aux données de vos tâches réelles (c'est ce que nous avons fait dans notre projet).

Pour raccourcir cet article, j'ai utilisé seulement 2 types d'entrées. L'un d'eux est destiné à refléter le cas réel: haystackenviron 1,5 Ko de taille (avec du texte lisible par l'homme à l'intérieur) needle- 9 octets, et pas dans haystackcette séquence (cela est nécessaire pour forcer l'algorithme à effectuer une analyse complète).

Un autre type d'entrée est nécessaire pour obtenir le comportement le plus défavorable d'un algorithme quadratique. C'est beaucoup plus court que les données du tout début de cet article: sinon il faudrait attendre une minute entière, tu te souviens? Arrayhaystackest défini dans le format "AA...AAB"(la même longueur que le premier type de données), et needle- 64 octets (en particulier pour l'algorithme de recherche de sous-chaîne binaire pour y faire face) un tableau du même type (la correspondance n'est qu'à la toute fin haystack).

Un benchmark écrit dans le cadre JMH peut être trouvé ici . Si vous avez d'autres idées sur quoi et comment mesurer ici - vous pouvez cloner ce référentiel, modifier quelque chose et publier des commentaires.

À la suggestion de Vladimir Sitnikov , j'ai ajouté des résultats de référence pour java.util.regex.Pattern; il utilise l'algorithme de Boyer-Moore sous le capot.


(Note du traducteur: à propos, Vladimir Sitnikov est membre de plusieurs comités de programme du groupe JUG Ru et fait lui-même des rapports intéressants. Par exemple, une vidéo de son rapport de JPoint 2019 intitulée «Java ralentit: édition CodeCache» est disponible sur le lien ).

Résultats de référence


Les résultats sont donnés en millisecondes, moins c'est mieux: Ici tout est comme prévu:

# JMH version: 1.21
# VM version: JDK 13.0.1, OpenJDK 64-Bit Server VM, 13.0.1+9
Benchmark (searchInput) Mode Cnt Score Error Units
javaIndexOf REGULAR avgt 5 0.622 ± 0.002 us/op
shiftingBitMask REGULAR avgt 5 1.982 ± 0.017 us/op
regexPattern REGULAR avgt 5 2.184 ± 0.006 us/op
kmp REGULAR avgt 5 2.635 ± 0.016 us/op
scalaIndexOfSlice REGULAR avgt 5 3.202 ± 0.009 us/op
guavaIndexOf REGULAR avgt 5 3.696 ± 0.095 us/op
ahoCorasic REGULAR avgt 5 7.063 ± 0.040 us/op
shiftingBitMask WORST_CASE avgt 5 1.986 ± 0.010 us/op
kmp WORST_CASE avgt 5 5.120 ± 0.006 us/op
ahoCorasic WORST_CASE avgt 5 6.892 ± 0.025 us/op
scalaIndexOfSlice WORST_CASE avgt 5 8.765 ± 0.007 us/op
regexPattern WORST_CASE avgt 5 11.566 ± 0.086 us/op
javaIndexOf WORST_CASE avgt 5 23.029 ± 0.124 us/op
guavaIndexOf WORST_CASE avgt 5 52.927 ± 0.275 us/op



  • Pour les données ordinaires, il domine javaIndexOf, car il utilise des intrinsèques hautes performances à l'intérieur, à cause desquels la partie constante est petite;
  • , : , (O(nm)) javaIndexOf, — , shiftingBitMask ( ) .
  • guavaIndexOf , javaIndexOf; , 2 , shiftingBitMask;
  • scalaIndexOfSlice - , knuthMorrisPratt, , — , ;
  • la performance n'est pas la caractéristique la plus forte ahoCorasic(ou au moins de sa mise en œuvre; je dois admettre que je n'ai pas vraiment essayé d'y faire des microoptimisations, car je ne l'ai ajoutée qu'en raison de sa caractéristique distinctive: la possibilité de rechercher sur plusieurs lignes à la fois, et similaire au sujet d'un article séparé);
  • les données d'entrée (et la longueur needle) n'ont pas affecté les performances shiftingBitMasket ahoCorasic.

résultats


Dans différents cas, les repères peuvent fonctionner de différentes manières. Malgré le fait que les résultats ci-dessus semblent très indicatifs, vous devez toujours prendre des mesures vous-même et sur des données qui reflètent vos tâches réelles.

Sur la base des données présentées, j'ai tiré les conclusions suivantes:

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

C'est tout! Si vous aimez lire sur les algorithmes, les performances, etc. (ainsi que sur Scala, JVM et Java en général), abonnez-vous à l'auteur de cet article, Linas Medziunas ( Medium , Twitter ).

Le référentiel github avec tout le code de cet article est ici .


Les traductions d'articles sont publiées avec le soutien du groupe JUG Ru et de la conférence JPoint .

More articles:


All Articles