Project1

标题: 【效率测试】Ruby中include方法的效率问题 [打印本页]
作者: 寒冷魔王    时间: 2015-1-28 13:08
标题: 【效率测试】Ruby中include方法的效率问题
本帖最后由 寒冷魔王 于 2015-1-28 13:18 编辑

昨天重构了SMRC，新建类Point表示点的坐标，期间运用到了include方法。发现这个版本比上次发布的版本效率要快1倍。
今天调试了半天，终于找到了原因：include方法判断的内容：数组还是类。
如下发布测试代码：
  1. class Test
  2.   def self.test(string,&block)
  3.     time = Time.new
  4.     block.call
  5.     puts string,Time.new-time
  6.   end
  7. end

  9. class Point
  10.   attr_accessor :x, :y
  11.   def initialize(x, y)
  12.     @x = x
  13.     @y = y
  14.   end
  15.   def ==(point)
  16.     return @x==point.x && @y==point.y
  17.   end
  18. end

  20. point1 = Array.new
  21. point2 = Array.new
  22. max = 10000000

  24. Test.test("Push Class Point") { max.times { |i| point1.push Point.new(i,i) } }
  25. Test.test("Push Class Array") { max.times { |i| point2.push [i,i] } }
  26. Test.test("Include Class Point") { point1.include?(Point.new(max,0)) } # 取最坏情况
  27. Test.test("Include Class Array") { point2.include?([max,0]) }
复制代码
结果
  1. Push Class Point
  2. 3.588006
  3. Push Class Array
  4. 2.277604
  5. Include Class Point
  6. 1.060802
  7. Include Class Array
  8. 2.168404
复制代码
这个测试表明，使用include方法判断数组时，效率要比判断类（在类内内建方法"=="）慢得多。虽然构建对象时，数组对象的构建速度要快一些。

（注：如果想要测试，请使用控制台窗口运行，否则发生死机现象与本人无关。）

围观：@taroxd  @RyanBern  
作者: RyanBern    时间: 2015-1-28 14:24
我的测试结果：

因为机子太慢我改成5000000了TAT

啥？为啥不一样？因为我改了源码。
RUBY 代码复制
  1. class Test
  2.   def self.test(string,&block)
  3.     time = Time.new
  4.     block.call
  5.     puts string,Time.new-time
  6.   end
  7. end
  8.  
  9. class Point
  10.   attr_accessor :x, :y
  11.   def initialize(x, y)
  12.     @x = x
  13.     @y = y
  14.   end
  15.   def ==(point)
  16.     return @x==point.x && @y==point.y
  17.   end
  18. end
  19.  
  20. class Array
  21.   def point_include?(point_arr)
  22.     self.each do |point|
  23.       return true if point[0] == point_arr[0] && point[1] == point_arr[1]
  24.     end
  25.     return false
  26.   end
  27. end
  28.  
  29.  
  30. point1 = Array.new
  31. point2 = Array.new
  32. max = 5000000
  33.  
  34. Test.test("Push Class Point") { max.times { |i| point1.push Point.new(i,i) } }
  35.  
  36. Test.test("Push Class Array") { max.times { |i| point2.push [i,i] } }
  37.  
  38. Test.test("Include Class Point") { point1.include?(Point.new(max,0)) } # 取最坏情况
  39.  
  40. Test.test("Include Class Array") { point2.point_include?([max,0]) }

总觉得Array#==方法太不自然了。
作者: 寒冷魔王    时间: 2015-1-28 14:58
本帖最后由 寒冷魔王 于 2015-1-28 14:59 编辑
RyanBern 发表于 2015-1-28 14:24
我的测试结果：

因为机子太慢我改成5000000了TAT


我的那段程序的三个改法：（地图100*100，移动100）

第一个是使用数组+默认include的结果
第二个是我用Point类优化的结果
第三个是用你的方法更改我的程序所得的结果

第二三个差不多，第一个差许多。。果然Ruby的Array效率低啊。。
作者: 寒冷魔王    时间: 2015-1-28 15:06
本帖最后由 寒冷魔王 于 2015-1-28 15:26 编辑
RyanBern 发表于 2015-1-28 14:24
我的测试结果：

因为机子太慢我改成5000000了TAT


RUBY 代码复制
  1. class Test
  2.   def self.test(string,&block)
  3.     time = Time.new
  4.     block.call
  5.     puts string,Time.new-time
  6.   end
  7. end
  8.  
  9. point = Array.new
  10. max = 10000000
  11.  
  12. Test.test("Push Class Array") { max.times { |i| point.push [i,i] } }
  13. Test.test("Include Class Array") { point.include?([max,0]) } # 取最坏情况
  14. Test.test("Do Class Array") { point.each { |p| break if p==[max,0] } # 迭代+判断 }
  15. Test.test("Do2 Class Array") { point.each { |p| } } # 纯迭代
  16. Test.test("Do3 Class Array") { point.each { |p| a=p;a==p } } # 赋值+判断自身引用
  17. Test.test("Each_Index Class Array")  { point.each_index { |i| } } # Each_Index迭代
  18. #Test.test("Each_Index2 Class Array") { point.each_index { |i| p==[i,i] } }  # ！！卡死
  19. Test.test("For Class Array")  { for i in 0...point.size; end  } # For迭代
结果
RUBY 代码复制
  1. Push Class Array
  2. 2.076804
  3. Include Class Array
  4. 2.170404
  5. Do Class Array
  6. 3.902007
  7. Do2 Class Array
  8. 0.624001
  9. Do3 Class Array
  10. 1.113064
  11. Each_Index Class Array
  12. 0.622035
  13. For Class Array
  14. 0.641037


感觉而言，Include 和 迭代+Ruby实现的判断，差不多。
根据以上测试，include效率低下应该是Array自身的判断==问题。
Array先判断是否是自身引用，然后再判断数组元素。

总而言之，Ruby的Array类是个效率非常低的类= =
作者: taroxd    时间: 2015-1-30 07:50
本帖最后由 taroxd 于 2015-1-30 07:56 编辑

为何不用 Hash 或者 Set？

顺便提一句，数组在算 hash 的时候也很慢。

RUBY 代码复制
  1. require 'benchmark'
  2.  
  3. time = 10_000_000
  4.  
  5. default_proc = -> h, k { h[k] = Hash.new(&default_proc) }
  6.  
  7. hash = Hash.new(&default_proc)
  8.  
  9. array_key = 1,2,3,4,5
  10.  
  11. hash[array_key] = hash[1][2][3][4][5] = 0
  12.  
  13. Benchmark.bmbm do |x|
  14.   x.report("embed key") { time.times { hash[1][2][3][4][5] } }
  15.   x.report("array key") { time.times { hash[array_key] } }
  16. end
  17.  
  18. =begin
  19. Rehearsal ---------------------------------------------
  20. embed key   1.700000   0.000000   1.700000 (  1.704098)
  21. array key  14.633000   0.000000  14.633000 ( 14.631836)
  22. ----------------------------------- total: 16.333000sec
  23.  
  24.                 user     system      total        real
  25. embed key   1.669000   0.000000   1.669000 (  1.665095)
  26. array key  14.493000   0.000000  14.493000 ( 14.530831)
  27. =end




欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1