为什么这个 Haskell 代码运行如此缓慢？

Question

我对Haskell还比较新，尝试编写一个Scrabble求解器。它可以接收当前拥有的字母，找到所有排列，并过滤掉不在词典中的单词。代码非常简单：

import Data.List

main = do
    dict    <- readFile "words"
    letters <- getLine
    let dictWords = words dict
    let perms = permutations letters
    print [x | x <- perms, x `elem` dictWords]

然而，与我使用 Python 实现的非常相似的实现比较起来，速度极慢。是否有什么根本性的错误？

*编辑：这是我的 Python 代码：

from itertools import permutations

letters = raw_input("please enter your letters (without spaces): ")

d = open('words')
dictionary = [line.rstrip('\n') for line in d.readlines()]
d.close()

perms = ["".join(p) for p in permutations(letters)]

validWords = []

for p in perms:
    if p in dictionary: validWords.append(p)


for validWord in validWords:
    print validWord

我没有精确计时，但大致上感觉Python实现的速度是Haskell的两倍左右。也许我不该说Haskell的代码与Python相比是“极慢的”，但由于Haskell是静态类型语言，所以我认为它本应该比Python更快，而不是比Python还慢。

- nilcit

---

你能发布Python代码和一些性能基准测试吗？ - Sage Mitchell

“words dict”只是一个列表，而“elem”正在通过该列表执行顺序搜索。 - ErikR

我不确定为什么这个问题被严重地贬低了。对于初学者来说，这是一个合理的问题。这里没有足够的信息来给出有意义的答案，因为很多情况可能取决于你如何运行此代码。但是你可以进行一些高级改进，比如使用Text和[Set]（https://hackage.haskell.org/package/containers）。为什么这个问题与等价的Python解决方案具有不同的性能特征非常有趣，如果您发布您的Python代码，那将有助于我们解决它。 - Ian Henry

当然，答案是“因为你使用了错误的数据结构”。 - isekaijin

@ThomasM.DuBuisson，你一定是在开玩笑。使用“Text”并不能解决这里的根本问题。 - dfeuer

Answer 1

检查x是否为dictWords的元素可能会非常缓慢。我假设你的类似Python实现将dictWords存储在一个集合或已排序的向量中（在后一种情况下使用二进制搜索）？似乎你可能也想在这里这样做。

使用这个单词列表和下面的代码，Python版本运行约30秒，Haskell版本需要1.5分钟。因此，Haskell比Python更慢（也许是因为它使用链表，所有事情都相等，迭代速度较慢），但与Python相比，并不算“非常缓慢”。在任一版本中切换到使用集合可以将时间减少到不到1秒。

from itertools import permutations
f = open('twl06.txt')
words = f.read().split()

print [''.join(p) for p in permutations('apricot') if ''.join(p) in words]

以下是基于集合的Haskell代码：

import Data.Set
import Data.List

main = do
    dict    <- readFile "twl06.txt"
    let letters = "apricot"
    let dictWords = Data.Set.fromList $ words dict
    let perms = permutations letters
    print [x | x <- perms, member x dictWords]

- happydave

---

Python代码将字典存储为字符串列表，就像Haskell实现一样。在Python中，要检查成员资格，我使用了"in"函数。 - nilcit

嗯，我不知道如何明确回答你的问题，但将dictWords存储为集合仍然可能解决你的运行时间问题。 - happydave

我本以为Haskell比Python快，因为它是静态类型的，所以当它比Python慢3倍时，我称之为“非常慢”。这是我的措辞不当，我应该更清楚地说明情况。其他人建议也使用Set，它确实改善了运行时间。然而，我仍然很好奇为什么Haskell中的列表比Python中的列表慢。对于Python实现，要查找一个单词，它仍然必须遍历列表。Python的列表是否比Haskell的更优化？如何可能加速迭代这么多？ - nilcit

请注意，Python的列表（list）是内置的，这意味着它们直接在C中实现为“可调整大小的数组”。这意味着对element in sequence的单个调用将产生单个方法调用的解释开销，然后会触发list.__contains__的实现，在基础数组上执行C循环，并从C调用等式运算符。因此，最终CPython的in与编译语言相比并没有太多的开销，因为大部分工作都是在编译代码中完成的，唯一的开销就是通用比较。 - Bakuriu

Answer 2

我对Haskell还不是很熟悉，尝试制作一个Scrabble求解器。

使用更好的算法可以大大改善问题。

如果首先将输入字母排序，而不是测试每个排列，则只需进行一次字典查找即可获取可以从它们中形成的所有可能单词（anagrams）（使用全部字母）。

以下是创建该字典为Data.Map的代码。创建Map有启动成本，但是在第一次查询之后，随后的查找非常快。

import Data.List
import qualified Data.Map.Strict as Map
import Control.Monad
import System.IO

main = do
  contents <- readFile "words"
  let pairs = [ (sort w, [w]) | w <- words contents ]
      dict = foldl' (\m (k,v) -> Map.insertWith (++) k v m) Map.empty pairs
      -- dict = foldr (\(k,v) m -> Map.insertWith (++) k v m) Map.empty pairs
  forever $ do
    putStr "Enter letters: " >> hFlush stdout
    letters <- getLine
    case Map.lookup (sort letters) dict of
      Nothing -> putStrLn "No words."
      Just ws -> putStrLn $ "Words: " ++ show ws

一个包含236K个单词（2.5 MB）的Word文件创建地图所需的时间为4-5秒。使用ByteStrings或Text而不是Strings可能会获得更好的性能。

一些可以尝试的好的字母组合：

steer rat tuna lapse groan neat

注意：在使用GHC 7.10.2时，我发现这段代码在没有使用-O2编译的情况下表现最佳。

- ErikR

---

非常感谢您的回复！我实际上尝试了与您提供的解决方案非常相似的方法-对输入和字典中的单词进行排序，然后以此检查变位词。我使用了Set结构，并使用Set.member函数检查成员资格。然而，这种实现并没有真正改善我的运行时间。但是，您提供的实现在初始化后非常快速！我一定会学习Map的。再次感谢您的帮助-作为这门语言的新手，我非常感激！ - nilcit

作为后续 - 当我在代码中包含了一个永久循环（其中我对输入和字典单词进行了排序），第一个之后的查询立即完成。我猜这是因为惰性评估？也就是说，直到第一次查询时，代码才真正创建字典，当它实际需要它时，但在随后的查询中，它已经存在了吗？ - nilcit

没错。但是你必须小心使用 forever 和编译器版本以及选项 - 有时地图会在每次迭代中重新计算。当地图不被重新计算时，第二个和后续的查找是瞬间完成的。 - ErikR

虽然 Data.Map 在某些情况下可能足够快，但如果你使用字符串（以任何格式）作为键，则这是一种相当糟糕的数据结构。HashMap 可能更好，但类似于 Trie 的数据结构似乎是最好的选择。 - dfeuer