This documentation is automatically generated by online-judge-tools/verification-helper
benchmarks/datastructure/sset/bucket.cr
- View this file on GitHub
- Last update: 2022-01-22 15:32:00+09:00
Depends on
Code
require "../sset_benchmark_helper"
require "../../../src/datastructure/sset/bucket"
benchmark_sset_add_delete(SSet::Bucket)# 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
# 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
benchmark_sset_add_delete(SSet::Bucket)