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"]
}

使用这种结构，编写输出时唯一要做的就是迭代哈希值并打印它们，因为它们已经分组。

您的代码的另一件事是，它似乎生成了一大堆一次性对象，这将确保您的垃圾收集器保持忙碌，这通常是 ruby​​ 的一个很大的瓶颈。

寻找基准工具和/或分析器来分析您的代码并查看可以在哪里获得批准也可能是一件好事。

于 2012-09-19T09:52:39.567 回答
4

从根本上说，您的代码很慢，因为对于其中的每个单词（45k），您会遍历整个哈希（其中 45k）来寻找具有相同签名的单词，因此您要进行 45k * 45k 的这些比较。另一种表达方式是说您的复杂性是单词数量的 n^2。

下面的代码实现了您的基本想法，但在我碰巧躺在身边的 236k 字文件上运行了几秒钟。它肯定会更快 - 可以消除第二次通过数据查找具有> 1个项目的东西，但可读性会降低

它也比你的代码短很多，大约三分之一，同时保持可读性，主要是因为我使用了更多的标准库函数和惯用的 ruby​​。

例如， load_words 方法用于collect将一个数组转换为另一个数组，而不是遍历一个数组并将内容添加到第二个数组。类似地，签名函数使用inject而不是迭代字符。最后，我习惯于group_by进行实际的分组。所有这些方法都恰好在 Enumerable 中——非常值得熟悉这些方法。

signature_for_word可以变得更加简洁

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

这需要单词，将其拆分为字符，然后将每个字符映射到正确的数字。reduce(:*)（reduce 是注入的别名）然后将它们相乘。

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.

很多时候，缓慢归结为内部循环运行的次数，因此您还可以记录它们运行的​​次数。

您可以做的一个非常快速的改进是将主要 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 回答