-
-
Save pietia/46852 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
import sys | |
import time | |
import random | |
from red_black_tree import RedBlackTree | |
import sys | |
#import cProfile | |
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()) | |
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
$:.unshift(File.expand_path(File.dirname(__FILE__) + "/../../lib")) | |
require 'red_black_tree' | |
def rbt_bm | |
n = 100000 | |
a1 = []; n.times { a1 << rand(999_999) } | |
a2 = []; n.times { a2 << rand(999_999) } | |
start = Time.now | |
n = 100_000 | |
tree = RedBlackTree.new | |
n.times { tree.insert(RedBlackTree::Node.new(n)) } | |
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 | |
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
RED = 1 | |
BLACK = 2 | |
COLORS = [RED, BLACK] | |
class Node: | |
def __init__(self, key, color = RED): | |
if not color in COLORS: | |
raise TypeError("Bad value for color parameter (%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 | |
#return "<Node @key=%s, @color=%s, @left=%s, @right=%s>" % (self.key, self.color, self.left, self.right) | |
def is_red(self): | |
return self.color == RED | |
def is_black(self): | |
return self.color == BLACK | |
def is_nil(self): | |
return False | |
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 = BLACK | |
self.key = None | |
self.left = self.right = self.parent = None | |
def is_nil(self): | |
return True | |
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 del(key): | |
def insert(self, x): | |
self.__insert_helper(x) | |
x.color = RED | |
while x != self.root and x.parent.color == RED: | |
if x.parent == x.parent.parent.left: | |
y = x.parent.parent.right | |
if not y.is_nil() and 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 | |
self.__left_rotate(x) | |
x.parent.color = BLACK | |
x.parent.parent.color = RED | |
self.__right_rotate(x.parent.parent) | |
else: | |
y = x.parent.parent.left | |
if not y.is_nil() and 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 | |
self.__right_rotate(x) | |
x.parent.color = BLACK | |
x.parent.parent.color = RED | |
self.__left_rotate(x.parent.parent) | |
self.root.color = BLACK | |
def delete(self, z): | |
if z.left.is_nil() or z.right.is_nil(): | |
y = z | |
else: | |
y = self.successor(z) | |
if y.left.is_nil(): | |
x = y.right | |
else: | |
x = y.left | |
x.parent = y.parent | |
if y.parent.is_nil(): | |
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 == BLACK: | |
self.__delete_fixup(x) | |
self.size -= 1 | |
return y | |
def minimum(self, x = None): | |
if x is None: x = self.root | |
while not x.left.is_nil(): | |
x = x.left | |
return x | |
def maximum(self, x = None): | |
if x is None: x = self.root | |
while not x.right.is_nil(): | |
x = x.right | |
return x | |
def successor(self, x): | |
if not x.right.is_nil(): | |
return self.minimum(x.right) | |
y = x.parent | |
while not y.is_nil() and x == y.right: | |
x = y | |
y = y.parent | |
return y | |
def predecessor(self, x): | |
if not x.left.is_nil(): | |
return self.maximum(x.left) | |
y = x.parent | |
while not y.is_nil() 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 not x.is_nil(): | |
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 not x.is_nil(): | |
yield x.key | |
x = self.predecessor(x) | |
def search(self, key, x = None): | |
if x is None: x = self.root | |
while not x.is_nil() and x.key != key: | |
if key < x.key: | |
x = x.left | |
else: | |
x = x.right | |
return x | |
def is_empty(self): | |
return self.root.is_nil() | |
def black_height(self, x = None): | |
if x is None: x = self.root | |
height = 0 | |
while not x.is_nil(): | |
x = x.left | |
if x.is_nil() or x.is_black(): | |
height += 1 | |
return height | |
def __left_rotate(self, x): | |
if x.right.is_nil(): | |
raise "x.right is nil!" | |
y = x.right | |
x.right = y.left | |
if not y.left.is_nil(): y.left.parent = x | |
y.parent = x.parent | |
if x.parent.is_nil(): | |
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 x.left.is_nil(): | |
raise "x.left is nil!" | |
y = x.left | |
x.left = y.right | |
if not y.right.is_nil(): y.right.parent = x | |
y.parent = x.parent | |
if x.parent.is_nil(): | |
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 not x.is_nil(): | |
y = x | |
if z.key < x.key: | |
x = x.left | |
else: | |
x = x.right | |
z.parent = y | |
if y.is_nil(): | |
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 == BLACK: | |
if x == x.parent.left: | |
w = x.parent.right | |
if w.color == RED: | |
w.color = BLACK | |
x.parent.color = RED | |
self.__left_rotate(x.parent) | |
w = x.parent.right | |
if w.left.color == BLACK and w.right.color == BLACK: | |
w.color = RED | |
x = x.parent | |
else: | |
if w.right.color == BLACK: | |
w.left.color = BLACK | |
w.color = RED | |
self.__right_rotate(w) | |
w = x.parent.right | |
w.color = x.parent.color | |
x.parent.color = BLACK | |
w.right.color = BLACK | |
self.__left_rotate(x.parent) | |
x = self.root | |
else: | |
w = x.parent.left | |
if w.color == RED: | |
w.color = BLACK | |
x.parent.color = RED | |
self.__right_rotate(x.parent) | |
w = x.parent.left | |
if w.right.color == BLACK and w.left.color == BLACK: | |
w.color = RED | |
x = x.parent | |
else: | |
if w.left.color == BLACK: | |
w.right.color = BLACK | |
w.color = RED | |
self.__left_rotate(w) | |
w = x.parent.left | |
w.color = x.parent.color | |
x.parent.color = BLACK | |
w.left.color = BLACK | |
self.__right_rotate(x.parent) | |
x = root | |
x.color = 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
# all interpreters built from source | |
$ ruby1.9.1 bm_red_black_tree.rb | |
4.949379389 | |
4.85002854 | |
4.872958709 | |
4.75958293 | |
4.824939178 | |
$ ruby1.8.6 bm_red_black_tree.rb | |
13.245832 | |
13.335391 | |
13.974618 | |
14.115719 | |
13.896763 | |
$ ~/opt/src/jruby/bin/jruby --server bm_red_black_tree.rb 20 | |
6.863479 | |
3.409712 | |
3.545647 | |
3.574088 | |
3.547512 | |
3.498346 | |
3.446358 | |
3.483826 | |
3.313169 | |
3.431394 | |
3.461995 | |
3.326763 | |
3.440695 | |
3.286011 | |
3.390503 | |
3.524378 | |
3.322712 | |
3.435351 | |
3.459602 | |
3.326452 | |
$ ~/opt/src/jruby/bin/jruby --server --fast bm_red_black_tree.rb 20 | |
7.088924 | |
2.298887 | |
2.488584 | |
3.616405 | |
3.743274 | |
2.295828 | |
2.360864 | |
2.294946 | |
2.381404 | |
2.23098 | |
2.389819 | |
2.305196 | |
2.255837 | |
2.354832 | |
2.271856 | |
2.647422 | |
2.436133 | |
2.262261 | |
2.286042 | |
2.461298 | |
$ ~/opt/bin/python bm_red_black_tree.py | |
16.874310 | |
16.919597 | |
16.818060 | |
16.984473 | |
17.225864 | |
$ ~/opt/bin/python2.6 bm_red_black_tree.py | |
16.934663 | |
17.016423 | |
16.703839 | |
17.076022 | |
16.968335 | |
$ ~/opt/bin/python3.0 bm_red_black_tree.py | |
11.534306 | |
11.542991 | |
11.569866 | |
11.713882 | |
11.637492 | |
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
model name : Intel(R) Core(TM)2 Duo CPU T8300 @ 2.40GHz | |
######################## | |
jruby --version | |
jruby 1.1.6 (ruby 1.8.6 patchlevel 114) (2008-12-17 rev 8388) [i386-java] | |
ruby --version | |
ruby 1.8.6 (2008-08-11 patchlevel 287) [i686-linux] | |
python --version | |
Python 2.5.2 | |
jython --version | |
Jython 2.5b1 (trunk:5903:5905, Jan 9 2009, 16:01:29) | |
[Java HotSpot(TM) Server VM (Sun Microsystems Inc.)] on java1.6.0_11 | |
######################## | |
python bm_red_black_tree.py | |
23.203221 | |
26.215589 | |
25.151917 | |
25.242468 | |
24.118340 | |
jython bm_red_black_tree.py | |
18.650000 | |
16.735000 | |
15.966000 | |
15.878000 | |
15.195000 | |
jythonserver bm_red_black_tree.py | |
19.630000 | |
17.668000 | |
15.408000 | |
14.670000 | |
14.703000 | |
ruby bm_red_black_tree.rb | |
10.651496 | |
12.019062 | |
13.499802 | |
13.5671 | |
13.726589 | |
jruby bm_red_black_tree.rb | |
7.42838 | |
7.035626 | |
6.913339 | |
7.105795 | |
7.035911 | |
jruby --server bm_red_black_tree.rb | |
6.531473 | |
4.11704 | |
4.149193 | |
3.979266 | |
4.047518 | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment