Created
January 7, 2009 15:33
-
-
Save radarek/44301 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
*.rbc | |
*.pyc |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Red Black Tree benchmark for ruby && python. | |
Mainly to comparison different ruby implementations and python version to see how it's related to ruby (for that specific benchmark). | |
How to run? | |
some-ruby --some-options bm1.rb 100 # run bm1.rb with looping 100x times | |
where: | |
some-ruby is you ruby (ruby, ruby1.9, rbx, jruby, maglev etc.) | |
--some-options - specific options for your ruby version (ie. --server fot jruby) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys | |
import time | |
import random | |
from red_black_tree import RedBlackTree | |
import sys | |
minor = sys.version_info[0] | |
if minor >= 3: | |
xrange = range | |
def rbt_bm(): | |
n = 100000 | |
a1 = [random.randint(0, 999999) for x in xrange(0, n)] | |
a2 = [random.randint(0, 999999) for x in xrange(0, n)] | |
start = time.time() | |
tree = RedBlackTree() | |
for i in xrange(0, n): | |
tree.add(i) | |
for i in xrange(0, n): | |
tree.delete(tree.root) | |
tree = RedBlackTree() | |
for x in a1: | |
tree.add(x) | |
for x in a2: | |
tree.search(x) | |
for key in tree.inorder_walk(): | |
key + 1 | |
for key in tree.reverse_inorder_walk(): | |
key + 1 | |
for i in xrange(0, n): | |
tree.maximum() | |
for i in xrange(0, n): | |
tree.minimum() | |
return time.time() - start | |
if len(sys.argv) > 1: | |
n = int(sys.argv[1]) | |
else: | |
n = 5 | |
for i in xrange(0, n): | |
print("%02f" % rbt_bm()) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'red_black_tree' | |
require "benchmark" | |
def rbt_bm | |
n = 100_000 | |
a1 = []; n.times { a1 << rand(999_999) } | |
a2 = []; n.times { a2 << rand(999_999) } | |
start = Time.now | |
tree = RedBlackTree.new | |
n.times {|i| tree.add(i) } | |
n.times { tree.delete(tree.root) } | |
tree = RedBlackTree.new | |
a1.each {|e| tree.add(e) } | |
a2.each {|e| tree.search(e) } | |
tree.inorder_walk {|key| key + 1 } | |
tree.reverse_inorder_walk {|key| key + 1 } | |
n.times { tree.minimum } | |
n.times { tree.maximum } | |
return Time.now - start | |
end | |
N = (ARGV[0] || 5).to_i | |
N.times do | |
puts rbt_bm.to_f | |
puts "GC.count = #{GC.count}" if GC.respond_to?(:count) | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys | |
import time | |
import random | |
from red_black_tree import RedBlackTree | |
import sys | |
def bm(arr): | |
start = time.time() | |
tree = RedBlackTree() | |
for x in arr: | |
tree.add(x) | |
return time.time() - start | |
if len(sys.argv) > 1: | |
n = int(sys.argv[1]) | |
else: | |
n = 5 | |
arr = [] | |
for line in sys.stdin: | |
arr.append(int(line)) | |
for i in range(0, n): | |
print("%02f" % bm(arr)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'red_black_tree' | |
def bm(arr) | |
start = Time.now | |
tree = RedBlackTree.new | |
arr.each do |x| | |
tree.add(x) | |
end | |
return Time.now - start | |
end | |
N = (ARGV[0] || 5).to_i | |
arr = [] | |
$stdin.each_line {|line| arr << line.to_i } | |
N.times do | |
puts bm(arr) | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"fmt" | |
"math/rand" | |
"time" | |
) | |
type Color int | |
const ( | |
Red Color = iota | |
Black | |
) | |
type Node struct { | |
left *Node | |
right *Node | |
parent *Node | |
key int | |
color Color | |
} | |
var NilNode = NewNilNode() | |
func NewNilNode() *Node { | |
node := &Node{color: Black} | |
return node | |
} | |
func NewNode(key int, color Color) *Node { | |
node := &Node{key: key, color: color, left: NilNode, right: NilNode, parent: NilNode} | |
return node | |
} | |
func (self *Node) isRed() bool { | |
return self.color == Red | |
} | |
func (self *Node) isBlack() bool { | |
return self.color == Black | |
} | |
func (self *Node) isNil() bool { | |
return self == NilNode | |
} | |
type RedBlackTree struct { | |
root *Node | |
size int | |
} | |
func NewRedBlackTree() *RedBlackTree { | |
tree := &RedBlackTree{root: NilNode, size: 0} | |
return tree | |
} | |
func (tree *RedBlackTree) add(key int) { | |
tree.insert(NewNode(key, Red)) | |
} | |
func (tree *RedBlackTree) insert(x *Node) { | |
tree.insertHelper(x) | |
x.color = Red | |
for x != tree.root && x.parent.color == Red { | |
if x.parent == x.parent.parent.left { | |
y := x.parent.parent.right | |
if !y.isNil() && y.color == 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 | |
tree.leftRotate(x) | |
} | |
x.parent.color = Black | |
x.parent.parent.color = Red | |
tree.rightRotate(x.parent.parent) | |
} | |
} else { | |
y := x.parent.parent.left | |
if !y.isNil() && y.color == 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 | |
tree.rightRotate(x) | |
} | |
x.parent.color = Black | |
x.parent.parent.color = Red | |
tree.leftRotate(x.parent.parent) | |
} | |
} | |
} | |
tree.root.color = Black | |
} | |
func (tree *RedBlackTree) insertHelper(z *Node) { | |
y := NilNode | |
x := tree.root | |
for !x.isNil() { | |
y = x | |
if z.key < x.key { | |
x = x.left | |
} else { | |
x = x.right | |
} | |
} | |
z.parent = y | |
if y.isNil() { | |
tree.root = z | |
} else { | |
if z.key < y.key { | |
y.left = z | |
} else { | |
y.right = z | |
} | |
} | |
tree.size += 1 | |
} | |
func (tree *RedBlackTree) leftRotate(x *Node) { | |
y := x.right | |
x.right = y.left | |
if !y.left.isNil() { | |
y.left.parent = x | |
} | |
y.parent = x.parent | |
if x.parent.isNil() { | |
tree.root = y | |
} else { | |
if x == x.parent.left { | |
x.parent.left = y | |
} else { | |
x.parent.right = y | |
} | |
} | |
y.left = x | |
x.parent = y | |
} | |
func (tree *RedBlackTree) rightRotate(x *Node) { | |
y := x.left | |
x.left = y.right | |
if !y.right.isNil() { | |
y.right.parent = x | |
} | |
y.parent = x.parent | |
if x.parent.isNil() { | |
tree.root = y | |
} else { | |
if x == x.parent.left { | |
x.parent.left = y | |
} else { | |
x.parent.right = y | |
} | |
} | |
y.right = x | |
x.parent = y | |
} | |
func (tree *RedBlackTree) minimum(x *Node) *Node { | |
if x == nil { | |
x = tree.root | |
} | |
for !x.left.isNil() { | |
x = x.left | |
} | |
return x | |
} | |
func (tree *RedBlackTree) maximum(x *Node) *Node { | |
if x == nil { | |
x = tree.root | |
} | |
for !x.right.isNil() { | |
x = x.right | |
} | |
return x | |
} | |
func (tree *RedBlackTree) successor(x *Node) *Node { | |
if !x.right.isNil() { | |
return tree.minimum(x.right) | |
} | |
y := x.parent | |
for !y.isNil() && x == y.right { | |
x = y | |
y = y.parent | |
} | |
return y | |
} | |
func (tree *RedBlackTree) predecessor(x *Node) *Node { | |
if !x.left.isNil() { | |
return tree.maximum(x.left) | |
} | |
y := x.parent | |
for !y.isNil() && x == y.left { | |
x = y | |
y = y.parent | |
} | |
return y | |
} | |
func (tree *RedBlackTree) delete(z *Node) *Node { | |
var x, y *Node | |
if z.left.isNil() || z.right.isNil() { | |
y = z | |
} else { | |
y = tree.successor(z) | |
} | |
if y.left.isNil() { | |
x = y.right | |
} else { | |
x = y.left | |
} | |
x.parent = y.parent | |
if y.parent.isNil() { | |
tree.root = x | |
} else { | |
if y == y.parent.left { | |
y.parent.left = x | |
} else { | |
y.parent.right = x | |
} | |
} | |
if y != z { | |
z.key = y.key | |
} | |
if y.color == Black { | |
tree.deleteFixup(x) | |
} | |
tree.size -= 1 | |
return y | |
} | |
func (tree *RedBlackTree) deleteFixup(x *Node) { | |
for x != tree.root && x.color == Black { | |
if x == x.parent.left { | |
w := x.parent.right | |
if w.color == Red { | |
w.color = Black | |
x.parent.color = Red | |
tree.leftRotate(x.parent) | |
w = x.parent.right | |
} | |
if w.left.color == Black && w.right.color == Black { | |
w.color = Red | |
x = x.parent | |
} else { | |
if w.right.color == Black { | |
w.left.color = Black | |
w.color = Red | |
tree.rightRotate(w) | |
w = x.parent.right | |
} | |
w.color = x.parent.color | |
x.parent.color = Black | |
w.right.color = Black | |
tree.leftRotate(x.parent) | |
x = tree.root | |
} | |
} else { | |
w := x.parent.left | |
if w.color == Red { | |
w.color = Black | |
x.parent.color = Red | |
tree.rightRotate(x.parent) | |
w = x.parent.left | |
} | |
if w.right.color == Black && w.left.color == Black { | |
w.color = Red | |
x = x.parent | |
} else { | |
if w.left.color == Black { | |
w.right.color = Black | |
w.color = Red | |
tree.leftRotate(w) | |
w = x.parent.left | |
} | |
w.color = x.parent.color | |
x.parent.color = Black | |
w.left.color = Black | |
tree.rightRotate(x.parent) | |
x = tree.root | |
} | |
} | |
} | |
x.color = Black | |
} | |
func (tree *RedBlackTree) search(key int) *Node { | |
x := tree.root | |
for !x.isNil() && x.key != key { | |
if key < x.key { | |
x = x.left | |
} else { | |
x = x.right | |
} | |
} | |
return x | |
} | |
func (tree *RedBlackTree) inorderWalk(callback func(int)) { | |
x := tree.minimum(nil) | |
for !x.isNil() { | |
callback(x.key) | |
x = tree.successor(x) | |
} | |
} | |
func (tree *RedBlackTree) reverseInorderWalk(callback func(int)) { | |
x := tree.maximum(nil) | |
for !x.isNil() { | |
callback(x.key) | |
x = tree.predecessor(x) | |
} | |
} | |
func rbt_bm() time.Duration { | |
n := 100000 | |
a1 := make([]int, 0) | |
a2 := make([]int, 0) | |
for i := 0; i < n; i++ { | |
a1 = append(a1, rand.Int()) | |
a2 = append(a2, rand.Int()) | |
} | |
start := time.Now() | |
tree := NewRedBlackTree() | |
for i := 0; i < n; i++ { | |
tree.add(i) | |
} | |
for i := 0; i < n; i++ { | |
tree.delete(tree.root) | |
} | |
tree = NewRedBlackTree() | |
for _, e := range a1 { | |
tree.add(e) | |
} | |
for _, e := range a2 { | |
tree.search(e) | |
} | |
tree.inorderWalk(func(x int) { | |
_ = x + 1 | |
}) | |
tree.reverseInorderWalk(func(x int) { | |
_ = x + 1 | |
}) | |
for i := 0; i < n; i++ { | |
tree.minimum(nil) | |
} | |
for i := 0; i < n; i++ { | |
tree.maximum(nil) | |
} | |
return time.Now().Sub(start) | |
} | |
func main() { | |
for i := 0; i < 10; i++ { | |
fmt.Println(rbt_bm()) | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node: | |
RED = True | |
BLACK = False | |
def __init__(self, key, color = RED): | |
if not type(color) == bool: | |
raise TypeError("Bad value for color parameter, expected True/False but given %s" % color) | |
self.color = color | |
self.key = key | |
self.left = self.right = self.parent = NilNode.instance() | |
def __str__(self, level = 0, indent = " "): | |
s = level * indent + str(self.key) | |
if self.left: | |
s = s + "\n" + self.left.__str__(level + 1, indent) | |
if self.right: | |
s = s + "\n" + self.right.__str__(level + 1, indent) | |
return s | |
def __nonzero__(self): | |
return True | |
def __bool__(self): | |
return True | |
class NilNode(Node): | |
__instance__ = None | |
@classmethod | |
def instance(self): | |
if self.__instance__ is None: | |
self.__instance__ = NilNode() | |
return self.__instance__ | |
def __init__(self): | |
self.color = Node.BLACK | |
self.key = None | |
self.left = self.right = self.parent = None | |
def __nonzero__(self): | |
return False | |
def __bool__(self): | |
return False | |
class RedBlackTree: | |
def __init__(self): | |
self.root = NilNode.instance() | |
self.size = 0 | |
def __str__(self): | |
return ("(root.size = %d)\n" % self.size) + str(self.root) | |
def add(self, key): | |
self.insert(Node(key)) | |
def insert(self, x): | |
self.__insert_helper(x) | |
x.color = Node.RED | |
while x != self.root and x.parent.color == Node.RED: | |
if x.parent == x.parent.parent.left: | |
y = x.parent.parent.right | |
if y and y.color == Node.RED: | |
x.parent.color = Node.BLACK | |
y.color = Node.BLACK | |
x.parent.parent.color = Node.RED | |
x = x.parent.parent | |
else: | |
if x == x.parent.right: | |
x = x.parent | |
self.__left_rotate(x) | |
x.parent.color = Node.BLACK | |
x.parent.parent.color = Node.RED | |
self.__right_rotate(x.parent.parent) | |
else: | |
y = x.parent.parent.left | |
if y and y.color == Node.RED: | |
x.parent.color = Node.BLACK | |
y.color = Node.BLACK | |
x.parent.parent.color = Node.RED | |
x = x.parent.parent | |
else: | |
if x == x.parent.left: | |
x = x.parent | |
self.__right_rotate(x) | |
x.parent.color = Node.BLACK | |
x.parent.parent.color = Node.RED | |
self.__left_rotate(x.parent.parent) | |
self.root.color = Node.BLACK | |
def delete(self, z): | |
if not z.left or not z.right: | |
y = z | |
else: | |
y = self.successor(z) | |
if not y.left: | |
x = y.right | |
else: | |
x = y.left | |
x.parent = y.parent | |
if not y.parent: | |
self.root = x | |
else: | |
if y == y.parent.left: | |
y.parent.left = x | |
else: | |
y.parent.right = x | |
if y != z: z.key = y.key | |
if y.color == Node.BLACK: | |
self.__delete_fixup(x) | |
self.size -= 1 | |
return y | |
def minimum(self, x = None): | |
if x is None: x = self.root | |
while x.left: | |
x = x.left | |
return x | |
def maximum(self, x = None): | |
if x is None: x = self.root | |
while x.right: | |
x = x.right | |
return x | |
def successor(self, x): | |
if x.right: | |
return self.minimum(x.right) | |
y = x.parent | |
while y and x == y.right: | |
x = y | |
y = y.parent | |
return y | |
def predecessor(self, x): | |
if x.left: | |
return self.maximum(x.left) | |
y = x.parent | |
while y and x == y.left: | |
x = y | |
y = y.parent | |
return y | |
def inorder_walk(self, x = None): | |
if x is None: x = self.root | |
x = self.minimum() | |
while x: | |
yield x.key | |
x = self.successor(x) | |
def reverse_inorder_walk(self, x = None): | |
if x is None: x = self.root | |
x = self.maximum() | |
while x: | |
yield x.key | |
x = self.predecessor(x) | |
def search(self, key, x = None): | |
if x is None: x = self.root | |
while x and x.key != key: | |
if key < x.key: | |
x = x.left | |
else: | |
x = x.right | |
return x | |
def is_empty(self): | |
return bool(self.root) | |
def black_height(self, x = None): | |
if x is None: x = self.root | |
height = 0 | |
while x: | |
x = x.left | |
if not x or x.is_black(): | |
height += 1 | |
return height | |
def __left_rotate(self, x): | |
if not x.right: | |
raise "x.right is nil!" | |
y = x.right | |
x.right = y.left | |
if y.left: y.left.parent = x | |
y.parent = x.parent | |
if not x.parent: | |
self.root = y | |
else: | |
if x == x.parent.left: | |
x.parent.left = y | |
else: | |
x.parent.right = y | |
y.left = x | |
x.parent = y | |
def __right_rotate(self, x): | |
if not x.left: | |
raise "x.left is nil!" | |
y = x.left | |
x.left = y.right | |
if y.right: y.right.parent = x | |
y.parent = x.parent | |
if not x.parent: | |
self.root = y | |
else: | |
if x == x.parent.left: | |
x.parent.left = y | |
else: | |
x.parent.right = y | |
y.right = x | |
x.parent = y | |
def __insert_helper(self, z): | |
y = NilNode.instance() | |
x = self.root | |
while x: | |
y = x | |
if z.key < x.key: | |
x = x.left | |
else: | |
x = x.right | |
z.parent = y | |
if not y: | |
self.root = z | |
else: | |
if z.key < y.key: | |
y.left = z | |
else: | |
y.right = z | |
self.size += 1 | |
def __delete_fixup(self, x): | |
while x != self.root and x.color == Node.BLACK: | |
if x == x.parent.left: | |
w = x.parent.right | |
if w.color == Node.RED: | |
w.color = Node.BLACK | |
x.parent.color = Node.RED | |
self.__left_rotate(x.parent) | |
w = x.parent.right | |
if w.left.color == Node.BLACK and w.right.color == Node.BLACK: | |
w.color = Node.RED | |
x = x.parent | |
else: | |
if w.right.color == Node.BLACK: | |
w.left.color = Node.BLACK | |
w.color = Node.RED | |
self.__right_rotate(w) | |
w = x.parent.right | |
w.color = x.parent.color | |
x.parent.color = Node.BLACK | |
w.right.color = Node.BLACK | |
self.__left_rotate(x.parent) | |
x = self.root | |
else: | |
w = x.parent.left | |
if w.color == Node.RED: | |
w.color = Node.BLACK | |
x.parent.color = Node.RED | |
self.__right_rotate(x.parent) | |
w = x.parent.left | |
if w.right.color == Node.BLACK and w.left.color == Node.BLACK: | |
w.color = Node.RED | |
x = x.parent | |
else: | |
if w.left.color == Node.BLACK: | |
w.right.color = Node.BLACK | |
w.color = Node.RED | |
self.__left_rotate(w) | |
w = x.parent.left | |
w.color = x.parent.color | |
x.parent.color = Node.BLACK | |
w.left.color = Node.BLACK | |
self.__right_rotate(x.parent) | |
x = root | |
x.color = Node.BLACK | |
if __name__ == "__main__": | |
tree = RedBlackTree() | |
tree.add(10) | |
tree.add(3) | |
tree.add(7) | |
tree.add(4) | |
tree.add(20) | |
tree.add(15) | |
print(tree) | |
for key in tree.inorder_walk(): | |
print("key = %s" % key) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Algorithm based on "Introduction to Algorithms" by Cormen and others | |
class RedBlackTree | |
class Node | |
attr_accessor :color | |
attr_accessor :key | |
attr_accessor :left | |
attr_accessor :right | |
attr_accessor :parent | |
RED = :red | |
BLACK = :black | |
COLORS = [RED, BLACK].freeze | |
def initialize(key, color = RED) | |
raise ArgumentError, "Bad value for color parameter" unless COLORS.include?(color) | |
@color = color | |
@key = key | |
@left = @right = @parent = NilNode.instance | |
end | |
def black? | |
return color == BLACK | |
end | |
def red? | |
return color == RED | |
end | |
end | |
class NilNode < Node | |
class << self | |
private :new | |
@instance = nil | |
# it's not thread safe | |
def instance | |
if @instance.nil? | |
@instance = new | |
def instance | |
return @instance | |
end | |
end | |
return @instance | |
end | |
end | |
def initialize | |
self.color = BLACK | |
self.key = 0 | |
self.left = nil | |
self.right = nil | |
self.parent = nil | |
end | |
def nil? | |
return true | |
end | |
end | |
include Enumerable | |
attr_accessor :root | |
attr_accessor :size | |
def initialize | |
self.root = NilNode.instance | |
self.size = 0 | |
end | |
def add(key) | |
insert(Node.new(key)) | |
end | |
def insert(x) | |
insert_helper(x) | |
x.color = Node::RED | |
while x != root && x.parent.color == Node::RED | |
if x.parent == x.parent.parent.left | |
y = x.parent.parent.right | |
if !y.nil? && y.color == Node::RED | |
x.parent.color = Node::BLACK | |
y.color = Node::BLACK | |
x.parent.parent.color = Node::RED | |
x = x.parent.parent | |
else | |
if x == x.parent.right | |
x = x.parent | |
left_rotate(x) | |
end | |
x.parent.color = Node::BLACK | |
x.parent.parent.color = Node::RED | |
right_rotate(x.parent.parent) | |
end | |
else | |
y = x.parent.parent.left | |
if !y.nil? && y.color == Node::RED | |
x.parent.color = Node::BLACK | |
y.color = Node::BLACK | |
x.parent.parent.color = Node::RED | |
x = x.parent.parent | |
else | |
if x == x.parent.left | |
x = x.parent | |
right_rotate(x) | |
end | |
x.parent.color = Node::BLACK | |
x.parent.parent.color = Node::RED | |
left_rotate(x.parent.parent) | |
end | |
end | |
end | |
root.color = Node::BLACK | |
end | |
alias << insert | |
def delete(z) | |
y = (z.left.nil? || z.right.nil?) ? z : successor(z) | |
x = y.left.nil? ? y.right : y.left | |
x.parent = y.parent | |
if y.parent.nil? | |
self.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.color == Node::BLACK | |
delete_fixup(x) | |
end | |
self.size -= 1 | |
return y | |
end | |
def minimum(x = root) | |
while !x.left.nil? | |
x = x.left | |
end | |
return x | |
end | |
def maximum(x = root) | |
while !x.right.nil? | |
x = x.right | |
end | |
return x | |
end | |
def successor(x) | |
if !x.right.nil? | |
return minimum(x.right) | |
end | |
y = x.parent | |
while !y.nil? && x == y.right | |
x = y | |
y = y.parent | |
end | |
return y | |
end | |
def predecessor(x) | |
if !x.left.nil? | |
return maximum(x.left) | |
end | |
y = x.parent | |
while !y.nil? && x == y.left | |
x = y | |
y = y.parent | |
end | |
return y | |
end | |
def inorder_walk(x = root) | |
x = self.minimum | |
while !x.nil? | |
yield x.key | |
x = successor(x) | |
end | |
end | |
alias each inorder_walk | |
def reverse_inorder_walk(x = root) | |
x = self.maximum | |
while !x.nil? | |
yield x.key | |
x = predecessor(x) | |
end | |
end | |
alias reverse_each reverse_inorder_walk | |
def search(key, x = root) | |
while !x.nil? && x.key != key | |
key < x.key ? x = x.left : x = x.right | |
end | |
return x | |
end | |
def empty? | |
return self.root.nil? | |
end | |
def black_height(x = root) | |
height = 0 | |
while !x.nil? | |
x = x.left | |
height +=1 if x.nil? || x.black? | |
end | |
return height | |
end | |
private | |
def left_rotate(x) | |
raise "x.right is nil!" if x.right.nil? | |
y = x.right | |
x.right = y.left | |
y.left.parent = x if !y.left.nil? | |
y.parent = x.parent | |
if x.parent.nil? | |
self.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 right_rotate(x) | |
raise "x.left is nil!" if x.left.nil? | |
y = x.left | |
x.left = y.right | |
y.right.parent = x if !y.right.nil? | |
y.parent = x.parent | |
if x.parent.nil? | |
self.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 insert_helper(z) | |
y = NilNode.instance | |
x = root | |
while !x.nil? | |
y = x | |
z.key < x.key ? x = x.left : x = x.right | |
end | |
z.parent = y | |
if y.nil? | |
self.root = z | |
else | |
z.key < y.key ? y.left = z : y.right = z | |
end | |
self.size += 1 | |
end | |
def delete_fixup(x) | |
while x != root && x.color == Node::BLACK | |
if x == x.parent.left | |
w = x.parent.right | |
if w.color == Node::RED | |
w.color = Node::BLACK | |
x.parent.color = Node::RED | |
left_rotate(x.parent) | |
w = x.parent.right | |
end | |
if w.left.color == Node::BLACK && w.right.color == Node::BLACK | |
w.color = Node::RED | |
x = x.parent | |
else | |
if w.right.color == Node::BLACK | |
w.left.color = Node::BLACK | |
w.color = Node::RED | |
right_rotate(w) | |
w = x.parent.right | |
end | |
w.color = x.parent.color | |
x.parent.color = Node::BLACK | |
w.right.color = Node::BLACK | |
left_rotate(x.parent) | |
x = root | |
end | |
else | |
w = x.parent.left | |
if w.color == Node::RED | |
w.color = Node::BLACK | |
x.parent.color = Node::RED | |
right_rotate(x.parent) | |
w = x.parent.left | |
end | |
if w.right.color == Node::BLACK && w.left.color == Node::BLACK | |
w.color = Node::RED | |
x = x.parent | |
else | |
if w.left.color == Node::BLACK | |
w.right.color = Node::BLACK | |
w.color = Node::RED | |
left_rotate(w) | |
w = x.parent.left | |
end | |
w.color = x.parent.color | |
x.parent.color = Node::BLACK | |
w.left.color = Node::BLACK | |
right_rotate(x.parent) | |
x = root | |
end | |
end | |
end | |
x.color = Node::BLACK | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# updated results (now run on mac os x so they are different than old one) | |
# As you can see rubinius is the fastest one for this specific benchmark | |
# (and I remember that it was about the same speed as jruby/mri about 6 months ago). | |
# I believe this benchmark is not so specific to rubinius so I hope that rubinius | |
# guys will keep up the good work. Seriously guys, I love you :). | |
# ruby.old is default ruby installation on mac os x 10.6 | |
$ ruby.old --version && ruby.old -I. bm1.rb 3 | |
ruby 1.8.7 (2009-06-12 patchlevel 174) [universal-darwin10.0] | |
12.877407 | |
12.714056 | |
12.711498 | |
12.741095 | |
12.629786 | |
$ ruby --version && ruby -I. bm1.rb 5 | |
ruby 1.8.7 (2009-12-24 patchlevel 248) [i686-darwin10.0.0], MBARI 0x6770, Ruby Enterprise Edition 2010.01 | |
11.430688 | |
11.527716 | |
11.671069 | |
11.685053 | |
11.567304 | |
# we run it 20x because jvm needs more time to warm up (jit) | |
$ jruby --version && jruby --server bm1.rb 20 | |
jruby 1.5.2 (ruby 1.8.7 patchlevel 249) (2010-08-20 1c5e29d) (Java HotSpot(TM) 64-Bit Server VM 1.6.0_20) [x86_64-java] | |
6.251 | |
3.536 | |
3.64 | |
3.666 | |
3.463 | |
3.488 | |
3.452 | |
3.36 | |
3.488 | |
3.547 | |
3.462 | |
3.413 | |
3.464 | |
3.446 | |
3.416 | |
3.431 | |
3.429 | |
3.462 | |
3.45 | |
3.67 | |
# the same case but with --fast magic option! | |
$ jruby --version && jruby --server --fast bm1.rb 20 | |
jruby 1.5.2 (ruby 1.8.7 patchlevel 249) (2010-08-20 1c5e29d) (Java HotSpot(TM) 64-Bit Server VM 1.6.0_20) [x86_64-java] | |
5.832 | |
3.388 | |
2.995 | |
3.12 | |
2.993 | |
3.07 | |
3.077 | |
3.053 | |
2.971 | |
2.908 | |
2.984 | |
2.973 | |
3.005 | |
3.115 | |
2.985 | |
3.011 | |
2.875 | |
2.892 | |
3.007 | |
2.985 | |
$ ruby-trunk --version && ruby-trunk -I. bm1.rb 5 | |
ruby 1.9.3dev (2010-09-06 trunk 29190) [x86_64-darwin10.4.0] | |
5.355459 | |
GC.count = 7 | |
5.412945 | |
GC.count = 9 | |
5.439458 | |
GC.count = 12 | |
5.43296 | |
GC.count = 14 | |
5.383552 | |
GC.count = 16 | |
$ rbx --version && rbx -I. bm1.rb 20 | |
rubinius 1.0.1 (1.8.7 9191de6c 2010-06-03 JI) [x86_64-apple-darwin10.4.0] | |
2.208848 | |
1.1334840000000002 | |
1.152181 | |
1.115856 | |
1.108351 | |
1.140871 | |
1.094401 | |
1.191103 | |
1.126919 | |
1.099199 | |
1.132336 | |
1.135996 | |
1.123894 | |
1.127398 | |
1.089978 | |
1.125649 | |
1.123299 | |
1.104524 | |
1.141342 | |
1.089031 | |
$ python3 --version && python3 bm1.py 5 | |
Python 3.1.2 | |
11.031023 | |
11.283902 | |
11.486423 | |
11.280034 | |
11.337633 | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment