This documentation is automatically generated by online-judge-tools/verification-helper
benchmarks/datastructure/sset.cr
- View this file on GitHub
- Last update: 2022-01-22 15:32:00+09:00
Depends on
- src/datastructure/binary_tree.cr
- src/datastructure/sset/bucket.cr
- src/datastructure/sset/red_black_tree.cr
- src/datastructure/sset/treap.cr
Code
require "benchmark"
require "../../src/datastructure/sset/red_black_tree"
require "../../src/datastructure/sset/treap"
require "../../src/datastructure/sset/bucket"
private def add(type : T.class, x, label, values) forall T
x.report(label) do
set = T.new
values.each { |x| set.add x }
end
end
private def add_delete(type : T.class, x, label, values) forall T
x.report(label) do
set = T.new
values.each { |x| set.add x }
values.each { |x| set.delete x }
end
end
private def each(type : T.class, x, label, n) forall T
set = T.new 0...n
x.report(label) do
s = 0i64
set.each { |x| s += x }
end
end
private def includes?(type : T.class, x, label, n) forall T
set = T.new (0...n).step(by: 2)
x.report(label) do
(0...n).each { |x| set.includes?(x) }
end
end
private def add_includes?(type : T.class, x, label, values, n) forall T
x.report(label) do
set = T.new
values.each { |x| set << x }
(0...n).each { |x| set.includes?(x) }
end
end
private def ge(type : T.class, x, label, n) forall T
set = T.new (0...n).step(by: 2)
x.report(label) do
(0...n).each { |x| set.ge(x) }
end
end
R = Random.new(42)
values5 = (0...10**5).to_a.shuffle(R)
values6 = (0...10**6).to_a.shuffle(R)
{% begin %}
{% hash = {
"SSet::RedBlackTree" => "RBT",
"SSet::Treap" => "Treap",
"SSet::Bucket(Int32, 1, 170, 0)" => "Bucket( 1, false)",
"SSet::Bucket(Int32, 30, 170, 0)" => "Bucket(30, false)",
"SSet::Bucket(Int32, 60, 170, 0)" => "Bucket(60, false)",
"SSet::Bucket(Int32, 90, 170, 0)" => "Bucket(90, false)",
"SSet::Bucket(Int32, 1, 170, 1)" => "Bucket( 1, true)",
"SSet::Bucket(Int32, 30, 170, 1)" => "Bucket(30, true)",
"SSet::Bucket(Int32, 60, 170, 1)" => "Bucket(60, true)",
"SSet::Bucket(Int32, 90, 170, 1)" => "Bucket(90, true)",
} %}
puts "#add (1e5 times)"
Benchmark.ips do |x|
{% for type, label in hash %} add({{type.id}}, x, {{label}}, values5); {% end %}
end
puts "\n#add and #delete (1e5 times)"
Benchmark.ips do |x|
{% for type, label in hash %} add_delete({{type.id}}, x, {{label}}, values5); {% end %}
end
puts "\n#add (1e6 times)"
Benchmark.ips do |x|
{% for type, label in hash %} add({{type.id}}, x, {{label}}, values6); {% end %}
end
puts "\n#add (1e6 times) and #delete (1e6 times)"
Benchmark.ips do |x|
{% for type, label in hash %} add_delete({{type.id}}, x, {{label}}, values6); {% end %}
end
puts "\n#add (1e6 times) and #includes? (1e6 times)"
Benchmark.ips do |x|
{% for type, label in hash %} add_includes?({{type.id}}, x, {{label}}, values6, 10**6); {% end %}
end
puts "\n#each (1e6 elements)"
Benchmark.ips do |x|
{% for type, label in hash %} each({{type.id}}, x, {{label}}, 10**6); {% end %}
end
puts "\n#includes? (1e6 times with 5e5 elements)"
Benchmark.ips do |x|
{% for type, label in hash %} includes?({{type.id}}, x, {{label}}, 10**6); {% end %}
end
puts "\n#ge (1e6 times with 5e5 elements)"
Benchmark.ips do |x|
{% for type, label in hash %} ge({{type.id}}, x, {{label}}, 10**6); {% end %}
end
{% end %}require "benchmark"
# require "../../src/datastructure/sset/red_black_tree"
# require "../binary_tree"
module TreeNode(T)
abstract def key : T
abstract def left
abstract def right
abstract def parent
def node?
true
end
def nil_node?
false
end
def key? : T?
key
end
def key! : T
key
end
def min_node : self
x = self
while x.left.node?
x = x.left
end
x
end
def max_node : self
x = self
while x.right.node?
x = x.right
end
x
end
def succ : self
if right.node?
return right.min_node
end
x, y = self, parent
while y.node? && x != y.left
x = y
y = y.parent
end
y
end
def pred : self
if left.node?
return left.max_node
end
x, y = self, parent
while y.node? && x != y.right
x = y
y = y.parent
end
y
end
def to_s(io : IO)
io << '[' << key << ']'
end
def inspect(io : IO)
to_s(io)
end
end
module TreeNilNode(T)
def node?
false
end
def nil_node?
true
end
def key? : T?
nil
end
def key!
raise NilAssertionError.new
end
def to_s(io : IO)
io << "NilNode"
end
def inspect(io : IO)
to_s(io)
end
end
module BinaryTree(T, Node, NilNode)
class EmptyError < Exception
def initialize(message = "Empty RedBlackTree")
super(message)
end
end
include Enumerable(T)
include Iterable(T)
abstract def root
abstract def size : Int32
abstract def add?(key : T) : Bool
abstract def delete(key : T) : Bool
def empty? : Bool
root.nil_node?
end
def clear : self
@root = NilNode.new
@size = 0
self
end
def add(key : T) : self
add?(key)
self
end
def <<(key : T) : self
add(key)
end
def rotate_left(x : Node) : Nil
raise "x.right is nil!" if x.right.nil_node?
y = x.right
x.right = y.left
y.left.parent = x if y.left.node?
y.parent = x.parent
if x.parent.nil_node?
@root = y
else
if x == x.parent.left
x.parent.left = y
else
x.parent.right = y
end
end
y.left = x
x.parent = y
end
def rotate_right(x : Node) : Nil
raise "x.left is nil!" if x.left.nil_node?
y = x.left
x.left = y.right
y.right.parent = x if y.right.node?
y.parent = x.parent
if x.parent.nil_node?
@root = y
else
if x == x.parent.left
x.parent.left = y
else
x.parent.right = y
end
end
y.right = x
x.parent = y
end
def min_node : Node
root.min_node
end
def max_node : Node
root.max_node
end
def min? : T?
min_node.key?
end
def min : T
min? || raise EmptyError.new
end
def max? : T?
max_node.key?
end
def max : T
max? || raise EmptyError.new
end
private class InorderWalkIterator(T, Node)
include Iterator(T)
def initialize(@node : Node)
end
def next
if @node.nil_node?
stop
else
@node.key.tap { @node = @node.succ }
end
end
end
def each(node : Node = min_node, &block) : Nil
while node.node?
yield node.key
node = node.succ
end
end
def each(node : Node = min_node)
InorderWalkIterator(T, Node).new(node)
end
private class ReverseInorderWalkIterator(T, Node)
include Iterator(T)
def initialize(@node : Node)
end
def next
if @node.nil_node?
stop
else
@node.key.tap { @node = @node.pred }
end
end
end
def reverse_each(node : Node = max_node, &block) : Nil
while node.node?
yield node.key
node = node.pred
end
end
def reverse_each(node : Node = max_node)
ReverseInorderWalkIterator(T, Node).new(node)
end
def includes?(key : T) : Bool
x = root
loop do
return false if x.nil_node?
cmp = key <=> x.key
return true if cmp == 0
x = cmp < 0 ? x.left : x.right
end
end
def search(key : T, x : Node = root) : Node
while x.node?
cmp = key <=> x.key
break if cmp == 0
x = cmp < 0 ? x.left : x.right
end
x
end
def le_node(key : T, x : Node = root) : Node
loop do
cmp = key <=> x.key
y = cmp < 0 ? x.left : x.right
if y.nil_node?
return cmp < 0 ? x.pred : x
end
x = y
end
end
def lt_node(key : T, x : Node = root) : Node
loop do
cmp = key <=> x.key
y = cmp <= 0 ? x.left : x.right
if y.nil_node?
return cmp <= 0 ? x.pred : x
end
x = y
end
end
def ge_node(key : T, x : Node = root) : Node
loop do
cmp = key <=> x.key
y = cmp <= 0 ? x.left : x.right
if y.nil_node?
return cmp <= 0 ? x : x.succ
end
x = y
end
end
def gt_node(key : T, x : Node = root) : Node
loop do
cmp = key <=> x.key
y = cmp < 0 ? x.left : x.right
if y.nil_node?
return cmp < 0 ? x : x.succ
end
x = y
end
end
{% for method in [:le, :lt, :ge, :gt] %}
def {{method.id}}(key : T) : T?
{{method.id}}_node(key).key?
end
def {{method.id}}!(key : T) : T
{{method.id}}_node(key).key!
end
{% end %}
end
# Copied with modifications from: https://github.com/crystal-lang/crystal/blob/1.1.1/samples/red_black_tree.cr
class SSet::RedBlackTree(T)
class Node(T)
enum Color
Red
Black
end
include TreeNode(T)
property key : T, color : Color
property! left : Node(T), right : Node(T), parent : Node(T)
def initialize(@key : T, @color : Color = :red)
@left = @right = @parent = NilNode(T).new
end
def black?
color.black?
end
def red?
color.red?
end
def split(split_key : T) : {Node(T), Node(T)}
if nil_node?
{NilNode(T).new, NilNode(T).new}
elsif split_key < key
l, r = left.split(split_key)
self.left = r
r.parent = self
{l, self}
else
l, r = right.split(split_key)
self.right = l
l.parent = self
{self, r}
end
end
end
class NilNode(T) < Node(T)
include TreeNilNode(T)
def initialize
@key = uninitialized T
@left = @right = @parent = self
end
end
include BinaryTree(T, Node(T), NilNode(T))
getter root : Node(T), size : Int32 = 0
def initialize
@root = NilNode(T).new
end
def initialize(enumerable : Enumerable(T))
initialize
enumerable.each { |x| self << x }
end
protected def initialize(@root : Node(T))
end
private def insert_node(x : Node(T)) : Nil
insert_helper(x)
x.color = :red
while x != root && x.parent.red?
if x.parent == x.parent.parent.left
y = x.parent.parent.right
if !y.nil_node? && y.red?
x.parent.color = :black
y.color = :black
x.parent.parent.color = :red
x = x.parent.parent
else
if x == x.parent.right
x = x.parent
left_rotate(x)
end
x.parent.color = :black
x.parent.parent.color = :red
right_rotate(x.parent.parent)
end
else
y = x.parent.parent.left
if !y.nil_node? && y.red?
x.parent.color = :black
y.color = :black
x.parent.parent.color = :red
x = x.parent.parent
else
if x == x.parent.left
x = x.parent
right_rotate(x)
end
x.parent.color = :black
x.parent.parent.color = :red
left_rotate(x.parent.parent)
end
end
end
root.color = :black
end
private def delete_node(z : Node(T)) : Nil
y = (z.left.nil_node? || z.right.nil_node?) ? z : z.succ
x = y.left.nil_node? ? y.right : y.left
x.parent = y.parent
if y.parent.nil_node?
@root = x
else
if y == y.parent.left
y.parent.left = x
else
y.parent.right = x
end
end
z.key = y.key if y != z
if y.black?
delete_fixup(x)
end
@size -= 1
y
end
def add?(key : T) : Bool
return false if includes?(key)
insert_node(Node.new(key))
true
end
def delete(key : T) : Bool
node = search(key)
return false if node.nil_node?
delete_node(node)
true
end
def split(key : T) : {self, self}
l, r = root.split(key)
l.parent = NilNode(T).new
r.parent = NilNode(T).new
{RedBlackTree(T).new(l), RedBlackTree(T).new(r)}
end
def black_height(x : Node = root)
height = 0
until x.nil_node?
x = x.left
height += 1 if x.nil_node? || x.black?
end
height
end
def to_s(io : IO) : Nil
io << "SSet::RedBlackTree{"
each_with_index do |x, i|
io << ", " if i > 0
io << x
end
io << '}'
end
def inspect(io : IO) : Nil
to_s(io)
end
private def left_rotate(x : Node)
raise "x.right is nil!" if x.right.nil_node?
y = x.right
x.right = y.left
y.left.parent = x if !y.left.nil_node?
y.parent = x.parent
if x.parent.nil_node?
@root = y
else
if x == x.parent.left
x.parent.left = y
else
x.parent.right = y
end
end
y.left = x
x.parent = y
end
private def right_rotate(x : Node)
raise "x.left is nil!" if x.left.nil_node?
y = x.left
x.left = y.right
y.right.parent = x if !y.right.nil_node?
y.parent = x.parent
if x.parent.nil_node?
@root = y
else
if x == x.parent.left
x.parent.left = y
else
x.parent.right = y
end
end
y.right = x
x.parent = y
end
private def insert_helper(z : Node)
y = NilNode(T).new
x = root
while !x.nil_node?
y = x
x = (z.key < x.key) ? x.left : x.right
end
z.parent = y
if y.nil_node?
@root = z
else
z.key < y.key ? y.left = z : y.right = z
end
@size += 1
end
private def delete_fixup(x : Node)
while x != root && x.black?
if x == x.parent.left
w = x.parent.right
if w.red?
w.color = :black
x.parent.color = :red
left_rotate(x.parent)
w = x.parent.right
end
if w.left.black? && w.right.black?
w.color = :red
x = x.parent
else
if w.right.black?
w.left.color = :black
w.color = :red
right_rotate(w)
w = x.parent.right
end
w.color = x.parent.color
x.parent.color = :black
w.right.color = :black
left_rotate(x.parent)
x = root
end
else
w = x.parent.left
if w.red?
w.color = :black
x.parent.color = :red
right_rotate(x.parent)
w = x.parent.left
end
if w.right.black? && w.left.black?
w.color = :red
x = x.parent
else
if w.left.black?
w.right.color = :black
w.color = :red
left_rotate(w)
w = x.parent.left
end
w.color = x.parent.color
x.parent.color = :black
w.left.color = :black
right_rotate(x.parent)
x = root
end
end
end
x.color = :black
end
end
# require "../../src/datastructure/sset/treap"
# require "../binary_tree"
class SSet::Treap(T)
class Node(T)
include TreeNode(T)
getter key : T, priority : Int32
property! left : Node(T), right : Node(T), parent : Node(T)
def initialize(@key : T, @priority : Int32)
@left = @right = @parent = NilNode(T).new
end
def split(split_key : T) : {Node(T), Node(T)}
if nil_node?
{NilNode(T).new, NilNode(T).new}
elsif split_key < key
l, r = left.split(split_key)
self.left = r
r.parent = self
{l, self}
else
l, r = right.split(split_key)
self.right = l
l.parent = self
{self, r}
end
end
def to_s(io : IO)
io << '[' << key << ']'
end
end
class NilNode(T) < Node(T)
include TreeNilNode(T)
def initialize
@key = uninitialized T
@left = @right = @parent = self
end
end
include BinaryTree(T, Node(T), NilNode(T))
getter root : Node(T), size : Int32 = 0
def initialize
@root = NilNode(T).new
end
def initialize(enumerable : Enumerable(T))
initialize
enumerable.each { |x| self << x }
end
protected def initialize(@root : Node(T))
end
private def add_node(node : Node) : Bool
if empty?
@root = node
@size += 1
return true
end
u, prev = root, NilNode(T).new
while u.node?
cmp = node.key <=> u.key
return false if cmp == 0
u, prev = cmp < 0 ? u.left : u.right, u
end
if node.key < prev.key
prev.left = node
else
prev.right = node
end
node.parent = prev
@size += 1
true
end
private def bubble_up(u : Node) : Nil
raise "u is nil node" unless u.node?
while u.parent.node? && u.parent.priority > u.priority
if u.parent.right == u
rotate_left(u.parent)
else
rotate_right(u.parent)
end
end
@root = u if u.parent.nil_node?
end
def add?(key : T) : Bool
u = Node.new(key, rand(Int32))
add_node(u).tap do |f|
bubble_up(u) if f
end
end
private def trickle_down(u : Node(T))
loop do
l, r = u.left.node?, u.right.node?
break unless l || r
if !l
rotate_left(u)
elsif !r
rotate_right(u)
elsif u.left.priority < u.right.priority
rotate_right(u)
else
rotate_left(u)
end
@root = u.parent if root == u
end
end
def delete(key : T) : Bool
u = search(key)
return false if u.nil_node?
trickle_down(u)
if u.parent.left == u
u.parent.left = NilNode(T).new
else
u.parent.right = NilNode(T).new
end
@size -= 1
if size == 0
@root = NilNode(T).new
end
true
end
def split(key : T) : {self, self}
l, r = root.split(key)
l.parent = NilNode(T).new
r.parent = NilNode(T).new
{Treap(T).new(l), Treap(T).new(r)}
end
def to_s(io : IO) : Nil
io << "SSet::Treap{"
each_with_index do |x, i|
io << ", " if i > 0
io << x
end
io << '}'
end
def inspect(io : IO) : Nil
to_s(io)
end
end
# require "../../src/datastructure/sset/bucket"
# reference: https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
class SSet::Bucket(T, BUCKET_RATIO, REBUILD_RATIO, BSEARCH)
include Enumerable(T)
include Iterable(T)
include Indexable(T)
getter size = 0
@buckets = [] of Array(T)
def initialize
end
def initialize(a : Enumerable(T))
build a.to_a.sort!.uniq!
end
private def build(a : Array(T)) : Nil
@size = a.size
bucket_size = Math.sqrt(size / BUCKET_RATIO).ceil.to_i
@buckets = Array.new(bucket_size) { |i| a[size * i // bucket_size...size * (i + 1) // bucket_size] }
end
private def build
build to_a
end
def empty? : Bool
@size == 0
end
def clear
@size = 0
@buckets.clear
end
def min? : T?
empty? ? nil : @buckets.first.first
end
def min : T
min? || raise EmptyError.new
end
def max? : T?
empty? ? nil : @buckets.last.last
end
def max : T
max? || raise EmptyError.new
end
def each(&) : Nil
@buckets.each do |bucket|
bucket.each do |object|
yield object
end
end
end
private class ItemIterator(T)
include Iterator(T)
def initialize(@buckets : Array(Array(T)))
@i, @j = 0, 0
end
def next
if @buckets.size == @i
stop
else
@buckets[@i][@j].tap do
@j += 1
@i, @j = @i + 1, 0 if @buckets[@i].size == @j
end
end
end
end
def each
ItemIterator(T).new(@buckets)
end
def reverse_each(&) : Nil
@buckets.reverse_each do |bucket|
bucket.reverse_each do |object|
yield object
end
end
end
private def find_bucket(object : T)
{% if BSEARCH > 0 %}
@buckets.bsearch { |bucket| object <= bucket.last } || @buckets.last
{% else %}
@buckets.find(@buckets.last) { |bucket| object <= bucket.last }
{% end %}
end
def includes?(object : T) : Bool
false if empty?
find_bucket(object).bsearch { |x| x >= object } == object
end
def unsafe_fetch(index : Int) : T
@buckets.each do |bucket|
return bucket.unsafe_fetch(index) if index < bucket.size
index -= bucket.size
end
raise "Bug"
end
def add?(object : T) : Bool
if size == 0
@buckets = [[object]]
@size = 1
return true
end
a = find_bucket(object)
i = a.bsearch_index { |x| x >= object }
return false if i && a[i] == object
i ? a.insert(i, object) : a.push(object)
@size += 1
build if a.size > @buckets.size * REBUILD_RATIO
true
end
def add(object : T) : self
add?(object)
self
end
def <<(object : T) : self
add(object)
end
def concat(elems) : self
elems.each { |object| add(object) }
self
end
def delete(object : T) : Bool
return false if empty?
a = find_bucket(object)
i = a.bsearch_index { |x| x >= object }
return false if i.nil? || a[i] != object
a.delete_at(i)
@size -= 1
build if a.empty?
true
end
def count(object : T) : Int32
includes?(object) ? 1 : 0
end
def index(object : T) : Int32?
offset = 0
@buckets.each do |bucket|
if bucket.last >= object
i = bucket.bsearch_index { |x| x >= object }.not_nil!
return offset + i if bucket[i] == object
end
end
end
def index_left(object : T) : Int32
@buckets.reduce(0) do |offset, bucket|
if bucket.last >= object
return offset + bucket.bsearch_index { |x| x >= object }.not_nil!
end
offset + bucket.size
end
end
def index_right(object : T) : Int32?
@buckets.reduce(0) do |offset, bucket|
if bucket.last > object
return offset + bucket.bsearch_index { |x| x > object }.not_nil!
end
offset + bucket.size
end
end
def le(object : T) : T?
@buckets.reverse_each do |bucket|
if bucket.first <= object
i = bucket.bsearch_index { |x| x > object } || bucket.size
return bucket[i - 1]
end
end
end
def lt(object : T) : T?
@buckets.reverse_each do |bucket|
if bucket.first < object
i = bucket.bsearch_index { |x| x >= object } || bucket.size
return bucket[i - 1]
end
end
end
def ge(object : T) : T?
{% if BSEARCH > 0 %}
@buckets.bsearch { |bucket| bucket.last >= object }.try do |bucket|
bucket.bsearch { |x| x >= object }.not_nil!
end
{% else %}
@buckets.each do |bucket|
if bucket.last >= object
return bucket.bsearch { |x| x >= object }.not_nil!
end
end
{% end %}
end
def gt(object : T) : T?
@buckets.each do |bucket|
if bucket.last > object
return bucket.bsearch { |x| x > object }.not_nil!
end
end
end
{% for method in [:le, :lt, :ge, :gt] %}
def {{method.id}}!(object : T) : T
{{method.id}}(object).not_nil!
end
{% end %}
{% for op in [:&, :|, :^, :+, :-] %}
def {{op.id}}(other : Enumerable(T)) : self
SSet::Bucket(T, BUCKET_RATIO, REBUILD_RATIO, BSEARCH).new (self.to_set {{op.id}} other.to_set)
end
{% end %}
def to_a : Array(T)
@buckets.each_with_object(Array(T).new size) do |bucket, a|
a.concat bucket
end
end
def to_s(io : IO) : Nil
io << "SSet::Bucket{"
join(", ", io)
io << "}"
end
def inspect(io : IO) : Nil
@buckets.inspect(io)
end
end
private def add(type : T.class, x, label, values) forall T
x.report(label) do
set = T.new
values.each { |x| set.add x }
end
end
private def add_delete(type : T.class, x, label, values) forall T
x.report(label) do
set = T.new
values.each { |x| set.add x }
values.each { |x| set.delete x }
end
end
private def each(type : T.class, x, label, n) forall T
set = T.new 0...n
x.report(label) do
s = 0i64
set.each { |x| s += x }
end
end
private def includes?(type : T.class, x, label, n) forall T
set = T.new (0...n).step(by: 2)
x.report(label) do
(0...n).each { |x| set.includes?(x) }
end
end
private def add_includes?(type : T.class, x, label, values, n) forall T
x.report(label) do
set = T.new
values.each { |x| set << x }
(0...n).each { |x| set.includes?(x) }
end
end
private def ge(type : T.class, x, label, n) forall T
set = T.new (0...n).step(by: 2)
x.report(label) do
(0...n).each { |x| set.ge(x) }
end
end
R = Random.new(42)
values5 = (0...10**5).to_a.shuffle(R)
values6 = (0...10**6).to_a.shuffle(R)
{% begin %}
{% hash = {
"SSet::RedBlackTree" => "RBT",
"SSet::Treap" => "Treap",
"SSet::Bucket(Int32, 1, 170, 0)" => "Bucket( 1, false)",
"SSet::Bucket(Int32, 30, 170, 0)" => "Bucket(30, false)",
"SSet::Bucket(Int32, 60, 170, 0)" => "Bucket(60, false)",
"SSet::Bucket(Int32, 90, 170, 0)" => "Bucket(90, false)",
"SSet::Bucket(Int32, 1, 170, 1)" => "Bucket( 1, true)",
"SSet::Bucket(Int32, 30, 170, 1)" => "Bucket(30, true)",
"SSet::Bucket(Int32, 60, 170, 1)" => "Bucket(60, true)",
"SSet::Bucket(Int32, 90, 170, 1)" => "Bucket(90, true)",
} %}
puts "#add (1e5 times)"
Benchmark.ips do |x|
{% for type, label in hash %} add({{type.id}}, x, {{label}}, values5); {% end %}
end
puts "\n#add and #delete (1e5 times)"
Benchmark.ips do |x|
{% for type, label in hash %} add_delete({{type.id}}, x, {{label}}, values5); {% end %}
end
puts "\n#add (1e6 times)"
Benchmark.ips do |x|
{% for type, label in hash %} add({{type.id}}, x, {{label}}, values6); {% end %}
end
puts "\n#add (1e6 times) and #delete (1e6 times)"
Benchmark.ips do |x|
{% for type, label in hash %} add_delete({{type.id}}, x, {{label}}, values6); {% end %}
end
puts "\n#add (1e6 times) and #includes? (1e6 times)"
Benchmark.ips do |x|
{% for type, label in hash %} add_includes?({{type.id}}, x, {{label}}, values6, 10**6); {% end %}
end
puts "\n#each (1e6 elements)"
Benchmark.ips do |x|
{% for type, label in hash %} each({{type.id}}, x, {{label}}, 10**6); {% end %}
end
puts "\n#includes? (1e6 times with 5e5 elements)"
Benchmark.ips do |x|
{% for type, label in hash %} includes?({{type.id}}, x, {{label}}, 10**6); {% end %}
end
puts "\n#ge (1e6 times with 5e5 elements)"
Benchmark.ips do |x|
{% for type, label in hash %} ge({{type.id}}, x, {{label}}, 10**6); {% end %}
end
{% end %}