2012-07-01 42 views
7

tembel değerlendirme davranışını anlamada yardıma ihtiyacım var Nqueens probleminin iki versiyonunu yazdım ve benzer bir verimliliğe sahip olduklarını düşünüyorum ama öyle değil. Bunun, Haskell'in tembel değerlendirme davranışından kaynaklandığını düşünüyorum. Aşağıdaki örnek nasıl çalıştığını kimse oldukça çalışır nqueens2 iken boyutu 8.Haskell

bir yönetim kurulu için değerlendirmek nqueens1 8 8 veya 8 8 nqueens2 arayarak

nqueens1 n 1 = [[i] | i <- [1..n]] 
nqueens1 n k = [ i:q | i <- [1..n], q <- (nqueens1 n (k - 1)), isSafe i q k] 

isSafe i q n = isSafeHelper i (zip q [(n-1),(n-2)..1]) 
     where isSafeHelper i [] = True 
       isSafeHelper i (x:xs) = (i /= fst x) && abs(i - (fst x)) /= abs(n - (snd x)) && 
             isSafeHelper i xs 
nqueens2 n 1 = [[i] | i <- [1..n]] 
nqueens2 n k = [ i:q | i <- [1..n], q <- boards, isSafe i q k] 
      where boards = nqueens2 n (k-1) 

Bunları değerlendirebilir, lütfen açıklayabilir verimli nqueens1 performans sorunları var. Bunun, yinelemeli çağrının (nqueens n (k-1)) birden çok kez değerlendirilmekte olduğuna inanıyorum. Haskells tembel değerlendirme anlayışından bu durum böyle olmamalı.

Lütfen bu davranışı anlama konusunda bana yardımcı olun.

Şimdiden teşekkürler.

+1

"Tembel değerlendirme" geç şeyler değerlendirilmesi hakkındadır - değil değerlendirerek şey defalarca kaçınma hakkında. –

+4

@DanielWagner Aslında, tembel değerlendirme ve isim-arama arasındaki fark, tam olarak, isim-arama kullanılarak bir kez daha değerlendirilecek olan belirli ifadelerin, yalnızca tembel değerlendirme kullanılarak bir kez değerlendirildiğidir. Buradaki problemle alakalı değil. – sepp2k

+2

@ sepp2k Haklıyım, ya "tembel değerlendirme" yerine "isimsiz arama" diyerek ya da "pek çok şeyi değerlendirmekten kaçınmak" yerine "hatırlatma" diyerek daha hassas olmalıydım. –

cevap

10

Evet, özyinelemeli arama, birden çok kez değerlendirilir. Spesifik olarak i için her değer için bir kez değerlendirilir. Bunu önlemek istiyorsanız q <- bölüm i <- bölümünden önce gelir, böylece

, sen jeneratörler yeniden düzenleyebilirsiniz:

[ i:q | q <- nqueens2 n (k - 1), i <- [1..n], isSafe i q k] 

Ancak bu sonuçların sıralamasını değiştirir. bu kabul edilemez ise, bir zamanlar özyinelemeli aramanın sonucu hesaplamak için let kullanmak ve sonra bu gibi kullanabilirsiniz:

[ i:q | let rec = nqueens2 n (k - 1), i <- [1..n], q <- rec, isSafe i q k] 
+0

Yinelemeli çağrının bir kereden fazla değerlendirildiğini tahmin ettim ve bu nqueens1'deki yavaşlamanın sebebiydi, ancak nqueens2'deki tek değişiklik bu ifadeye bir isim vermektir. Bu Haskell derleyicisi tarafından kolayca yapılabilirdi. Derleyicinin bunu neden yapamayacağını bilmek istedim. Teşekkür ederiz. – prasannak

+2

Bu tür bir "optimizasyon", zaman için alan ticareti yapar. Subterm artık pek çok kez değerlendirilmese de tekrar gerekebileceği sürece hafızaya alınmalıdır. Bu nedenle, GHC son derece dikkatli ve genellikle bu tür dönüşümleri otomatik olarak yapmaz. Genel kural şudur: Bir terimin en fazla bir defa değerlendirilmesini istiyorsanız, o zaman bir isim verin. – kosmikus