Project

General

Profile

Feature #15281 ยป intersect.rb

RGBD (Oleg Zubchenko), 11/03/2018 12:57 PM

 
1
#!/usr/bin/env ruby
2

    
3
require 'benchmark/ips'
4
require 'set'
5

    
6
class Set
7
  def fast_intersect(enum)
8
    n = self.class.new
9
    if enum.is_a?(Set)
10
      # if enum.size > size
11
      #   each { |o| n.add(o) if enum.include?(o) }
12
      # else
13
        enum.each { |o| n.add(o) if include?(o) }
14
      # end
15
    else
16
      do_with_enum(enum) { |o| n.add(o) if include?(o) }
17
    end
18
    n
19
  end
20

    
21
  def fastest_intersect(enum)
22
    n = self.class.new
23
    if enum.is_a?(Set)
24
      if enum.size > size
25
        each { |o| n.add(o) if enum.include?(o) }
26
      else
27
        enum.each { |o| n.add(o) if include?(o) }
28
      end
29
    else
30
      do_with_enum(enum) { |o| n.add(o) if include?(o) }
31
    end
32
    n
33
  end
34
end
35

    
36
n_values1 = 100
37
size_2_percentage = 0.8
38
overlap_percentage = 0.5
39

    
40
n_values2 = (n_values1 * size_2_percentage).to_i
41
overlap = (n_values2 * overlap_percentage).to_i
42

    
43
a1 = (0...n_values1).to_a
44
a2 = ((n_values1 - overlap)...(n_values1 - overlap + n_values2)).to_a
45
s1 = Set.new(a1)
46
s2 = Set.new(a2)
47
ss1 = SortedSet.new(a1)
48
ss2 = SortedSet.new(a2)
49

    
50
puts s1.size
51
puts s2.size
52
puts((s1 & s2).size)
53

    
54
method_groups = {
55
  Set_Set: {
56
    old: -> { s2 & s1 },
57
    fast: -> { s2.fast_intersect s1 },
58
    fastest: -> { s2.fastest_intersect s1 },
59
  },
60
  Set_SortedSet: {
61
    old: -> { s2 & ss1 },
62
    fast: -> { s2.fast_intersect ss1 },
63
    fastest: -> { s2.fastest_intersect ss1 },
64
  },
65
  SortedSet_Set: {
66
    old: -> { ss2 & s1 },
67
    fast: -> { ss2.fast_intersect s1 },
68
    fastest: -> { ss2.fastest_intersect s1 },
69
  },
70
  SortedSet_SortedSet: {
71
    old: -> { ss2 & ss1 },
72
    fast: -> { ss2.fast_intersect ss1 },
73
    fastest: -> { ss2.fastest_intersect ss1 },
74
  },
75
  Set_Array: {
76
    old: -> { s2 & a1 },
77
    fastest: -> { s2.fast_intersect a1 },
78
  },
79
}
80

    
81
method_groups.each do |group_name, group|
82
  puts '*' * 80
83
  puts group_name
84
  puts '*' * 80
85
  Benchmark.ips do |bm|
86
    group.each do |name, method|
87
      bm.report(name, &method)
88
    end
89

    
90
    bm.compare!
91
  end
92
end