在做一道题时碰到的问题，记录下来，备忘
题目：Substring with Concatenation of All Words
简单就是说，给一个字符串s，再给一个由字符串words（每个字符串的长度一样）组成的数组。遍历s，如果其中的一个子字符串sub_s是可以由words中的所有字符串组成。那么就记录该sub_s的首字符的index。再把所有的index返回成一个数组。
- 最开始的想法很直接，即把words中的所有元素进行一次排列
Array#permutation，然后将排列好的每一个数组join成一个字符串，再用String#index方法找到索引，再返回
def find_substring1(s, words)
array =[]
words.permutation.map(&:join).each do |ele|
array << s.index(ele)
end
array.compact.sort
end
这样写的好处是简洁，充分体现了ruby的优势，但缺点是一旦words中的元素有很多，比如10个以上，那么使用permutation就会生成10!这么多的排列，不仅执行速度上会变得很慢，还很容易溢出。所以这个方法是不可取的。
- 接着尝试了另一种方法
def find_substring2(s, words)
array = []
m = words.first.size
return [] if s.size < words.size
j = 0
until j > s.size - words.size * m
words_dup = words.dup
j.step(s.size-1,m) do |i|
substr = s[i,m]
if words_dup.include? substr
index = words_dup.index(substr)
words_dup.delete_at(index)
if words_dup.empty?
array << j
break
end
else
break
end
end
j += 1
end
array
end
从s[0](j=0)开始，先判断s[0,m](这里假设words中每个字符串的长度是m)是否在words_dup数组中，如果在，则从words_dup数组中删除该字符串，然后再判断s[m,m]是否在words_dup数组中，如果不在，则重新开始，从s[1](j+=1)开始重新判断。如果words_dup为空了，说明s中存在一个子字符串是由words中所有的字符串组成的，此时将j添加到array中，最后返回array。
这样可以满足大部分情况，但是当s或者words特别大的时候，比如：
s = "ab" * 5000
words = ["ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba"]
此时该方法的性能会变得很差。
- 上面方法的瓶颈应该是在include?、index、delete_at这三个方法上。所以想到，是否可以用hash来将字符串的判断变成整数的运算提高性能。
def find_substring3(s, words)
array = []
h = Hash.new(0)
words.each {|ele| h[ele] += 1}
m = words.first.size
return [] if s.size < words.size
j = 0
until j > s.size - words.size * m
hash = h.dup
j.step(s.size-1,m) do |i|
substr = s[i,m]
if hash[substr] > 0
hash[substr] -= 1
if hash.all? {|k,v| v == 0}
array << j
break
end
else
break
end
end
j += 1
end
array
end
整个判断逻辑是一样的，不同的是，在最开始的时候，将words数组转化为了一个hash，其中key是words中的字符串元素，value是这些字符串元素在words中的重复次数。这样hash的长度肯定是小于等于words的。省去了一些空间。同时将判断变成了hash[substr] > 0(对应上面方法的include?)、删除元素变成了hash[substr] -= 1(对应上面方法的Index,delete_at)。运行一下看看效果。
结果却变得更慢了！
- 那是什么原因呢？看代码发现有一行是hash.all? {|k,v| v == 0}，此处是判断，当words中所有的字符串的次数都为0里，说明s中存在一个子字符串是由words中所有的字符串组成的。分析可以知道，每次循环，都会去调用all?这个方法，而这个方法是比较耗时的，因为是需要遍历hash中的每一对键值。所以再次修改
def find_substring4(s, words)
array = []
h = Hash.new(0)
words.each {|ele| h[ele] += 1}
m = words.first.size
return [] if s.size < words.size
j = 0
until j > s.size - words.size * m
hash = h.dup
j.step(s.size-1,m) do |i|
substr = s[i,m]
if hash[substr] > 0
hash[substr] -= 1
#这里
unless hash.any? {|k,v| v > 0}
array << j
break
end
else
break
end
end
j += 1
end
array
end
将all?改为了any?,这样就不需要遍历整个hash了。
OK。可以用benchmark看一下结果(因为permutation方法在这种输入的情况下已经溢出了，所以就不执行了)
require 'benchmark'
Benchmark.bm(10) do |t|
t.report("find_substring2") { find_substring2(s, words) }
t.report("find_substring3") { find_substring3(s, words) }
t.report("find_substring4") { find_substring4(s, words) }
end
结果如下：
user system total real
find_substring2 2.329000 0.000000 2.329000 ( 2.327370)
find_substring3 3.312000 0.000000 3.312000 ( 3.376481)
find_substring4 0.609000 0.000000 0.609000 ( 0.620764)
提升很明显！
- 再试着优化一下
def find_substring5(s, words)
array = []
h = Hash.new(0)
words.each {|ele| h[ele] += 1}
m = words.first.size
return [] if s.size < words.size
j = 0
until j > s.size - words.size * m
hash = h.dup
j.step(s.size-1,m) do |i|
substr = s[i,m]
if hash[substr] > 0
hash[substr] -= 1
#这里
hash.delete(substr) if hash[substr] == 0
if hash.empty?
array << j
break
end
else
break
end
end
j += 1
end
array
end
将any?改成有empty?，并且在之前增加了一步操作，如果hash[substr]的重复次数为0，那么就在hash中删除掉该元素。这样在循环的过程中，hash的元素会变小，因此要比any? 操作的数据小一些。
验证一下：
require 'benchmark'
Benchmark.bm(10) do |t|
t.report("find_substring4") { find_substring4(s, words) }
t.report("find_substring5") { find_substring5(s, words) }
end
结果如下：
user system total real
find_substring4 0.610000 0.016000 0.626000 ( 0.624748)
find_substring5 0.531000 0.000000 0.531000 ( 0.526358)
提升不是很明显，但还是有提升的。
试着总结一下（不一定正确，但可以往这个方向去试着优化）
- 如果可以用整数操作，尽量用整数进行操作，比字符串的操作要快
- 一些方法比如permutation、combination用起来很方便，但却是牺牲了空间和时间的
- 另一些方法比如all?需要遍历才能最终判断的，尽量用any?来取代。而empty?的开销还要小一些。
- 一般来说，在大数据的情况下，Hash的表现要高于Array
