require 'ruby-prof'
class Trie
attr_reader :value, :children
attr_accessor :number_exists,
refix
def initialize(value=nil)
@value = value
@children = []
@number_exists = false
@prefix=''
end
def <<(value)
sub_trie = Trie.new(value)
sub_trie.prefix = prefix+value.to_s
children << sub_trie
return sub_trie
end
def each
info = [value, children, number_exists, prefix]
yield(info)
@children.each do |child_node|
child_node.each { |e| yield e }
end
end
def output(opt='all')
if(opt.is_a?(String))
if(opt.downcase=='all')
each do |x|
if(x[3]!='')
if(x[2])
puts x[3]
end
end
end
else
puts "Error: '#{opt}' not a valid selection.\n \
Valid selections\n \
- All: outputs every # in the Trie\n \
- #: (e.g. 1, 123, 43...) checks if the # exists in the Trie"
end
else if(opt.is_a?(Fixnum))
each do |x|
if(x[3].to_i==opt)
if(x[2])
puts x[3].to_s + ' exists.'
return true
end
end
end
puts "#{opt} not found."
end
end
end
#--------------------------------------------------------------------------------------
def child_value?(value, node)
if(node.children.empty?)
return 'empty' # Return: 'empty', children
,
'D.N.E.'
else
i=0; while(i<node.children.size)
if(node.children.value==value)
return node.children # Something wrong here ????
else if(i==node.children.size-1)
return 'D.N.E.'
end
end
i+=1
end
end
end
def add_digits(digitArray)
node = self
while(digitArray[0])
scan = child_value?(digitArray[0], node) # Scan the trie for
the digit
# Empty case
if(scan=='empty')
node = node<<(digitArray[0])
if(digitArray.size==1)
node.number_exists = true
end
digitArray.delete_at(0)
# D.N.E. case
else if(scan=='D.N.E.')
node = node<<(digitArray[0])
if(digitArray.size==1)
node.number_exists = true
end
digitArray.delete_at(0)
# Value exists case
else if(scan.is_a?(Trie))
if(digitArray.size==1)
scan.number_exists = true # ?? FOR OUTPUT.. check this
area
end
node = scan
digitArray.delete_at(0)
if(digitArray.size==0)
return true
end
else
puts "**Scan error**"
digitArray.delete_at(0)
end
end
end
end
#end function
end
#--------------------------------------------------------------------------------------
def add_number(number)
if(number.is_a?(Fixnum))
digitArray = []
number.to_s.each_byte { |byte| digitArray.push(byte.chr.to_i) }
add_digits(digitArray)
else
puts "\'#{number}\' not a valid *Fixnum*"
end
end
# End of class Trie
end
t = Trie.new(nil)
open('output.txt', 'w') do |f|
i=0; while i<100000
#-----6 digit number-----
min = 100000
max = 999999
f << min + rand(max-min+1) << "\n"
i+=1
end
f.flush
end
RubyProf.start
File.open('output.txt', 'r').each do |x|
t.add_number(x.chomp.to_i)
end
result = RubyProf.stop
printer = RubyProf::FlatPrinter.new(result)
printer.print(STDOUT, 0)
*Trie data structure for random-generated 6-digit numbers
I think I've finally managed to put together a newbie Trie data
structure. I'm kind of lost, though, when it comes to testing it. It's
suppose to be a very effective data structure, but when I test it out,
it doesn't seem very good. Compared to a hash and an array, it's much
slower at adding new numbers and only sometimes is it faster at
retrieving a specific number.
If anybody can go through my newbie code and point out areas that are
ineffective or inefficient, that'd be terrific. I'm positive that my
implementation is very poor, and I need some feedback from more
experienced people about how to fix it.
Thanks a lot!
Justin