Самый быстрый способ проверить, соответствует ли строка регулярному выражению в Ruby?

Question 1

Каков самый быстрый способ проверить, соответствует ли строка регулярному выражению в Ruby?

Моя проблема в том, что мне нужно «egrep» просмотреть огромный список строк, чтобы найти те, которые соответствуют регулярному выражению, заданному во время выполнения. Меня волнует только то, соответствует ли строка регулярному выражению, а не то, где она совпадает, и каково содержимое совпадающих групп. Я надеюсь, что это предположение можно использовать для сокращения времени, которое мой код тратит на сопоставление регулярных выражений.

Я загружаю регулярное выражение с помощью

pattern = Regexp.new(ptx).freeze

Я обнаружил, что string =~ patternэто немного быстрее, чем string.match(pattern).

Есть ли другие уловки или ярлыки, которые можно использовать, чтобы сделать этот тест еще быстрее?

Question 2

Начиная с Ruby 2.4.0, вы можете использовать RegExp#match?:

pattern.match?(string)

Regexp#match?явно указан как повышение производительности в примечаниях к выпуску 2.4.0 , поскольку позволяет избежать выделения объектов, выполняемого другими методами, такими как Regexp#matchи =~:

Regexp # match?
Добавлен Regexp#match?, который выполняет сопоставление регулярного выражения без создания объекта обратной ссылки и изменения, $~чтобы уменьшить выделение объекта.

Question 3

Это простой тест:

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)

Так =~быстрее, но это зависит от того, что вы хотите иметь в качестве возвращаемого значения. Если вы просто хотите проверить, содержит ли текст регулярное выражение или не используйте=~

Question 4

Это тест, который я провел после того, как нашел в сети несколько статей.

С 2.4.0 победителем является re.match?(str)(как предлагает @ wiktor-stribiżew), в предыдущих версиях он re =~ strкажется самым быстрым, хотя str =~ reи почти таким же быстрым.

#!/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

Результаты МРТ 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)

Результаты МРТ 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)

Результаты MRI 2.3.3 (похоже, есть регресс в сопоставлении регулярных выражений):

$ ./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)

Результаты МРТ 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

А как насчет re === str(сравнение случаев)?

Поскольку он оценивается как true или false и не нуждается в хранении совпадений, возврате индекса совпадения и тому подобном, мне интересно, будет ли это еще более быстрый способ сопоставления, чем =~.

Хорошо, я это проверил. =~по-прежнему быстрее, даже если у вас несколько групп захвата, однако он быстрее, чем другие варианты.

Кстати, что хорошего freeze? Я не мог измерить прирост производительности от этого.

Question 6

В зависимости от того, насколько сложным является ваше регулярное выражение, вы можете просто использовать простую нарезку строки. Я не уверен в практичности этого для вашего приложения и в том, действительно ли это будет предлагать какие-либо улучшения скорости.

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

Question 7

Мне интересно, есть ли какой-нибудь странный способ сделать эту проверку еще быстрее, возможно, используя какой-то странный метод в Regexp или какую-то странную конструкцию.

Механизмы регулярных выражений различаются по тому, как они реализуют поиск, но, как правило, они привязывают ваши шаблоны к скорости и избегают жадных совпадений, особенно при поиске длинных строк.

Лучше всего, пока вы не ознакомитесь с тем, как работает конкретный движок, - это провести тесты и добавить / удалить привязки, попытаться ограничить поиск, использовать подстановочные знаки вместо явных совпадений и т. Д.

Фруктово камень очень полезна для быстрого бенчмаркинг вещей, потому что это умно. Встроенный в Ruby код Benchmark также полезен, хотя вы можете писать тесты, которые обманывают вас, если вы не будете осторожны.

Я использовал оба во многих ответах здесь, в Stack Overflow, поэтому вы можете просмотреть мои ответы и увидеть множество маленьких трюков и результатов, которые дадут вам идеи о том, как писать более быстрый код.

Самое важное, что нужно помнить, - это плохо - преждевременно оптимизировать код, прежде чем вы узнаете, где происходит замедление.

Question 8

Чтобы завершить ответы Виктора Стрибьева и Дуги, я бы сказал, что это /regex/.match?("string")примерно так быстро "string".match?(/regex/).

Ruby 2.4.0 (10 000 000 ~ 2 секунды)

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>

Рубин 2.6.2 (100000000 ~ 20 сек)

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>

Примечание: время варьируется, иногда /regex/.match?("string")быстрее, а иногда "string".match?(/regex/)разница может быть только из-за активности машины.

Answer 1

Каков самый быстрый способ проверить, соответствует ли строка регулярному выражению в Ruby?

Моя проблема в том, что мне нужно «egrep» просмотреть огромный список строк, чтобы найти те, которые соответствуют регулярному выражению, заданному во время выполнения. Меня волнует только то, соответствует ли строка регулярному выражению, а не то, где она совпадает, и каково содержимое совпадающих групп. Я надеюсь, что это предположение можно использовать для сокращения времени, которое мой код тратит на сопоставление регулярных выражений.

Я загружаю регулярное выражение с помощью

pattern = Regexp.new(ptx).freeze

Я обнаружил, что string =~ patternэто немного быстрее, чем string.match(pattern).

Есть ли другие уловки или ярлыки, которые можно использовать, чтобы сделать этот тест еще быстрее?

Answer 2

Если вас не волнует содержание соответствующих групп, почему они у вас есть? Вы можете ускорить регулярное выражение, преобразовав их в режим без захвата.

Марк Томас

Answer 3

1

Поскольку регулярное выражение предоставляется во время выполнения, я предполагаю, что оно не ограничено, и в этом случае могут быть внутренние ссылки внутри reg-exp на группировки, и поэтому их преобразование в не захватывающее путем изменения регулярного выражения может изменить результат (если вы не дополнительно проверьте наличие внутренних ссылок, но проблема становится все более сложной). Мне кажется любопытным, что = ~ будет быстрее, чем string.match.

djconnel 09

Answer 4

Какая польза от замораживания здесь регулярного выражения?

Hardik

Answer 5

Начиная с Ruby 2.4.0, вы можете использовать RegExp#match?:

pattern.match?(string)

Regexp#match?явно указан как повышение производительности в примечаниях к выпуску 2.4.0 , поскольку позволяет избежать выделения объектов, выполняемого другими методами, такими как Regexp#matchи =~:

Regexp # match?
Добавлен Regexp#match?, который выполняет сопоставление регулярного выражения без создания объекта обратной ссылки и изменения, $~чтобы уменьшить выделение объекта.

Answer 6

6

Спасибо за предложение. Я обновил тестовый сценарий и Regexp#match?действительно работает как минимум на 50% быстрее, чем другие альтернативы.

gioele

Answer 7

74

Это простой тест:

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)

Так =~быстрее, но это зависит от того, что вы хотите иметь в качестве возвращаемого значения. Если вы просто хотите проверить, содержит ли текст регулярное выражение или не используйте=~

Дуги
источник

2

Как я уже писал, я уже обнаружил, что =~это быстрее match, с менее значительным увеличением производительности при работе с большими регулярными выражениями. Мне интересно, есть ли какой-нибудь странный способ сделать эту проверку еще быстрее, возможно, используя какой-то странный метод в Regexp или какую-то странную конструкцию.

gioele 09

Думаю, других решений нет

Дуги

О чем !("test123" !~ /1/)?

ma11hew28

1

@MattDiPasquale, двойное обратное не должно быть быстрее, чем"test123" =~ /1/

Dougui

1

/1/.match?("test123")быстрее, чем "test123" =~ /1/если бы он только проверял, содержит ли текст регулярное выражение или нет.

noraj 01

Answer 8

2

Как я уже писал, я уже обнаружил, что =~это быстрее match, с менее значительным увеличением производительности при работе с большими регулярными выражениями. Мне интересно, есть ли какой-нибудь странный способ сделать эту проверку еще быстрее, возможно, используя какой-то странный метод в Regexp или какую-то странную конструкцию.

gioele 09

Answer 9

Думаю, других решений нет

Дуги

Answer 10

О чем !("test123" !~ /1/)?

ma11hew28

Answer 11

1

@MattDiPasquale, двойное обратное не должно быть быстрее, чем"test123" =~ /1/

Dougui

Answer 12

1

/1/.match?("test123")быстрее, чем "test123" =~ /1/если бы он только проверял, содержит ли текст регулярное выражение или нет.

noraj 01

Answer 13

Это тест, который я провел после того, как нашел в сети несколько статей.

С 2.4.0 победителем является re.match?(str)(как предлагает @ wiktor-stribiżew), в предыдущих версиях он re =~ strкажется самым быстрым, хотя str =~ reи почти таким же быстрым.

#!/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

Результаты МРТ 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)

Результаты МРТ 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)

Результаты MRI 2.3.3 (похоже, есть регресс в сопоставлении регулярных выражений):

$ ./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)

Результаты МРТ 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

Просто чтобы добавить примечание, буквальные формы быстрее, чем эти. Например, /a+b/ =~ strи str =~ /a+b/. Это справедливо даже при повторении их через функции, и я считаю, что это достаточно правильно, чтобы рассматривать его как лучше, чем хранение и замораживание регулярных выражений в переменной. Я тестировал свой скрипт с Ruby 1.9.3p547, ruby 2.0.0p481 и ruby 2.1.4p265. Возможно, эти улучшения были внесены в более поздние исправления, но я пока не планирую тестировать его с более ранними версиями / исправлениями.

konsolebox

Answer 15

Я думал !(re !~ str)может быть быстрее, но это не так.

ma11hew28

Answer 16

А как насчет re === str(сравнение случаев)?

Поскольку он оценивается как true или false и не нуждается в хранении совпадений, возврате индекса совпадения и тому подобном, мне интересно, будет ли это еще более быстрый способ сопоставления, чем =~.

Хорошо, я это проверил. =~по-прежнему быстрее, даже если у вас несколько групп захвата, однако он быстрее, чем другие варианты.

Кстати, что хорошего freeze? Я не мог измерить прирост производительности от этого.

Answer 17

Эффекты freezeне будут отображаться в результатах, потому что они возникают до циклов тестирования и воздействуют на сам шаблон.

Железный Человек

Answer 18

5

В зависимости от того, насколько сложным является ваше регулярное выражение, вы можете просто использовать простую нарезку строки. Я не уверен в практичности этого для вашего приложения и в том, действительно ли это будет предлагать какие-либо улучшения скорости.

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

Джиммидиф
источник

Я не могу использовать нарезку строк, потому что регулярное выражение предоставляется во время выполнения, и я не контролирую это.

gioele 09

Вы можете использовать нарезку строки, но не нарезку с использованием фиксированной строки. Используйте переменную вместо строки в кавычках, и она все равно будет работать.

Железный Человек

Answer 19

Я не могу использовать нарезку строк, потому что регулярное выражение предоставляется во время выполнения, и я не контролирую это.

gioele 09

Answer 20

Вы можете использовать нарезку строки, но не нарезку с использованием фиксированной строки. Используйте переменную вместо строки в кавычках, и она все равно будет работать.

Железный Человек

Answer 21

Мне интересно, есть ли какой-нибудь странный способ сделать эту проверку еще быстрее, возможно, используя какой-то странный метод в Regexp или какую-то странную конструкцию.

Механизмы регулярных выражений различаются по тому, как они реализуют поиск, но, как правило, они привязывают ваши шаблоны к скорости и избегают жадных совпадений, особенно при поиске длинных строк.

Лучше всего, пока вы не ознакомитесь с тем, как работает конкретный движок, - это провести тесты и добавить / удалить привязки, попытаться ограничить поиск, использовать подстановочные знаки вместо явных совпадений и т. Д.

Фруктово камень очень полезна для быстрого бенчмаркинг вещей, потому что это умно. Встроенный в Ruby код Benchmark также полезен, хотя вы можете писать тесты, которые обманывают вас, если вы не будете осторожны.

Я использовал оба во многих ответах здесь, в Stack Overflow, поэтому вы можете просмотреть мои ответы и увидеть множество маленьких трюков и результатов, которые дадут вам идеи о том, как писать более быстрый код.

Самое важное, что нужно помнить, - это плохо - преждевременно оптимизировать код, прежде чем вы узнаете, где происходит замедление.

Answer 22

Чтобы завершить ответы Виктора Стрибьева и Дуги, я бы сказал, что это /regex/.match?("string")примерно так быстро "string".match?(/regex/).

Ruby 2.4.0 (10 000 000 ~ 2 секунды)

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>

Рубин 2.6.2 (100000000 ~ 20 сек)

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>

Примечание: время варьируется, иногда /regex/.match?("string")быстрее, а иногда "string".match?(/regex/)разница может быть только из-за активности машины.

Самый быстрый способ проверить, соответствует ли строка регулярному выражению в Ruby?

Ответы: