ruby - Anagrams Code Kata，Ruby 解决方案非常慢

Question

我最近一直在玩 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

Answer 1

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​​ 中的一个很大的瓶颈。

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