Лучший способ найти подстроку в строке - PullRequest
Новая
       13

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

8 голосов
/ 06 октября 2010

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

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

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

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

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

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

Ответы [ 7 ]

10 голосов
/ 06 октября 2010

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

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

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

5 голосов
/ 07 октября 2010

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

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

В более старых версиях 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, поэтому результаты напрямую не связаны с информацией выше, но все же полезно.

4 голосов
/ 06 октября 2010

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

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

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

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

2 голосов
/ 06 октября 2010

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

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

0 голосов
/ 07 октября 2010

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

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

0 голосов
/ 06 октября 2010

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

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

0 голосов
/ 06 октября 2010

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

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

Нет похожих вопросов

...