Лучший способ найти подстроку в строке

У меня проблема, когда я пытаюсь найти подстроку в строке. Эта подстрока может или не может быть в строке.

str = "hello how are you?"
substr = "how are"

Два способа, которые я знаю, если это можно сделать, это:

string.indexOf("how are")регулярное выражение

Но есть ли другой "оптимизированный" способ? Что бы вы сделали?

Может ли Ruby дать лучший ответ? Поскольку мы используем jRuby, ответ может быть на Ruby или Java.

 Automatico18 мая 2014 г., 17:59
Знайте, что это старо: «Лучший путь» во многом зависит от цели. Если это простота разработки,str.include?(substring) это здорово, но если это скорость, то может быть другой подход, который лучше.

Ответы на вопрос(7)

Если вы хотите только проверить, находится ли подстрока в строке, вы можете использовать:str[substr]

Возвращает подстроку или ноль.

"Что бы вы сделали?"

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

В более старых версиях Ruby мы видели, что поиск на основе регулярных выражений работает медленнее. Новый движок в 1.9.2, который я использую для тестирования, имеет большое значение. В частности, поиски без привязки были намного медленнее, чем привязки. Теперь мы можем ли вы использовать регулярное выражение или поиск по фиксированной строке по большей части. Использование match () без предварительной компиляции регулярного выражения является болезненным ударом по скорости, поэтому, если вы делаете много циклов с одним и тем же шаблоном, тогда имеет смысл назначить шаблон для переменной и ссылаться на нее.

Отображаемое время показывает, сколько времени потребовалось каждому тесту для выполнения «n» (750 000) итераций, поэтому чем меньше число, тем лучше.

require 'benchmark'

LOREM = %q{Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut et convallis purus. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Cras interdum nibh et nunc pellentesque vestibulum. Donec elementum felis malesuada urna vehicula consectetur commodo urna accumsan. Phasellus bibendum euismod tincidunt. Sed pellentesque cursus faucibus. Etiam bibendum tincidunt nibh eget ultrices. Fusce imperdiet, felis id consequat imperdiet, justo est ultrices elit, sed vestibulum dui nibh vel felis. Sed feugiat, libero quis consequat semper, magna tellus facilisis enim, rutrum adipiscing eros mauris commodo metus. Sed lobortis aliquet augue ac sodales. Quisque pharetra odio vel augue tempus porttitor.}

REGEX1 = %r{/porttitor\.$/}
REGEX2 = %r{/porttitor\./}
REGEX3 = %r{/porttitor\.\Z/}

n = 750_000
puts "word in string"
Benchmark.bm(15) do |x|
  x.report('string[""]:')   { n.times { LOREM['porttitor.']          } }
  x.report('string[//]:')   { n.times { LOREM[/porttitor\./]         } } # unanchored regex
  x.report('string[/$/]:')  { n.times { LOREM[/porttitor\.$/]        } } # anchored regex
  x.report('string[/\Z/]:') { n.times { LOREM[/porttitor\.\Z/]       } } # anchored regex
  x.report('index():')      { n.times { LOREM.index('porttitor.')    } }
  x.report('include?():')   { n.times { LOREM.include?('porttitor.') } }
  x.report('match($):')     { n.times { LOREM.match(/porttitor\.$/)  } }
  x.report('match(\Z):')    { n.times { LOREM.match(/porttitor\.\Z/) } }
  x.report('match():')      { n.times { LOREM.match(/porttitor\./)   } }
  x.report('match2($):')    { n.times { LOREM.match(REGEX1)          } } # compiled regex w/ anchor
  x.report('match2():')     { n.times { LOREM.match(REGEX2)          } } # compiled report w/out anchor
  x.report('match2(\Z):')   { n.times { LOREM.match(REGEX3)          } } # compiled regex w/ anchor
end

puts
puts "word not in string"
Benchmark.bm(15) do |x|
  x.report('string[""]:')   { n.times { LOREM['porttit0r.']          } }
  x.report('string[//]:')   { n.times { LOREM[/porttit0r\./]         } } # unanchored regex
  x.report('string[/$/]:')  { n.times { LOREM[/porttit0r\.$/]        } } # anchored regex
  x.report('string[/\Z/]:') { n.times { LOREM[/porttit0r\.\Z/]       } } # anchored regex
  x.report('index():')      { n.times { LOREM.index('porttit0r.')    } }
  x.report('include?():')   { n.times { LOREM.include?('porttit0r.') } }
  x.report('match($):')     { n.times { LOREM.match(/porttit0r\.$/)  } }
  x.report('match(\Z):')    { n.times { LOREM.match(/porttit0r\.\Z/) } }
  x.report('match():')      { n.times { LOREM.match(/porttit0r\./)   } }
end

С выходом:

word in string
                      user     system      total        real
string[""]:       0.670000   0.000000   0.670000 (  0.675319)
string[//]:       0.700000   0.000000   0.700000 (  0.706148)
string[/$/]:      0.720000   0.000000   0.720000 (  0.716853)
string[/\Z/]:     0.530000   0.000000   0.530000 (  0.527568)
index():          0.630000   0.000000   0.630000 (  0.638562)
include?():       0.610000   0.000000   0.610000 (  0.603223)
match($):         1.690000   0.000000   1.690000 (  1.696045)
match(\Z):        1.520000   0.010000   1.530000 (  1.532107)
match():          1.700000   0.000000   1.700000 (  1.698748)
match2($):        0.840000   0.000000   0.840000 (  0.847590)
match2():         0.840000   0.000000   0.840000 (  0.840969)
match2(\Z):       0.840000   0.000000   0.840000 (  0.835557)

word not in string
                      user     system      total        real
string[""]:       0.570000   0.000000   0.570000 (  0.578120)
string[//]:       0.740000   0.000000   0.740000 (  0.734751)
string[/$/]:      0.730000   0.000000   0.730000 (  0.735599)
string[/\Z/]:     0.560000   0.000000   0.560000 (  0.563673)
index():          0.620000   0.000000   0.620000 (  0.619451)
include?():       0.570000   0.000000   0.570000 (  0.574413)
match($):         0.910000   0.010000   0.920000 (  0.910059)
match(\Z):        0.730000   0.000000   0.730000 (  0.726533)
match():          0.950000   0.000000   0.950000 (  0.960865)

Для справки, вот некоторые цифры, использующие Ruby 1.8.7, который используется по умолчанию для Snow Leopard:

word in string
                     user     system      total        real
string[""]:      1.130000   0.000000   1.130000 (  1.130687)
string[//]:      1.170000   0.000000   1.170000 (  1.165692)
string[/$/]:     1.180000   0.000000   1.180000 (  1.184954)
string[/\Z/]:    1.180000   0.000000   1.180000 (  1.179168)
index():         1.070000   0.000000   1.070000 (  1.077791)
include?():      1.060000   0.000000   1.060000 (  1.056430)
match($):        1.470000   0.010000   1.480000 (  1.472797)
match(\Z):       1.480000   0.000000   1.480000 (  1.490172)
match():         1.480000   0.000000   1.480000 (  1.478146)
match2($):       0.650000   0.000000   0.650000 (  0.653029)
match2():        0.570000   0.000000   0.570000 (  0.574384)
match2(\Z):      0.640000   0.000000   0.640000 (  0.646688)

word not in string
                     user     system      total        real
string[""]:      1.040000   0.000000   1.040000 (  1.038885)
string[//]:      0.510000   0.000000   0.510000 (  0.507031)
string[/$/]:     0.510000   0.000000   0.510000 (  0.508425)
string[/\Z/]:    0.500000   0.000000   0.500000 (  0.507316)
index():         1.060000   0.000000   1.060000 (  1.055157)
include?():      1.030000   0.000000   1.030000 (  1.037060)
match($):        0.630000   0.000000   0.630000 (  0.623627)
match(\Z):       0.620000   0.000000   0.620000 (  0.624737)
match():         0.620000   0.000000   0.620000 (  0.623049)

Я добавил дополнительные тесты, чтобы дать некоторые представления о последствиях использования только не закрепленного и закрепленного регулярного выражения:

require 'fruity'

LOREM = %{Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut et convallis purus. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Cras interdum nibh et nunc pellentesque vestibulum. Donec elementum felis malesuada urna vehicula consectetur commodo urna accumsan. Phasellus bibendum euismod tincidunt. Sed pellentesque cursus faucibus. Etiam bibendum tincidunt nibh eget ultrices. Fusce imperdiet, felis id consequat imperdiet, justo est ultrices elit, sed vestibulum dui nibh vel felis. Sed feugiat, libero quis consequat semper, magna tellus facilisis enim, rutrum adipiscing eros mauris commodo metus. Sed lobortis aliquet augue ac sodales. Quisque pharetra odio vel augue tempus porttitor.}

compare do
  str_slice_regex  { LOREM[/porttitor\./]         } # unanchored regex
  str_slice_dollar { LOREM[/porttitor\.$/]        } # anchored regex
  str_slice_ctrlZ  { LOREM[/porttitor\.\Z/]       } # anchored regex
  str_slice_ctrlz  { LOREM[/porttitor\.\z/]       } # anchored regex
end

# >> Running each test 8192 times. Test will take about 1 second.
# >> str_slice_ctrlz is similar to str_slice_ctrlZ
# >> str_slice_ctrlZ is faster than str_slice_regex by 2x ± 0.1
# >> str_slice_regex is similar to str_slice_dollar

Это использует Fruity, поэтому результаты не напрямую связаны с информацией выше, но это все еще полезно.

 Nakilon07 окт. 2010 г., 19:38
Хорошая работа! Но для меня остается странным, что str [substr] медленнее, чем регулярные выражения. Теоретически, str [substr] - это самый простой метод для реализации с хорошей производительностью. Надеюсь, однажды Япония это оптимизирует.
 the Tin Man07 окт. 2010 г., 20:07
Я не смотрел на источник, но подозреваю, что str [substr] действительно обрабатывает каждую подстроку в скобках как регулярное выражение, заставляя перекомпилировать шаблон или пропуская другой код, который выполняет поиск по фиксированной строке. Выполнить поиск по фиксированной строке в C / C ++ легко, поэтому должна выполняться какая-то другая обработка. Или я сделал неверный тест, но я так не думаю.

Насколько мне известно, нет никакого «волшебного» способа быстрого поиска подстрок, если только вы не готовы заранее создать какие-то метаданные поиска (продумайте индекс). Это, скорее всего, потратит больше времени, чем сэкономит, если вы не будете часто искать в одной и той же строке.

Поскольку шаблон поиска прост, я бы избежал регулярных выражений.

Для обзора «других способов» вы можете начать со статьи в Википедии об алгоритмах поиска строк:

http://en.wikipedia.org/wiki/String_searching_algorithm

Индексирование строк - это один из наиболее очевидных способов ускорения, как упомянул Мартин, который уместен, только если вы выполняете несколько поисков по одной и той же строке:

http://en.wikipedia.org/wiki/Substring_index

лучший способ это indexof, регулярное выражение медленнее

Решение Вопроса

В Ruby используйтеString#include? метод:

str = "hello how are you?"
substr = "how are"
str.include? substr 

который возвращаетсяtrue.

Если вы убеждены, что средства вашей системы времени выполнения (которые предлагают поиск по строкам в строке и т. П.) Не достаточно быстры для вашего приложения, попробуйте реализоватьKMP алгоритм.

Но разработчики современных систем времени выполнения, вероятно, уже сделали это для вас.

Ваш ответ на вопрос