Swift 3: le moyen le plus performant de vérifier de nombreuses chaînes avec de nombreuses expressions régulières

Question

J'ai une liste de plusieurs centaines de chaînes et un tableau de 10k expressions régulières.

Je dois maintenant parcourir toutes les chaînes et vérifier laquelle des 10 expressions régulières correspond. Quelle est la manière la plus performante de le faire?

Actuellement, je fais ceci:

myRegularExpression.firstMatch(in: myString, options: myMatchingOption, range: NSMakeRange(0, myString.characters.count)) == nil 

où myRegularExpression est un NSRegularExpression stocké pour la réutilisation et myMatchingOption est NSRegularExpression.MatchingOptions(rawValue: 0)

Y at-il un moyen plus rapide, plus performant moyen de vérifier si une chaîne correspond à ces 10k expressions régulières?

EDIT:

Je dois savoir non seulement si l'un de mes 10k expressions régulières en forme, mais aussi que l'on. Donc, actuellement, j'ai une boucle for à l'intérieur d'une boucle for: l'externe itère sur mes centaines de cordes et pour chacune de ces cordes je passe en revue mes règles 10k et voir si une règle convient (bien sûr, je peux arrêter pour cette chaîne, donc à peu près:

for string in stringsToCheck { 
    for rule in myRules { 
     if string.matches(rule) { 
      // continue with next string of stringsToCheck 
     } 
    } 
} 

Answer 1

en fonction de la plate-forme que vous utilisez ce sur, séparer le travail en utilisant plusieurs threads peuvent fournir des améliorations de temps de réponse, mais je crois que l'optimisation vraiment dramatique pour cela nécessiterait un certain Par exemple, si les expressions n'ont pas d'ordre de priorité spécifique, vous pouvez les réorganiser (les réorganiser) pour créer les correspondances les plus probables. e premier de la liste. Cela pourrait être évalué de manière préemptive soit par le fournisseur des expressions, soit en utilisant une certaine fonction pour estimer leur complexité (par exemple la longueur de l'expression, la présence de symboles optionnels ou combinatoires). Il est également possible de l'évaluer statistiquement en collectant (et en conservant) le nombre de succès/pertes pour chaque expression. Mais bien sûr, une telle optimisation suppose que chaque chaîne correspondra à au moins une expression et que la règle 80/20 s'applique (c'est-à-dire que 20% des expressions correspondent à 80% des chaînes).

Si les expressions sont très simples et n'utilisent que des modèles de lettres, vous obtiendrez de meilleures performances avec plus d'implémentations "manuelles" des fonctions correspondantes (au lieu de regex). Dans le meilleur des cas, les modèles de lettres simples peuvent être convertis en un arbre de caractères et donner des ordres de grandeur dans les améliorations de performance.

Notez que ces solutions ne sont pas mutuellement exclusives. Par exemple, si une grande partie des expressions sont des motifs simples et que seulement quelques-uns ont des motifs complexes, vous n'avez pas à jeter le bébé avec l'eau du bain: vous pouvez appliquer l'optimisation du motif simple à un sous-ensemble de règles et utilisez la boucle imbriquée "brute force" pour les complexes complexes restants.

J'ai eu un problème similaire dans le passé où des milliers de règles devaient être appliquées sur des centaines de milliers d'enregistrements pour le traitement des réclamations d'assurance. L'approche traditionnelle du «système expert» consistait à créer une liste de règles et à faire passer tous les enregistrements. Évidemment, cela prendrait un temps ridicule (comme 2 mois d'exécution pour traiter un mois de réclamations). En y regardant dans un état d'esprit moins que «puriste», j'ai pu convaincre mon client que les règles devaient être définies de manière hiérarchique. Nous les avons donc divisés en un ensemble de règles d'admissibilité et un ensemble de règles de décision. Ensuite, nous avons peaufiné la structure en créant des groupes d'admissibilité et des groupes de décision.Nous nous sommes retrouvés avec une structure arborescente grossière dans laquelle les règles permettaient au système de réduire le nombre de règles à appliquer à un enregistrement donné. Avec cela, le temps de traitement de 6 semaines pour 250 000 enregistrements a été réduit à 7 heures (c'était en 1988). Tout ceci pour dire que revenir à la nature du problème à résoudre peut fournir des opportunités d'optimisation qui ne sont pas visibles lorsqu'on regarde simplement la mécanique d'une option de processus.