連想配列の再発明（線形検索、二分探索木、ハッシュテーブル）してそれぞれの時間計測

class MyHash1
	include Enumerable
	
	Pair = Struct.new( :key, :value )
	
	def initialize
		@table = []
	end
	
	def []( key )
		@table.each do |pair|
			return pair.value if pair.key.eql?( key )
		end
		return nil
	end
	
	def []=( key, value )
		@table.each do |pair|
			if pair.key.eql?( key )
				pair.value = value
				return value
			end
		end
		@table << Pair.new( key, value )
		return value
	end
	
	def delete( key )
		@table.each_with_index do |pair,i|
			if pair.key.eql?( key )
				value = pair.value
				@table.delete_at( i )
				return value
			end
		end
		return nil
	end
	
	def each
		@table.each do |pair|
			yield [pair.key, pair.value]
		end
	end
	
	def inspect
		'{' + map{|key,value|
			key.inspect+'=>'+value.inspect}.join(', ') + '}'
	end
end

class MyHash2
	include Enumerable
	
	#Node = Struct.new( :key, :hash, :value, :left, :right )
	class Node
		def initialize( key, value, left = nil, right = nil )
			@key = key
			@value = value
			@left = left
			@right = right
		end
		
		attr_accessor :key, :value, :left, :right
		
		def each
			@left.each{|v| yield v } if @left
			yield [key, value]
			@right.each{|v| yield v } if @right
		end
		
		def inspect( level = 0 )
			puts ' ' * level + key.inspect + '(' + value.inspect + ')'
			if @left
				puts ' ' * level + 'left:'
				@left.inspect( level + 1 )
			end
			if @right
				puts ' ' * level + 'right:'
				@right.inspect( level + 1 )
			end
		end
	end
	
	def initialize
		@tree = nil
	end
	
	attr_reader :tree
	
	def []( key )
		hash = key.hash
		node = @tree
		loop do
			return nil unless node
			return node.value if node.key.hash == hash && node.key.eql?( key )
			if hash < node.key.hash
				node = node.left
			else
				node = node.right
			end
		end
		return nil
	end
	
	def []=( key, value )
		hash = key.hash
		unless @tree
			@tree = Node.new( key, value )
			return value
		end
		node = @tree
		loop do
			if node.key.hash == hash && node.key.eql?( key )
				node.value = value
				return value
			end
			if hash < node.key.hash
				unless node.left
					node.left = Node.new( key, value )
					return value
				else
					node = node.left
				end
			else
				unless node.right
					node.right = Node.new( key, value )
					return value
				else
					node = node.right
				end
			end
		end
	end
	
	def delete( key )
		hash = key.hash
		node = @tree
		parent = nil
		set_node = proc{|v| @tree = v }
		loop do
			return nil unless node
			if node.key.hash == hash && node.key.eql?( key )
				value = node.value
				if node.left
					other = node.right
					set_node.call( node.left )
					node = node.left
					if other
						n = node
						n = n.right while n.right
						n.right = other
					end
				elsif node.right
					set_node.call( node.right )
				else
					set_node.call( nil )
				end
				return value
			end
			if hash < node.key.hash
				parent = node
				set_node = proc{|v| parent.left = v }
				node = node.left
			else
				parent = node
				set_node = proc{|v| parent.right = v }
				node = node.right
			end
		end
	end
	
	def each
		@tree.each{|v| yield v } if @tree
	end
	
	def inspect
		'{' + map{|key,value|
			key.inspect+'=>'+value.inspect}.join(', ') + '}'
	end
end

class MyHash3
	include Enumerable
	
	Pair = Struct.new( :key, :value )
	
	def initialize( size = 3 )
		@num = 0
		@table = Array.new( size )
	end

	def []( key )
		index = key.hash % @table.size
		list =  @table[index]
		return nil unless list
		list.each do |pair|
			return pair.value if key.eql?( pair.key )
		end
		return nil
	end
	
	def rehash
		new_hash = self.class.new( @table.size * 2 + 1 )
		each do |key,value|
			new_hash[key] = value
		end
		@table = new_hash.instance_variable_get( :@table )
		@num = new_hash.instance_variable_get( :@num )
	end
	
	def []=( key, value )
		index = key.hash % @table.size
		list =  @table[index]
		unless list
			@table[index] = [ Pair.new( key, value ) ]
		else
			list.each do |pair|
				if key.eql?( pair.key )
					pair.value = value
					return value
				end
			end
			list << Pair.new( key, value )
		end
		@num += 1
		rehash if @num.to_f / @table.size >= 3.0 / 4
		return value
	end
	
	def delete( key )
		index = key.hash % @table.size
		list =  @table[index]
		return nil unless list
		list.each_with_index do |pair,i|
			if key.eql?( pair.key )
				value = pair.value
				list.delete_at( i )
				@num -= 1
				return value
			end
		end
		return nil
	end
	
	def each
		@table.each do |list|
			next unless list
			list.each do |pair|
				yield [pair.key, pair.value]
			end
		end
	end
	
	def inspect
		'{' + map{|key,value|
			key.inspect+'=>'+value.inspect}.join(', ') + '}'
	end
end

require 'benchmark'

class_list = [Hash, MyHash1, MyHash2, MyHash3]

Benchmark.bm(10) do |x|
	class_list.each do |c|
		srand 0
		hash = c.new
		x.report( c.name ) do
			10000.times do |i|
				case i % 3
				when 0
					hash[rand(1e5)] = i
				when 1
					hash[rand(1e5)]
				when 2
					hash.delete( rand(1e5) )
				end
			end
		end
		#puts "#{hash.to_a.size} #{hash.to_a.sort.hash}"
	end
end

                user     system      total        real
Hash        0.031000   0.000000   0.031000 (  0.031000)
MyHash1    53.016000   0.047000  53.063000 ( 53.547000)
MyHash2     2.312000   0.000000   2.312000 (  2.312000)
MyHash3     0.406000   0.000000   0.406000 (  0.406000)

MyHash1 が線形検索、MyHash2が二分探索木、MyHash3がハッシュテーブル。
ハッシュテーブルの実装は404 Blog Not Found:アルゴリズム百選 - ハッシュを再発明するを参考に。
二分探索木の実装は、二分探索木 - Wikipediaを参考に。要素の削除は自分で考えた。
平衡2分探索木とやらを使えばもっと効率がいいみたいなので試したい。