Объяснение кода Ruby для построения структур данных Trie - PullRequest
Новая
       7

Объяснение кода Ruby для построения структур данных Trie

6 голосов
/ 28 января 2012

Итак, у меня есть этот код ruby, который я взял из Википедии и немного изменил: 

@trie = Hash.new()
def build(str)
    node = @trie
    str.each_char { |ch|
      cur = ch
      prev_node = node
      node = node[cur]
      if node == nil
        prev_node[cur] = Hash.new()
        node = prev_node[cur]
      end
    }
  end

build('dogs')

puts @trie.inspect

Сначала я запускал это на консоли irb, и каждый раз, когда я выводил node, он просто давал мне пустой хэш каждый раз {}, но когда я фактически вызывал эту функцию, строил с параметром 'dogs' string, он на самом деле работает, и выводит {"d"=>{"o"=>{"g"=>{"s"=>{}}}}}, что совершенно правильно.

Вероятно, это скорее вопрос Ruby, чем реальный вопрос о том, как работает алгоритм. Я не имею достаточного знания Ruby, чтобы понять, что там происходит, я думаю.

Ответы [ 2 ]

22 голосов
/ 28 января 2012

Вы, вероятно, теряетесь в этом беспорядке кода, который использует подход, который кажется более подходящим для C ++, чем для Ruby.Вот то же самое в более кратком формате, который использует специальный хэш для хранения: 

class Trie < Hash
  def initialize
    # Ensure that this is not a special Hash by disallowing
    # initialization options.
    super
  end

  def build(string)
    string.chars.inject(self) do |h, char|
      h[char] ||= { }
    end
  end
end

Он работает точно так же, но почти не имеет такой же путаницы с указателями и тому подобным:

*Модуль 1005 *

* Ruby * Enumerable полон удивительно полезных методов, таких как inject, и это именно то, что вам нужно для такой ситуации.

0 голосов
/ 28 января 2012

Я думаю, что вы просто используете irb неправильно.Вы должны ввести всю функцию, затем запустить ее и посмотреть, получите ли вы правильные результаты.Если это не работает, как насчет того, чтобы опубликовать весь сеанс IRB здесь.

Также здесь представлена ​​упрощенная версия вашего кода: 

def build(str)
  node = @trie
  str.each_char do |ch|
    node = (node[ch] ||= {})
  end
  # not sure what the return value should be
end
...