1

最近、Ruby をいじっていて、 http: //codekata.pragprog.com から Anagrams Code Kata を完成させました。

このソリューションはテスト駆動で、独自の素因数分解定理を利用していますが、実行速度が非常に遅いようです。45k ファイルだけで、これまでに約 10 分間実行されています。コードのパフォーマンスを改善するためのヒントを教えてもらえますか?

class AnagramFinder
def initialize
    @words = self.LoadWordsFromFile("dict45k.txt")
end

def OutputAnagrams
    hash = self.CalculatePrimeValueHash

    @words.each_index{|i|
        word = @words[i]
        wordvalue = hash[i]
        matches = hash.select{|key,value| value == wordvalue}
        if(matches.length > 1)
            puts("--------------")
            matches.each{|key,value|
                puts(@words[key])
            }
        end         
    }

end

def CalculatePrimeValueHash     
    hash = Hash.new
    @words.each_index{|i|
        word = @words[i]
        value = self.CalculatePrimeWordValue(word)
        hash[i] = value
    }

    hash
end

def CalculatePrimeWordValue(word)
    total = 1
    hash = self.GetPrimeAlphabetHash
    word.downcase.each_char {|c|
        value = hash[c]
        total = total * value
    }
    total
end

def LoadWordsFromFile(filename)

    contentsArray = []
    f = File.open(filename)

    f.each_line {|line|
        line = line.gsub(/[^a-z]/i, '')
        contentsArray.push line
    }

    contentsArray
end

def GetPrimeAlphabetHash
    hash = { "a" => 2, "b" => 3, "c" => 5, "d" => 7, "e" => 11, "f" => 13, "g" =>17, "h" =>19, "i" => 23, "j" => 29, "k" => 31, "l" => 37, "m" => 41, "n" =>43, "o" =>47, "p" => 53, "q" =>59, "r" => 61, "s" => 67, "t" => 71, "u" => 73, "v" => 79, "w" => 83, "x" => 89, "y" => 97, "z" => 101 }
end 
end
4

3 に答える 3

5

Frederick Cheung にはいくつかの良い点がありますが、いくつかの説明的な例を提供できると思いました。

あなたの主な問題は、インデックスを作成して、その中で線形検索を強制することだと思います。

単語リスト ( @words) は次のようになります。

[
  "ink",
  "foo",
  "kin"
]

つまり、単なる単語の配列です。

次に、 でハッシュ インデックスを作成します。CalculatePrimeValueHashハッシュ キーは の単語のインデックスと同じ@wordsです。

{
  0 => 30659, # 23 * 43 * 31, matching "ink"
  1 => 28717, # 13 * 47 * 47, matching "foo"
  2 => 30659  # 31 * 23 * 43, matching "kin"
}

これは良いスタートだと思いますが、このままにしておくと、ハッシュを繰り返し処理して、@words一緒に属するハッシュ キー (つまり、 のインデックス) を見つけ、それらを繰り返し処理してそれらを結合する必要があります。つまり、ここでの基本的な問題は、細分化しすぎていることです。

代わりに、プライム値をハッシュ キーとしてこのハッシュを作成し、そのキーを持つ単語の配列を指すようにすると、代わりに次のようなハッシュ インデックスが得られます。

{
  30659 => ["ink", "kin"],
  28717 => ["foo"]
}

この種の構造では、出力を書き込むために必要な唯一のことは、ハッシュ値を反復処理して出力することだけです。ハッシュ値は既にグループ化されているためです。

あなたのコードのもう 1 つの点は、大量の使い捨てオブジェクトを生成しているように見えることです。これにより、ガーバージ コレクターがビジー状態に保たれます。これは一般に、Ruby の非常に大きなチョーク ポイントです。

ベンチマーク ツールやプロファイラーを見つけてコードを分析し、どこで承認されるかを確認するのも良いことです。

于 2012-09-19T09:52:39.567 に答える
4

基本的に、あなたのコードは遅くなります。なぜなら、それらの単語 (45k) ごとにハッシュ全体 (45k) を反復して同じ署名を持つ単語を探しているため、これらの比較を 45k * 45k 実行しているためです。別の言い方をすれば、あなたの複雑さは単語数で n^2 であるということです。

以下のコードはあなたの基本的なアイデアを実装していますが、たまたま横たわっている 236k ワードのファイルで数秒で実行されます。それは間違いなく高速になる可能性があります-1つ以上のアイテムを持つものを見つけるためのデータの2回目のパスは排除できますが、読みにくくなります

また、主に私がより多くの標準ライブラリ関数と慣用的なルビーを使用したため、可読性を維持しながら、コードよりもはるかに短く、約 3 分の 1 です。

たとえば、load_words メソッドは、collectある配列を繰り返し処理して別の配列に追加するのではなく、ある配列を別の配列に変換するために使用します。同様に、署名関数はinject、文字を反復するのではなく使用します。最後にgroup_by、実際のグループ化を行っていました。これらのメソッドはすべて、たまたま Enumerable に含まれています。これらに精通する価値は十分にあります。

signature_for_wordでさらに厄介になる可能性があります

word.each_char.map {|c| CHAR_MAP[c.downcase]}.reduce(:*)

これは単語を受け取り、それを文字に分割し、それらのそれぞれを正しい数字にマップします。reduce(:*)(reduce は inject のエイリアスです) 次に、それらをすべて乗算します。

class AnagramFinder
  CHAR_MAP ={ "a" => 2, "b" => 3, "c" => 5, "d" => 7, "e" => 11, "f" => 13, "g" =>17, "h" =>19, "i" => 23, "j" => 29, "k" => 31, "l" => 37, "m" => 41, "n" =>43, "o" =>47, "p" => 53, "q" =>59, "r" => 61, "s" => 67, "t" => 71, "u" => 73, "v" => 79, "w" => 83, "x" => 89, "y" => 97, "z" => 101 }

  def initialize
    @words = load_words("/usr/share/dict/words")
  end

  def find_anagrams
    words_by_signature = @words.group_by {|word| signature_for_word word}
    words_by_signature.each do |signaure, words|
      if words.length > 1
        puts '----'
        puts words.join('; ')
      end
    end
  end

  def signature_for_word(word)
    word.downcase.each_char.inject(1) {| total, c| total * CHAR_MAP[c]}
  end

  def load_words(filename)
    File.readlines(filename).collect {|line| line.gsub(/[^a-z]/i, '')}
  end
end
于 2012-09-19T09:40:00.650 に答える
2

Benchmark ツールを使用して、速度の制限を開始できます。ここにいくつかの例があります:

http://www.skorks.com/2010/03/timing-ruby-code-it-is-easy-with-benchmark/

まず第一に、実行にかかる時間self.calculate_prime_value_hashとその後のcalculate_prime_word_value.

多くの場合、遅さは内部ループが実行される回数に帰着するため、それらが実行された回数を記録することもできます。

あなたができる非常に簡単な改善の 1 つは、素数の alhabet ハッシュを定数として設定することです。これは、まったく変更されていないためです。

PRIME_ALPHABET_HASH = { "a" => 2, "b" => 3, "c" => 5, "d" => 7, "e" => 11, "f" => 13, "g" =>17, "h" =>19, "i" => 23, "j" => 29, "k" => 31, "l" => 37, "m" => 41, "n" =>43, "o" =>47, "p" => 53, "q" =>59, "r" => 61, "s" => 67, "t" => 71, "u" => 73, "v" => 79, "w" => 83, "x" => 89, "y" => 97, "z" => 101 }
于 2012-09-19T09:04:49.690 に答える