一次提高代码性能的尝试

2016-04-20 本文已影响45人 kamionayuki

在做一道题时碰到的问题，记录下来，备忘
题目：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

一次提高代码性能的尝试

将all?改为了any?,这样就不需要遍历整个hash了。

提升很明显！

猜你喜欢

热点阅读