在字符串中查找子字符串的最佳方法

我有一个问题，我试图在字符串中搜索子字符串。 该子字符串可能在字符串中，也可能不在字符串中。

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

“你会怎么做？”

我会做一个基准测试并尝试比较不同的方法来完成同样的事情来学习哪个是最快的。

在旧版本的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 

随着输出：

字符串中的单词
                      用户系统总真实
 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）
匹配（\ 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）

字不在字符串中
                      用户系统总真实
 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）
匹配（$）：0.910000 0.010000 0.920000（0.910059）
匹配（\ Z）：0.730000 0.000000 0.730000（0.726533）
 match（）：0.950000 0.000000 0.950000（0.960865）

作为参考，这里有一些使用Ruby 1.8.7的数字，这是Snow Leopard的默认值：

字符串中的单词
                     用户系统总真实
 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）
匹配（$）：1.470000 0.010000 1.480000（1.472797）
匹配（\ 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）

字不在字符串中
                     用户系统总真实
 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）
匹配（$）：0.630000 0.000000 0.630000（0.623627）
匹配（\ 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，因此结果与上面的信息没有直接关联，但它仍然有用。

Answer 3

有关“其他方式”的概述，您可以从关于字符串搜索算法的维基百科文章开始：

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

索引字符串是加快速度的一种非常明显的方法，正如Martin所提到的那样，只有在对同一个字符串进行多次搜索时才适用：

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

Answer 4

如果你只想检查substring是否在字符串中，你可以使用： str[substr]

它返回substring或nil。

Answer 5

据我所知，除非你已经准备好事先构建某种搜索元数据（思考索引），否则没有“神奇”的方法可以非常快速地搜索子字符串。 除非您经常搜索相同的字符串，否则这样做最有可能浪费更多时间。

由于搜索模式很简单，我会避开正则表达式。

Answer 6

如果您确信运行时系统中的工具（提供字符串字符串搜索等）对于您的应用程序来说不够快，请尝试实施KMP算法。

但是，现代运行时系统的实现者可能已经为您完成了这项工作。

Answer 7

最好的方法是indexof，正则表达式更慢