【效率测试】Ruby中include方法的效率问题

寒冷魔王

昨天重构了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
   
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. point1 = Array.new
    
21. point2 = Array.new
    
22. max = 10000000
    
23. 
    
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

我的测试结果：

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

啥？为啥不一样？因为我改了源码。
[pre lang="Ruby"]class Test
  def self.test(string,&block)
    time = Time.new
    block.call
    puts string,Time.new-time
  end
end

class Point
  attr_accessor :x, :y
  def initialize(x, y)
    @x = x
    @y = y
  end
  def ==(point)
    return @x==point.x && @y==point.y
  end
end

class Array
  def point_include?(point_arr)
    self.each do |point|
      return true if point[0] == point_arr[0] && point[1] == point_arr[1]
    end
    return false
  end
end


point1 = Array.new
point2 = Array.new
max = 5000000

Test.test("Push Class Point") { max.times { |i| point1.push Point.new(i,i) } }

Test.test("Push Class Array") { max.times { |i| point2.push [i,i] } }

Test.test("Include Class Point") { point1.include?(Point.new(max,0)) } # 取最坏情况

Test.test("Include Class Array") { point2.point_include?([max,0]) }
[/pre]
总觉得Array#==方法太不自然了。

寒冷魔王

RyanBern 发表于 2015-1-28 14:24
我的测试结果：

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

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

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

第二三个差不多，第一个差许多。。果然Ruby的Array效率低啊。。

寒冷魔王

RyanBern 发表于 2015-1-28 14:24
我的测试结果：

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

[pre lang="ruby" line="1"]class Test
  def self.test(string,&block)
    time = Time.new
    block.call
    puts string,Time.new-time
  end
end

point = Array.new
max = 10000000

Test.test("Push Class Array") { max.times { |i| point.push [i,i] } }
Test.test("Include Class Array") { point.include?([max,0]) } # 取最坏情况
Test.test("Do Class Array") { point.each { |p| break if p==[max,0] } # 迭代+判断 }
Test.test("Do2 Class Array") { point.each { |p| } } # 纯迭代
Test.test("Do3 Class Array") { point.each { |p| a=p;a==p } } # 赋值+判断自身引用
Test.test("Each_Index Class Array")  { point.each_index { |i| } } # Each_Index迭代
#Test.test("Each_Index2 Class Array") { point.each_index { |i| p==[i,i] } }  # ！！卡死
Test.test("For Class Array")  { for i in 0...point.size; end  } # For迭代  [/pre]结果
[pre lang="ruby" line="1"]Push Class Array
2.076804
Include Class Array
2.170404
Do Class Array
3.902007
Do2 Class Array
0.624001
Do3 Class Array
1.113064
Each_Index Class Array
0.622035
For Class Array
0.641037[/pre]

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

总而言之，Ruby的Array类是个效率非常低的类= =

taroxd

为何不用 Hash 或者 Set？

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

[pre lang="ruby" line="1"]
require 'benchmark'

time = 10_000_000

default_proc = -> h, k { h[k] = Hash.new(&default_proc) }

hash = Hash.new(&default_proc)

array_key = 1,2,3,4,5

hash[array_key] = hash[1][2][3][4][5] = 0

Benchmark.bmbm do |x|
  x.report("embed key") { time.times { hash[1][2][3][4][5] } }
  x.report("array key") { time.times { hash[array_key] } }
end

=begin
Rehearsal ---------------------------------------------
embed key   1.700000   0.000000   1.700000 (  1.704098)
array key  14.633000   0.000000  14.633000 ( 14.631836)
----------------------------------- total: 16.333000sec

                user     system      total        real
embed key   1.669000   0.000000   1.669000 (  1.665095)
array key  14.493000   0.000000  14.493000 ( 14.530831)
=end[/pre]