Le moyen le plus rapide de vérifier si une chaîne correspond à une expression rationnelle en ruby?

Question 1

Quel est le moyen le plus rapide de vérifier si une chaîne correspond à une expression régulière dans Ruby?

Mon problème est que je dois "egrep" à travers une énorme liste de chaînes pour trouver celles qui correspondent à une expression rationnelle donnée au moment de l'exécution. Je me soucie seulement de savoir si la chaîne correspond à l'expression rationnelle, pas où elle correspond, ni quel est le contenu des groupes correspondants. J'espère que cette hypothèse peut être utilisée pour réduire le temps que mon code passe à faire correspondre les expressions rationnelles.

Je charge l'expression rationnelle avec

pattern = Regexp.new(ptx).freeze

J'ai trouvé que string =~ patternc'est légèrement plus rapide que string.match(pattern).

Existe-t-il d'autres astuces ou raccourcis qui peuvent être utilisés pour rendre ce test encore plus rapide?

Question 2

À partir de Ruby 2.4.0, vous pouvez utiliser RegExp#match?:

pattern.match?(string)

Regexp#match?est explicitement répertorié comme une amélioration des performances dans les notes de publication de la version 2.4.0 , car il évite les allocations d'objets effectuées par d'autres méthodes telles que Regexp#matchet =~:

Regexp # match?
Ajouté Regexp#match?, qui exécute une correspondance de regexp sans créer un objet de référence arrière et changer $~pour réduire l'allocation d'objets.

Question 3

Ceci est une simple référence:

require 'benchmark'

"test123" =~ /1/
=> 4
Benchmark.measure{ 1000000.times { "test123" =~ /1/ } }
=>   0.610000   0.000000   0.610000 (  0.578133)

"test123"[/1/]
=> "1"
Benchmark.measure{ 1000000.times { "test123"[/1/] } }
=>   0.718000   0.000000   0.718000 (  0.750010)

irb(main):019:0> "test123".match(/1/)
=> #<MatchData "1">
Benchmark.measure{ 1000000.times { "test123".match(/1/) } }
=>   1.703000   0.000000   1.703000 (  1.578146)

Donc, =~c'est plus rapide mais cela dépend de ce que vous voulez avoir comme valeur renvoyée. Si vous voulez juste vérifier si le texte contient une expression régulière ou ne pas utiliser=~

Question 4

C'est la référence que j'ai exécutée après avoir trouvé quelques articles sur le net.

Avec la version 2.4.0, le gagnant est re.match?(str)(comme le suggère @ wiktor-stribiżew), sur les versions précédentes, re =~ strsemble être le plus rapide, bien qu'il str =~ resoit presque aussi rapide.

#!/usr/bin/env ruby
require 'benchmark'

str = "aacaabc"
re = Regexp.new('a+b').freeze

N = 4_000_000

Benchmark.bm do |b|
    b.report("str.match re\t") { N.times { str.match re } }
    b.report("str =~ re\t")    { N.times { str =~ re } }
    b.report("str[re]  \t")    { N.times { str[re] } }
    b.report("re =~ str\t")    { N.times { re =~ str } }
    b.report("re.match str\t") { N.times { re.match str } }
    if re.respond_to?(:match?)
        b.report("re.match? str\t") { N.times { re.match? str } }
    end
end

Résultats IRM 1.9.3-o551:

$ ./bench-re.rb  | sort -t $'\t' -k 2
       user     system      total        real
re =~ str         2.390000   0.000000   2.390000 (  2.397331)
str =~ re         2.450000   0.000000   2.450000 (  2.446893)
str[re]           2.940000   0.010000   2.950000 (  2.941666)
re.match str      3.620000   0.000000   3.620000 (  3.619922)
str.match re      4.180000   0.000000   4.180000 (  4.180083)

Résultats IRM 2.1.5:

$ ./bench-re.rb  | sort -t $'\t' -k 2
       user     system      total        real
re =~ str         1.150000   0.000000   1.150000 (  1.144880)
str =~ re         1.160000   0.000000   1.160000 (  1.150691)
str[re]           1.330000   0.000000   1.330000 (  1.337064)
re.match str      2.250000   0.000000   2.250000 (  2.255142)
str.match re      2.270000   0.000000   2.270000 (  2.270948)

Résultats IRM 2.3.3 (il y a une régression dans l'appariement des regex, semble-t-il):

$ ./bench-re.rb  | sort -t $'\t' -k 2
       user     system      total        real
re =~ str         3.540000   0.000000   3.540000 (  3.535881)
str =~ re         3.560000   0.000000   3.560000 (  3.560657)
str[re]           4.300000   0.000000   4.300000 (  4.299403)
re.match str      5.210000   0.010000   5.220000 (  5.213041)
str.match re      6.000000   0.000000   6.000000 (  6.000465)

Résultats IRM 2.4.0:

$ ./bench-re.rb  | sort -t $'\t' -k 2
       user     system      total        real
re.match? str     0.690000   0.010000   0.700000 (  0.682934)
re =~ str         1.040000   0.000000   1.040000 (  1.035863)
str =~ re         1.040000   0.000000   1.040000 (  1.042963)
str[re]           1.340000   0.000000   1.340000 (  1.339704)
re.match str      2.040000   0.000000   2.040000 (  2.046464)
str.match re      2.180000   0.000000   2.180000 (  2.174691)

Question 5

Qu'en est-il re === str(comparaison de cas)?

Puisqu'il évalue true ou false et n'a pas besoin de stocker les correspondances, de renvoyer l'index de correspondance et ce genre de choses, je me demande si ce serait un moyen encore plus rapide de faire la correspondance que =~.

Ok, j'ai testé ça. =~est toujours plus rapide, même si vous avez plusieurs groupes de capture, mais il est plus rapide que les autres options.

BTW, à quoi bon freeze? Je ne pouvais en mesurer aucune amélioration de performance.

Question 6

Selon la complexité de votre expression régulière, vous pouvez simplement utiliser un simple découpage de chaîne. Je ne suis pas sûr de l'aspect pratique de cela pour votre application ou si cela offrirait ou non des améliorations de vitesse.

'testsentence'['stsen']
=> 'stsen' # evaluates to true
'testsentence'['koala']
=> nil # evaluates to false

Question 7

Ce que je me demande, c'est s'il existe un moyen étrange de rendre cette vérification encore plus rapide, peut-être en exploitant une méthode étrange dans Regexp ou une construction étrange.

Les moteurs d'expression régulière varient dans la façon dont ils implémentent les recherches, mais, en général, ancrent vos modèles pour la vitesse et évitent les correspondances gourmandes, en particulier lors de la recherche de longues chaînes.

La meilleure chose à faire, jusqu'à ce que vous soyez familiarisé avec le fonctionnement d'un moteur particulier, est de faire des benchmarks et d'ajouter / supprimer des ancres, d'essayer de limiter les recherches, d'utiliser des caractères génériques par rapport aux correspondances explicites, etc.

Le joyau fruité est très utile pour comparer rapidement les choses, car il est intelligent. Le code Benchmark intégré de Ruby est également utile, bien que vous puissiez écrire des tests qui vous trompent en ne faisant pas attention.

J'ai utilisé les deux dans de nombreuses réponses ici sur Stack Overflow, vous pouvez donc rechercher dans mes réponses et voir de nombreux petits trucs et résultats pour vous donner des idées sur la façon d'écrire du code plus rapidement.

La chose la plus importante à retenir est qu'il est mauvais d'optimiser prématurément votre code avant de savoir où se produisent les ralentissements.

Question 8

Pour compléter les réponses de Wiktor Stribiżew et Dougui, je dirais cela /regex/.match?("string")aussi vite que "string".match?(/regex/).

Rubis 2.4.0 (10 000 000 ~ 2 sec)

2.4.0 > require 'benchmark'
 => true 
2.4.0 > Benchmark.measure{ 10000000.times { /^CVE-[0-9]{4}-[0-9]{4,}$/.match?("CVE-2018-1589") } }
 => #<Benchmark::Tms:0x005563da1b1c80 @label="", @real=2.2060338060000504, @cstime=0.0, @cutime=0.0, @stime=0.04000000000000001, @utime=2.17, @total=2.21> 
2.4.0 > Benchmark.measure{ 10000000.times { "CVE-2018-1589".match?(/^CVE-[0-9]{4}-[0-9]{4,}$/) } }
 => #<Benchmark::Tms:0x005563da139eb0 @label="", @real=2.260814556000696, @cstime=0.0, @cutime=0.0, @stime=0.010000000000000009, @utime=2.2500000000000004, @total=2.2600000000000007>

Rubis 2.6.2 (100 000 000 ~ 20 sec)

irb(main):001:0> require 'benchmark'
=> true
irb(main):005:0> Benchmark.measure{ 100000000.times { /^CVE-[0-9]{4}-[0-9]{4,}$/.match?("CVE-2018-1589") } }
=> #<Benchmark::Tms:0x0000562bc83e3768 @label="", @real=24.60139879199778, @cstime=0.0, @cutime=0.0, @stime=0.010000999999999996, @utime=24.565644999999996, @total=24.575645999999995>
irb(main):004:0> Benchmark.measure{ 100000000.times { "CVE-2018-1589".match?(/^CVE-[0-9]{4}-[0-9]{4,}$/) } }
=> #<Benchmark::Tms:0x0000562bc846aee8 @label="", @real=24.634255946999474, @cstime=0.0, @cutime=0.0, @stime=0.010046, @utime=24.598276, @total=24.608321999999998>

Remarque: les temps varient, parfois /regex/.match?("string")est plus rapide et parfois "string".match?(/regex/), les différences peuvent uniquement être dues à l'activité de la machine.

Answer 1

96

Quel est le moyen le plus rapide de vérifier si une chaîne correspond à une expression régulière dans Ruby?

Mon problème est que je dois "egrep" à travers une énorme liste de chaînes pour trouver celles qui correspondent à une expression rationnelle donnée au moment de l'exécution. Je me soucie seulement de savoir si la chaîne correspond à l'expression rationnelle, pas où elle correspond, ni quel est le contenu des groupes correspondants. J'espère que cette hypothèse peut être utilisée pour réduire le temps que mon code passe à faire correspondre les expressions rationnelles.

Je charge l'expression rationnelle avec

pattern = Regexp.new(ptx).freeze

J'ai trouvé que string =~ patternc'est légèrement plus rapide que string.match(pattern).

Existe-t-il d'autres astuces ou raccourcis qui peuvent être utilisés pour rendre ce test encore plus rapide?

ruby regex performance gioele
la source

Si vous ne vous souciez pas du contenu des groupes correspondants, pourquoi les avez-vous? Vous pouvez rendre les expressions régulières plus rapides en les convertissant en non-capture.

Mark Thomas

1

Étant donné que l'expression rationnelle est fournie au moment de l'exécution, je suppose qu'elle n'est pas contrainte, auquel cas il peut y avoir des références internes dans le reg-exp à des regroupements, et donc les convertir en non-capture en modifiant l'expression rationnelle pourrait modifier le résultat (sauf si vous vérifier en outre les références internes, mais le problème devient de plus en plus complexe). Je trouve curieux = ~ serait plus rapide que string.match.

djconnel

quel est l'avantage de geler l'expression rationnelle ici?

Hardik

Answer 2

Si vous ne vous souciez pas du contenu des groupes correspondants, pourquoi les avez-vous? Vous pouvez rendre les expressions régulières plus rapides en les convertissant en non-capture.

Mark Thomas

Answer 3

1

Étant donné que l'expression rationnelle est fournie au moment de l'exécution, je suppose qu'elle n'est pas contrainte, auquel cas il peut y avoir des références internes dans le reg-exp à des regroupements, et donc les convertir en non-capture en modifiant l'expression rationnelle pourrait modifier le résultat (sauf si vous vérifier en outre les références internes, mais le problème devient de plus en plus complexe). Je trouve curieux = ~ serait plus rapide que string.match.

djconnel

Answer 4

quel est l'avantage de geler l'expression rationnelle ici?

Hardik

Answer 5

À partir de Ruby 2.4.0, vous pouvez utiliser RegExp#match?:

pattern.match?(string)

Regexp#match?est explicitement répertorié comme une amélioration des performances dans les notes de publication de la version 2.4.0 , car il évite les allocations d'objets effectuées par d'autres méthodes telles que Regexp#matchet =~:

Regexp # match?
Ajouté Regexp#match?, qui exécute une correspondance de regexp sans créer un objet de référence arrière et changer $~pour réduire l'allocation d'objets.

Answer 6

5

Merci pour la suggestion. J'ai mis à jour le script de référence et Regexp#match?est en effet au moins 50% plus rapide que les autres alternatives.

gioele

Answer 7

74

Ceci est une simple référence:

require 'benchmark'

"test123" =~ /1/
=> 4
Benchmark.measure{ 1000000.times { "test123" =~ /1/ } }
=>   0.610000   0.000000   0.610000 (  0.578133)

"test123"[/1/]
=> "1"
Benchmark.measure{ 1000000.times { "test123"[/1/] } }
=>   0.718000   0.000000   0.718000 (  0.750010)

irb(main):019:0> "test123".match(/1/)
=> #<MatchData "1">
Benchmark.measure{ 1000000.times { "test123".match(/1/) } }
=>   1.703000   0.000000   1.703000 (  1.578146)

Donc, =~c'est plus rapide mais cela dépend de ce que vous voulez avoir comme valeur renvoyée. Si vous voulez juste vérifier si le texte contient une expression régulière ou ne pas utiliser=~

Dougui
la source

2

Comme je l'ai écrit, j'ai déjà trouvé que =~c'est plus rapide que match, avec une augmentation des performances moins dramatique lorsque l'on fonctionne sur des expressions rationnelles plus grandes. Ce que je me demande, c'est s'il existe un moyen étrange de rendre cette vérification encore plus rapide, peut-être en exploitant une méthode étrange dans Regexp ou une construction étrange.

gioele

Je pense qu'il n'y a pas d'autres solutions

Dougui

Et quoi !("test123" !~ /1/)?

ma11hew28

1

@MattDiPasquale, deux fois l'inverse ne devrait pas être plus rapide que"test123" =~ /1/

Dougui

1

/1/.match?("test123")est plus rapide que "test123" =~ /1/si ce n'est que pour vérifier si le texte contient une expression régulière ou non.

noraj

Answer 8

2

Comme je l'ai écrit, j'ai déjà trouvé que =~c'est plus rapide que match, avec une augmentation des performances moins dramatique lorsque l'on fonctionne sur des expressions rationnelles plus grandes. Ce que je me demande, c'est s'il existe un moyen étrange de rendre cette vérification encore plus rapide, peut-être en exploitant une méthode étrange dans Regexp ou une construction étrange.

gioele

Answer 9

Je pense qu'il n'y a pas d'autres solutions

Dougui

Answer 10

Et quoi !("test123" !~ /1/)?

ma11hew28

Answer 11

1

@MattDiPasquale, deux fois l'inverse ne devrait pas être plus rapide que"test123" =~ /1/

Dougui

Answer 12

1

/1/.match?("test123")est plus rapide que "test123" =~ /1/si ce n'est que pour vérifier si le texte contient une expression régulière ou non.

noraj

Answer 13

C'est la référence que j'ai exécutée après avoir trouvé quelques articles sur le net.

Avec la version 2.4.0, le gagnant est re.match?(str)(comme le suggère @ wiktor-stribiżew), sur les versions précédentes, re =~ strsemble être le plus rapide, bien qu'il str =~ resoit presque aussi rapide.

#!/usr/bin/env ruby
require 'benchmark'

str = "aacaabc"
re = Regexp.new('a+b').freeze

N = 4_000_000

Benchmark.bm do |b|
    b.report("str.match re\t") { N.times { str.match re } }
    b.report("str =~ re\t")    { N.times { str =~ re } }
    b.report("str[re]  \t")    { N.times { str[re] } }
    b.report("re =~ str\t")    { N.times { re =~ str } }
    b.report("re.match str\t") { N.times { re.match str } }
    if re.respond_to?(:match?)
        b.report("re.match? str\t") { N.times { re.match? str } }
    end
end

Résultats IRM 1.9.3-o551:

$ ./bench-re.rb  | sort -t $'\t' -k 2
       user     system      total        real
re =~ str         2.390000   0.000000   2.390000 (  2.397331)
str =~ re         2.450000   0.000000   2.450000 (  2.446893)
str[re]           2.940000   0.010000   2.950000 (  2.941666)
re.match str      3.620000   0.000000   3.620000 (  3.619922)
str.match re      4.180000   0.000000   4.180000 (  4.180083)

Résultats IRM 2.1.5:

$ ./bench-re.rb  | sort -t $'\t' -k 2
       user     system      total        real
re =~ str         1.150000   0.000000   1.150000 (  1.144880)
str =~ re         1.160000   0.000000   1.160000 (  1.150691)
str[re]           1.330000   0.000000   1.330000 (  1.337064)
re.match str      2.250000   0.000000   2.250000 (  2.255142)
str.match re      2.270000   0.000000   2.270000 (  2.270948)

Résultats IRM 2.3.3 (il y a une régression dans l'appariement des regex, semble-t-il):

$ ./bench-re.rb  | sort -t $'\t' -k 2
       user     system      total        real
re =~ str         3.540000   0.000000   3.540000 (  3.535881)
str =~ re         3.560000   0.000000   3.560000 (  3.560657)
str[re]           4.300000   0.000000   4.300000 (  4.299403)
re.match str      5.210000   0.010000   5.220000 (  5.213041)
str.match re      6.000000   0.000000   6.000000 (  6.000465)

Résultats IRM 2.4.0:

$ ./bench-re.rb  | sort -t $'\t' -k 2
       user     system      total        real
re.match? str     0.690000   0.010000   0.700000 (  0.682934)
re =~ str         1.040000   0.000000   1.040000 (  1.035863)
str =~ re         1.040000   0.000000   1.040000 (  1.042963)
str[re]           1.340000   0.000000   1.340000 (  1.339704)
re.match str      2.040000   0.000000   2.040000 (  2.046464)
str.match re      2.180000   0.000000   2.180000 (  2.174691)

Answer 14

Juste pour ajouter une note, les formes littérales sont plus rapides que celles-ci. Par exemple /a+b/ =~ stret str =~ /a+b/. C'est valable même en les itérant à travers des fonctions et je vois cela suffisamment valide pour être considéré comme meilleur que le stockage et le gel d'expressions régulières sur une variable. J'ai testé mon script avec ruby 1.9.3p547, ruby 2.0.0p481 et ruby 2.1.4p265. Il est possible que ces améliorations aient été apportées sur des correctifs ultérieurs, mais je n'ai pas encore l'intention de le tester avec des versions / correctifs antérieurs.

konsolebox

Answer 15

Je pensais !(re !~ str)que c'était peut-être plus rapide, mais ce n'est pas le cas.

ma11hew28

Answer 16

Qu'en est-il re === str(comparaison de cas)?

Puisqu'il évalue true ou false et n'a pas besoin de stocker les correspondances, de renvoyer l'index de correspondance et ce genre de choses, je me demande si ce serait un moyen encore plus rapide de faire la correspondance que =~.

Ok, j'ai testé ça. =~est toujours plus rapide, même si vous avez plusieurs groupes de capture, mais il est plus rapide que les autres options.

BTW, à quoi bon freeze? Je ne pouvais en mesurer aucune amélioration de performance.

Answer 17

Les effets de freezen'apparaîtront pas dans les résultats car il se produit avant les boucles de référence et agit sur le modèle lui-même.

The Tin Man

Answer 18

5

Selon la complexité de votre expression régulière, vous pouvez simplement utiliser un simple découpage de chaîne. Je ne suis pas sûr de l'aspect pratique de cela pour votre application ou si cela offrirait ou non des améliorations de vitesse.

'testsentence'['stsen']
=> 'stsen' # evaluates to true
'testsentence'['koala']
=> nil # evaluates to false

Jimmydief
la source

Je ne peux pas utiliser le découpage de chaînes car l'expression rationnelle est fournie au moment de l'exécution et je n'ai aucun contrôle sur cela.

gioele

Vous pouvez utiliser le découpage de chaînes, mais pas le découpage en utilisant une chaîne fixe. Utilisez une variable au lieu d'une chaîne entre guillemets et cela fonctionnerait toujours.

The Tin Man

Answer 19

Je ne peux pas utiliser le découpage de chaînes car l'expression rationnelle est fournie au moment de l'exécution et je n'ai aucun contrôle sur cela.

gioele

Answer 20

Vous pouvez utiliser le découpage de chaînes, mais pas le découpage en utilisant une chaîne fixe. Utilisez une variable au lieu d'une chaîne entre guillemets et cela fonctionnerait toujours.

The Tin Man

Answer 21

Ce que je me demande, c'est s'il existe un moyen étrange de rendre cette vérification encore plus rapide, peut-être en exploitant une méthode étrange dans Regexp ou une construction étrange.

Les moteurs d'expression régulière varient dans la façon dont ils implémentent les recherches, mais, en général, ancrent vos modèles pour la vitesse et évitent les correspondances gourmandes, en particulier lors de la recherche de longues chaînes.

La meilleure chose à faire, jusqu'à ce que vous soyez familiarisé avec le fonctionnement d'un moteur particulier, est de faire des benchmarks et d'ajouter / supprimer des ancres, d'essayer de limiter les recherches, d'utiliser des caractères génériques par rapport aux correspondances explicites, etc.

Le joyau fruité est très utile pour comparer rapidement les choses, car il est intelligent. Le code Benchmark intégré de Ruby est également utile, bien que vous puissiez écrire des tests qui vous trompent en ne faisant pas attention.

J'ai utilisé les deux dans de nombreuses réponses ici sur Stack Overflow, vous pouvez donc rechercher dans mes réponses et voir de nombreux petits trucs et résultats pour vous donner des idées sur la façon d'écrire du code plus rapidement.

La chose la plus importante à retenir est qu'il est mauvais d'optimiser prématurément votre code avant de savoir où se produisent les ralentissements.

Answer 22

Pour compléter les réponses de Wiktor Stribiżew et Dougui, je dirais cela /regex/.match?("string")aussi vite que "string".match?(/regex/).

Rubis 2.4.0 (10 000 000 ~ 2 sec)

2.4.0 > require 'benchmark'
 => true 
2.4.0 > Benchmark.measure{ 10000000.times { /^CVE-[0-9]{4}-[0-9]{4,}$/.match?("CVE-2018-1589") } }
 => #<Benchmark::Tms:0x005563da1b1c80 @label="", @real=2.2060338060000504, @cstime=0.0, @cutime=0.0, @stime=0.04000000000000001, @utime=2.17, @total=2.21> 
2.4.0 > Benchmark.measure{ 10000000.times { "CVE-2018-1589".match?(/^CVE-[0-9]{4}-[0-9]{4,}$/) } }
 => #<Benchmark::Tms:0x005563da139eb0 @label="", @real=2.260814556000696, @cstime=0.0, @cutime=0.0, @stime=0.010000000000000009, @utime=2.2500000000000004, @total=2.2600000000000007>

Rubis 2.6.2 (100 000 000 ~ 20 sec)

irb(main):001:0> require 'benchmark'
=> true
irb(main):005:0> Benchmark.measure{ 100000000.times { /^CVE-[0-9]{4}-[0-9]{4,}$/.match?("CVE-2018-1589") } }
=> #<Benchmark::Tms:0x0000562bc83e3768 @label="", @real=24.60139879199778, @cstime=0.0, @cutime=0.0, @stime=0.010000999999999996, @utime=24.565644999999996, @total=24.575645999999995>
irb(main):004:0> Benchmark.measure{ 100000000.times { "CVE-2018-1589".match?(/^CVE-[0-9]{4}-[0-9]{4,}$/) } }
=> #<Benchmark::Tms:0x0000562bc846aee8 @label="", @real=24.634255946999474, @cstime=0.0, @cutime=0.0, @stime=0.010046, @utime=24.598276, @total=24.608321999999998>

Remarque: les temps varient, parfois /regex/.match?("string")est plus rapide et parfois "string".match?(/regex/), les différences peuvent uniquement être dues à l'activité de la machine.

Le moyen le plus rapide de vérifier si une chaîne correspond à une expression rationnelle en ruby?

Réponses: