为什么这个Haskell代码这么慢？

Question

我是Haskell的新手,并尝试制作拼字游戏解算器.它接收您当前拥有的字母,查找它们的所有排列并过滤掉那些字典单词.代码非常简单:

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的2倍.也许我不应该说Haskell代码相比之下"非常慢",但是由于Haskell是静态类型的,我想我只是认为它应该快得多,而且根本不比Python慢​​.

Answer 1

我是Haskell的新手,并尝试制作拼字游戏解算器.

通过使用更好的算法,您可以大大改善事物.

而不是测试输入字母的每个排列,如果你首先对它们进行排序,你只能进行一次字典查找,并获得可能由它们形成的所有可能的单词(字谜)(使用它们全部).

这是将该字典创建为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而不是字符串可能会提高性能.

尝试一些好的字母组合:

steer rat tuna lapse groan neat

注意:使用GHC 7.10.2我发现这个代码表现最好而不用 -O2编译.

Answer 2

检查是否x是一个元素dictWords可能非常慢.我假设您的类似python实现存储dictWords在一个集合或排序的向量中(在后一种情况下使用二进制搜索)？好像你可能想在这里做同样的事情.

使用这个单词列表和下面的代码,Python版本在大约30秒内运行,Haskell版本需要1.5分钟.因此Haskell速度较慢(可能是因为它使用链接列表,所有条件相同,迭代速度较慢),但与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]