有没有更好的方法在合理的时间内比较字符串?
Is there a better way to compare strings in a reasonable amount of time?
我有这个 Ruby 函数,它告诉我两个字符串是否 "almost" 相等,也就是说,字符串中的所有字符是否相同并且以相同的方式排序,除了一个。例如,这些是相等的
equal
eual
但这些不是
eal
equal
(上面少了两个字符)。所以在帮助下,我想出了这个
(lcs(a,b) == shortest && longest.length - shortest.length == 1)
其中las由
定义
def lcs(xstr, ystr)
return "" if xstr.empty? || ystr.empty?
x, xs, y, ys = xstr[0..0], xstr[1..-1], ystr[0..0], ystr[1..-1]
if x == y
x + lcs(xs, ys)
else
[lcs(xstr, ys), lcs(xs, ystr)].max_by {|x| x.size}
end
end
但是我的功能花费了非常长的时间。注意下面我的基准
2.4.0 :011 > timing = Benchmark.measure { StringHelper.lcs("navesxkolsky|1227000", "navsxkolsky|1227000") }
=> #<Benchmark::Tms:0x007fa1753830d8 @label="", @real=21.341279999993276, @cstime=0.0, @cutime=0.0, @stime=0.030000000000000027, @utime=21.28, @total=21.310000000000002>
这里有什么我遗漏的东西可以让我的比较时间缩短到 1 秒而不是 21 秒吗?
试试这个。主要思想是,如果该方法是 return false
,它会在已知时立即这样做,即使需要冗余代码也是如此。 (如果删除行 return false if (sz1-sz2).abs > 1
,下面的方法仍然有效。)
def equal_but_one?(str1, str2)
sz1 = str1.size
sz2 = str2.size
return false if (sz1-sz2).abs > 1
i = [sz1, sz2].max.times.find { |i| str1[i] != str2[i] }
return false if i.nil?
case sz1 <=> sz2
when 0
str1[i+1..-1] == str2[i+1..-1]
when -1
str2[i+1..-1] == str1[i..-1]
when 1
str1[i+1..-1] == str2[i..-1]
end
end
equal_but_one?('cat', 'cut') #=> true
equal_but_one?('bates', 'bats') #=> true
equal_but_one?('buss', 'bus') #=> true
equal_but_one?('cat', 'cat') #=> false
equal_but_one?('pig', 'pigs') #=> true
equal_but_one?('pig', 'pegs') #=> false
equal_but_one?('', '') #=> false
equal_but_one?('', 'a') #=> true
require 'benchmark'
Benchmark.measure { equal_but_one?("navesxkolsky|1227000", "navsxkolsky|1227000") }.real
#=> 1.6000005416572094e-05
我有这个 Ruby 函数,它告诉我两个字符串是否 "almost" 相等,也就是说,字符串中的所有字符是否相同并且以相同的方式排序,除了一个。例如,这些是相等的
equal
eual
但这些不是
eal
equal
(上面少了两个字符)。所以在帮助下,我想出了这个
(lcs(a,b) == shortest && longest.length - shortest.length == 1)
其中las由
定义 def lcs(xstr, ystr)
return "" if xstr.empty? || ystr.empty?
x, xs, y, ys = xstr[0..0], xstr[1..-1], ystr[0..0], ystr[1..-1]
if x == y
x + lcs(xs, ys)
else
[lcs(xstr, ys), lcs(xs, ystr)].max_by {|x| x.size}
end
end
但是我的功能花费了非常长的时间。注意下面我的基准
2.4.0 :011 > timing = Benchmark.measure { StringHelper.lcs("navesxkolsky|1227000", "navsxkolsky|1227000") }
=> #<Benchmark::Tms:0x007fa1753830d8 @label="", @real=21.341279999993276, @cstime=0.0, @cutime=0.0, @stime=0.030000000000000027, @utime=21.28, @total=21.310000000000002>
这里有什么我遗漏的东西可以让我的比较时间缩短到 1 秒而不是 21 秒吗?
试试这个。主要思想是,如果该方法是 return false
,它会在已知时立即这样做,即使需要冗余代码也是如此。 (如果删除行 return false if (sz1-sz2).abs > 1
,下面的方法仍然有效。)
def equal_but_one?(str1, str2)
sz1 = str1.size
sz2 = str2.size
return false if (sz1-sz2).abs > 1
i = [sz1, sz2].max.times.find { |i| str1[i] != str2[i] }
return false if i.nil?
case sz1 <=> sz2
when 0
str1[i+1..-1] == str2[i+1..-1]
when -1
str2[i+1..-1] == str1[i..-1]
when 1
str1[i+1..-1] == str2[i..-1]
end
end
equal_but_one?('cat', 'cut') #=> true
equal_but_one?('bates', 'bats') #=> true
equal_but_one?('buss', 'bus') #=> true
equal_but_one?('cat', 'cat') #=> false
equal_but_one?('pig', 'pigs') #=> true
equal_but_one?('pig', 'pegs') #=> false
equal_but_one?('', '') #=> false
equal_but_one?('', 'a') #=> true
require 'benchmark'
Benchmark.measure { equal_but_one?("navesxkolsky|1227000", "navsxkolsky|1227000") }.real
#=> 1.6000005416572094e-05