This documentation is automatically generated by online-judge-tools/verification-helper
benchmarks/datastructure/smultiset/treap.cr
- View this file on GitHub
- Last update: 2022-01-16 12:19:16+09:00
Depends on
- benchmarks/datastructure/sset_benchmark_helper.cr
- src/datastructure/binary_tree.cr
- src/datastructure/smultiset/treap.cr
Code
require "../../../src/datastructure/smultiset/treap"
require "../sset_benchmark_helper"
benchmark_sset_add_delete(SMultiSet::Treap)
puts
benchmark_sset_split(SMultiSet::Treap)# require "../../../src/datastructure/smultiset/treap"
# 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
class SMultiSet::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?
u, prev = node.key < u.key ? 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 << "SMultiSet::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 "../sset_benchmark_helper"
require "benchmark"
private class Foo
getter x
include Comparable(Foo)
def initialize(@x = 0)
end
def <=>(other : Foo)
x <=> other.x
end
end
private class SlowCmp
include Comparable(SlowCmp)
def initialize(size)
@array = Array(Int32).new(size) { yield }
end
def initialize
@array = [] of Int32
end
def <=>(other : SlowCmp)
@array.sum <=> other.@array.sum
end
end
private def add_delete(x, type : S.class, label, values) forall S
index = (0...values.size).to_a.shuffle Random.new(123)
x.report(label) do
s = S(typeof(values.first)).new
values.each { |x| s.add x }
index.each { |i| s.delete values[i] }
end
end
private def split(x, type : T.class, label, values, split_key) forall T
x.report(label) do
s = T.new values
_, _ = s.split(split_key)
end
end
def benchmark_sset_add_delete(type : S.class) forall S
r = Random.new(12345)
values3 = Array.new(10**3, &.itself)
values6 = Array.new(10**6, &.itself)
puts "-------- add, delete --------"
Benchmark.ips do |x|
add_delete x, S, "Int32 1e3 sorted", values3
add_delete x, S, "Int32 1e3 ", values3.shuffle(r)
add_delete x, S, "Int32 1e6 sorted", values6
add_delete x, S, "Int32 1e6 ", values6.shuffle(r)
add_delete x, S, "Int32 1e3 * 1e3 ", values6.map { |x| x % 1000 }.shuffle!(r)
add_delete x, S, "Array 1e6 * 1e2 ", Array.new(10**6) { Array.new(10**2) { r.rand(100) } }
add_delete x, S, "class 1e6 ", Array.new(10**6) { Foo.new r.rand(100) }
add_delete x, S, "SlowC 1e6 * 1e2 ", Array.new(10**6) { SlowCmp.new(100) { r.rand(100) } }
end
end
def benchmark_sset_split(type : S.class) forall S
values6 = Array.new(10**6, &.itself)
puts "-------- split --------"
Benchmark.ips do |x|
split x, S, "Int32 5e5+5e5", values6, 5_000_000
split x, S, "Int32 1e5+9e5", values6, 1_000_000
end
end
benchmark_sset_add_delete(SMultiSet::Treap)
puts
benchmark_sset_split(SMultiSet::Treap)