なぜこのHaskellコードが遅いのですか？

Question

私はハスケルには新しく、スクラブルソルバーを作ろうとしました。あなたが現在持っている手紙を取り込み、それらのすべての順列を見つけ、辞書の単語であるものを取り除きます。コードのかなりシンプル：それは私は、Pythonで持っている非常によく似た実装に比べ、非常に遅いですが

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コードだ：

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実装を約2倍の速Haskellの一つとしてあるように大体それは感じています。おそらく、私はHaskellのコードが「信じられないほど遅い」と言っていたはずが、Haskellが静的に型付けされているので、Pythonよりもはるかに速く、遅くなくてはならないと思った。

Answer 1

私はHaskellのに新しいの一種だと引っかくソルバを作ってみました。

より良いアルゴリズムを使用すると、事実上改善できます。あなたが最初にそれらを並べ替える 場合

代わりの入力文字のすべての順列をテストし、あなただけの1辞書検索を行い、 その（それらのすべてを使用することから形成することができる可能な単語（アナグラム）の全てを取得することができます）。

ここで、その辞書をData.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）のワードファイルのマップ作成時間は約4-5秒です。文字列の代わりにByteStringsまたはTextを使用すると、パフォーマンスが向上する可能性があります。しようとする

いくつかの良い文字の組み合わせ：

steer rat tuna lapse groan neat 

注：GHCの7.10.2を使用して、私は、このコードは、-O2でコンパイルせずに最高のを行いました。

Answer 2

xがdictWordsの要素であるかどうかを確認することは、非常に遅くなる可能性があります。私はあなたの同様のPythonの実装は、セットまたはソートベクトル（後者の場合はバイナリ検索を使用して）にdictWordsを格納すると仮定しますか？あなたはおそらく同じことをここでやりたいと思うようです。

this word listと以下のコードを使用すると、Pythonのバージョンは約30秒で実行され、Haskellのバージョンは1.5分かかります。だから、ハスケルは遅いです（おそらく、リンクリストを使用しているため、すべてが等しくなり、繰り返し処理が遅くなります）。しかし、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]