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

Question

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

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

Как шаблон поиска прост, я избегаю регулярного выражения.

Answer 4

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

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

Answer 5

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

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

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

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

Answer 6

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

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

Answer 7

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

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

В старых версиях 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.7) 
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) 

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