From: Justin To <tekmc@...>
Date: 2008-06-14T04:32:56+09:00
Subject: Re: Trie data structure

require 'ruby-prof'

class Trie
  attr_reader :value, :children
  attr_accessor :number_exists, :prefix
  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[i], 
'D.N.E.'
    else
      i=0; while(i<node.children.size)
        if(node.children[i].value==value)
          return node.children[i]       # 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






-- 
Posted via http://www.ruby-forum.com/.