Beni McAllister sunumu Keegan yol açan Non-Trivial Lazy Evaluation, stackoverflow bakıyordum: Why learn Haskell. Slayt en az işlev gösterir 8,, olarak tanımlanır:

minimum = head . sort

ve karmaşıklığı O olduğunu belirtir(n). Karmaşıklığı yerine göre sıralama(nlog n) ise doğrusal olduğu söyleniyor anlamıyorum. Sıralama sonrası sevk doğrusal sıralama yöntemleri, sıralama sayma gibi gerekli olacağı gibi veriler hakkında bir şey kabul etmez, doğrusal olamaz.

Olur tembel değerlendirme burada gizemli bir rol oynuyor? Eğer öyleyse, arkasında açıklaması nedir?

minimum = head . sort sort yapmış olmazsın çünkü tamamen bitti, olmayacakayarlıyoruz. sort yalnızca ilk öğe head tarafından talep edilen üretmek için gerektiği kadar yapılacak.

Örneğin mergesort, ilk başta n Sayı listesi karşılaştırılacak ikili, daha sonra kazananlar olacaktır eşleştirilmiş ve kıyasla (n/2 sayı), yeni kazananlar (n/4), vb. , O(n) minimal öğe üretmek için buluyoruz.

mergesortBy less [] = []
mergesortBy less xs = head $ until (null.tail) pairs [[x] | x <- xs]
  where
    pairs (x:y:t) = merge x y : pairs t
    pairs xs      = xs
    merge (x:xs) (y:ys) | less y x  = y : merge (x:xs) ys
                        | otherwise = x : merge  xs (y:ys)
    merge  xs     []                = xs
    merge  []     ys                = ys

Yukarıdaki kodu kendi üretiminde girdi karşılaştırmalar bir dizi üretir her numara etiketi ile artar olabilir:

mgsort xs = go $ map ((,) 0) xs  where
  go [] = []
  go xs = head $ until (null.tail) pairs [[x] | x <- xs]   where
    ....
    merge ((a,b):xs) ((c,d):ys) 
            | (d < b)   = (a c 1,d) : merge ((a 1,b):xs) ys    -- cumulative
            | otherwise = (a c 1,b) : merge  xs ((c 1,d):ys)   --   cost
    ....

g n = concat [[a,b] | (a,b) <- zip [1,3..n] [n,n-2..1]]   -- a little scrambler

Görüyoruz ki, birçok liste uzunlukları için çalışıyornitekim ~ n:

*Main> map (fst . head . mgsort . g) [10, 20, 40, 80, 160, 1600]
[9,19,39,79,159,1599]

Olup olmadığını görmek için sıralama kodu ~ n log n, onu değiştirelim, böylece her üretilen sayı taşır boyunca sadece kendi maliyet ve toplam maliyet daha sonra bulunan toplam üzerinden bütün sıralı listesi:

    merge ((a,b):xs) ((c,d):ys) 
            | (d < b)   = (c 1,d) : merge ((a 1,b):xs) ys      -- individual
            | otherwise = (a 1,b) : merge  xs ((c 1,d):ys)     --   cost

Burada çeşitli uzunluklarda listeleri için sonuçlar

*Main> let xs = map (sum . map fst . mgsort . g) [20, 40, 80, 160, 320, 640]
[138,342,810,1866,4218,9402]

*Main> map (logBase 2) $ zipWith (/) (tail xs) xs
[1.309328,1.2439256,1.2039552,1.1766101,1.1564085]

Yukarıdaki hızla genellikle tarafından yaşandığı gibi azalan olan liste artan uzunlukları, n empirical orders of growth gösterir~ n log nhesaplamaları. Ayrıca this blog post bkz. Burada hızlı bir korelasyon kontrol edin:

*Main> let xs = [n*log n | n<- [20, 40, 80, 160, 320, 640]] in 
                                    map (logBase 2) $ zipWith (/) (tail xs) xs
[1.3002739,1.2484156,1.211859,1.1846942,1.1637106]

düzenleme:Tembel değerlendirme mecazi üretici/tüketici deyim olarak görülebilir¹bir aracı gibi bağımsız depolama memoizing. Herhangi bir üretken tanım yazıyoruz, onun çıkış, bit bit tarafından üretecek ve tüketici(ler) tarafından talep edilen zaman - ama daha erken değil yapımcı tanımlar. Üretilen her ne ise, eğer bir tüketici farklı hızda aynı çıktı tüketir, aynı depolama, önceden doldurulmuş erişir, böylece memoized.

Artık tüketiciler depolama bir parça bakın kaldığında, çöp toplanır. Bazen en iyi duruma getirme derleyici ile uzak ara depolama ile yapmak mümkün tamamen, aracıyı ortadan.

¹Ayrıca Bkz: Oleg Kiselyov, Peyton-Jones ve Amr Sabry Simon tarafından Simple Generators v. Lazy Evaluation.