我有一个问题,我试图在字符串中搜索子字符串.该子字符串可能在字符串中,也可能不在字符串中.
str = "hello how are you?"
substr = "how are"
我知道可以做的两种方式是:
string.indexOf("how are")但是,还有其他"优化"方式吗？你会怎么做？
Ruby可以提供更好的答案吗？由于我们使用jRuby,答案可以是Ruby或Java.
Jas*_*Jas 10
在Ruby中,使用以下String#include?方法:
str = "hello how are you?"
substr = "how are"
str.include? substr
返回true.
有关“其他方式”的概述，您可以从维基百科上的“字符串搜索算法”文章开始。
正如 Martin 所提到的，使用“ Substring index ”对字符串进行索引是一种非常明显的加速方式，这仅适用于对同一字符串进行多次搜索：
"你会怎么做？"
我会做一个基准测试并尝试比较完成相同事情的不同方法来学习哪个是最快的.
在旧版本的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,因此结果与上面的信息没有直接关联,但它仍然有用.
| 归档时间： |
|
| 查看次数： |
5203 次 |
| 最近记录： |