Dlaczego ten kod Haskella jest tak wolny?

Question

Jestem trochę nowy w Haskell i próbowałem zrobić solver scrabble. Przyjmuje listy, które obecnie masz, znajduje wszystkie ich permutacje i odfiltrowuje te, które są słowami słownikowymi. Kod jest całkiem prosty:

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] 

Jest jednak niesamowicie powolny w porównaniu do bardzo podobnej implementacji, jaką mam w Pythonie. Czy coś fundamentalnego robię źle?

* edit: Oto mój kod 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 

nie miałem czasu na ich dokładnie, ale z grubsza to czuje się jak implementacja Pythona jest około 2x szybciej niż jednego Haskell. Być może nie powinienem był mówić, że kod Haskella był "niesamowicie wolny" w porównaniu, ale ponieważ Haskell jest statycznie napisany, wydaje mi się, że po prostu pomyślałem, że powinien być znacznie szybszy, a nie wolniejszy niż Python.

Answer 1

Jestem trochę nowych do Haskell i próbował dokonywania scrabble Solver.

Możesz znacznie poprawić rzeczy, używając lepszego algorytmu.

Zamiast testuje każdą permutację liter wejściowych, jeśli sortować je najpierw można dokonać tylko jednego słownika wyszukiwanie i uzyskać wszystkich możliwych słów (anagramy), które mogą być utworzone z nich (przy wszystkich z nich).

Oto kod, który tworzy ten słownik jako Data.Map. Istnieje koszt początkowy tworzenia mapy, ale po pierwszym zapytaniu kolejne zapytania są bardzo szybkie.

Czas utworzenia mapy dla pliku słownego 236K słów (2,5 MB) wynosi około 4-5 sekund. Lepsza wydajność jest prawdopodobnie możliwa dzięki użyciu ByteStrings lub tekstu zamiast ciągów.

Kilka dobrych kombinacje liter spróbować:

steer rat tuna lapse groan neat 

Uwaga: Używanie GHC 7.10.2 znalazłem ten kod wykonywany najlepszą bez kompilacji z -O2.

Answer 2

Sprawdzenie, czy x jest elementem o numerze dictWords, prawdopodobnie będzie bardzo powolne. Zakładam, że twoja podobna implementacja pythona przechowuje dictWords w zestawie lub posortowanym wektorze (używając wyszukiwania binarnego w tym drugim przypadku)? Wygląda na to, że prawdopodobnie chcesz zrobić to samo tutaj.

Używając this word list i poniższego kodu, wersja Pythona działa w około 30 sekund, a wersja Haskella trwa 1,5 minuty. Tak więc Haskell jest wolniejszy (być może dlatego, że używa listy połączonej, której wszystkie elementy są równe, wolniej jest iterować), ale nie nazwałbym tego "niesamowicie powolnym" w porównaniu do Pythona. Przełączenie na używanie zestawu w obu wersjach skraca czas do poniżej 1 sekundy.

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] 

A oto zestaw opartych kod 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]