Neden bu Haskell kodu çok yavaş?

Question

Haskell için yeni biriyim ve bir scrabble çözücü yapmayı denedim. Şu anda sahip olduğunuz harfleri alır, bunların tüm permütasyonlarını bulur ve sözlük kelimeleri olanları filtreler. kodun oldukça basit: ben Python ile sahip çok benzer bir uygulamaya göre, inanılmaz derecede yavaş Ancak

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] 

. Yanlış yaptığım bir şey var mı?

* edit: İşte benim Python kod:

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 

Ben tam bunları zaman aşımına yoktu, ama Python uygulaması kadar hızlı Haskell biri olarak yaklaşık 2x olduğu gibi kabaca hissediyor. Belki de Haskell kodunun "inanılmaz derecede yavaş" olduğunu söylememeliydim, ama Haskell statik olarak yazıldığından beri sanırım daha hızlı ve Python'dan daha yavaş olmamalıydı.

Answer 1

Ben Haskell için yeniyim ve bir scrabble çözücü yapma çalıştı:

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] 

Ve burada set tabanlı Haskell kod.

Daha iyi bir algoritma kullanarak işleri büyük ölçüde düzeltebilirsiniz.

Bunun yerine sıralama onları ilk yalnızca bir sözlük arama yapmak ve hepsi kullanılarak onları (oluşabilir olası kelimelerin (anagrams) tüm alabilirsiniz eğer, giriş harflerin her permütasyon test).

Bu sözlük, Data.Map olarak sözlüğü oluşturan koddur. Haritanın oluşturulmasında bir başlangıç ​​maliyeti vardır, ancak 'dan sonra ilk sorgudaki sonraki aramalar çok hızlıdır.

236K kelimelik bir sözcük dosyasının (2.5 MB) harita oluşturma süresi yaklaşık 4-5 saniyedir. Daha iyi performans, Dizeler yerine ByteStrings veya Text kullanılarak mümkündür.

Bazı iyi harf kombinasyonları denemek için:

steer rat tuna lapse groan neat 

Not: Kullanımı GHC 7.10.2 Bu kod -o2 ile derleme olmadan iyi gerçekleştirildi bulundu.

Answer 2

xdictWords öğesinin bir öğesinin çok yavaş olup olmadığını kontrol etme olasılığı çok düşüktür. Benzer python uygulamanızın dictWords bir set veya sıralanmış vektörde (ikinci durumda ikili arama kullanarak) depolandığını varsayabilir miyim? Muhtemelen aynı şeyi burada yapmak istiyor gibisiniz.

this word list ve aşağıdaki kodu kullanarak, Python sürümü yaklaşık 30 saniye içinde çalışır ve Haskell sürümü 1,5 dakika sürer. Yani Haskell daha yavaştır (belki de her şeyin eşit olduğu, bağlantılı bir liste kullandığı için daha yavaştır), fakat buna Python'a kıyasla "inanılmaz derecede yavaş" demezdim. Her iki versiyondaki bir seti kullanmaya geçmek, zamanı 1 saniyenin altına düşürür.

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]