Почему этот код 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 около 2х так быстро, как Haskell один. Возможно, мне следовало бы сказать, что код Haskell был «невероятно медленным» в сравнении, но поскольку Haskell статически типизирован, я думаю, я просто подумал, что он должен быть намного быстрее и не медленнее, чем Python вообще.

Answer 1

Я вроде новичок в Haskell и попытался сделать Эрудит решатель.

Вы можете существенно улучшить ситуацию, используя лучший алгоритм.

Вместо проверки каждой перестановки входных букв, если вы сортировать их сначала можно сделать только один словарь поиск и получить все возможные слова (анаграммы), которые могут быть образованы из их (используя все из них).

Вот код, который создает этот словарь как 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 МБ) составляет около 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 минуты. Таким образом, 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]