72

私は stackoverflow Non-Trivial Lazy Evaluationを見回していたので、Keegan McAllister のプレゼンテーション: Why learn Haskellにたどり着きました。スライド 8 で、彼は次のように定義された最小限の機能を示しています。

minimum = head . sort

その複雑さは O(n) であると述べています。置換による並べ替えが O(nlog n) の場合、複雑さが線形であると言われる理由がわかりません。投稿で言及されている並べ替えは、並べ替えのカウントなどの線形並べ替え方法で必要になるため、データについて何も想定していないため、線形にすることはできません。

ここで遅延評価が不思議な役割を果たしているのでしょうか? もしそうなら、その背後にある説明は何ですか？

4

7 に答える 7

60

ではminimum = head . sort、事前sortに行われないため、完全には行われません。は、 によって要求された最初の要素を生成するために必要なだけ実行されます。sorthead

たとえば、マージソートでは、最初nにリストの番号がペアごとに比較され、次に勝者がペアになって比較され (n/2番号)、次に新しい勝者が ( n/4) というようにO(n)比較されます。

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

上記のコードを拡張して、生成された各数値に、その生成に使用された多数の比較でタグを付けることができます。

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

いくつかのリストの長さで実行すると、実際に であることが~ nわかります。

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

ソートコード自体が~ n log nであるかどうかを確認するために、生成された各数値がそれ自体のコストだけを運ぶように変更し、ソートされたリスト全体の合計によって合計コストが求められるようにします。

    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

これは、さまざまな長さのリストの結果です。

*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]

上記は、リストの長さが増加するための経験的な成長の順序をn示しています。通常、~ n log n計算によって示されるように、リストは急速に減少します。このブログ投稿も参照してください。簡単な相関チェックは次のとおりです。

*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]

編集:遅延評価は、比喩的には一種の生産者/消費者のイディオム1と見なすことができ、仲介者として独立したメモ化ストレージを使用します。私たちが書いた生産的な定義は、消費者の要求に応じて少しずつ出力を生成するプロデューサーを定義しますが、すぐには生成されません。生成されたものはすべてメモ化されるため、別の消費者が同じ出力を異なるペースで消費した場合、以前に満たされた同じストレージにアクセスします。

ストレージの一部を参照するコンシューマがなくなると、ガベージ コレクションが行われます。最適化により、コンパイラーは中間ストレージを完全に排除し、仲介者を排除できる場合があります。

1参照: Simple Generators v. Lazy Evaluation (Oleg Kiselyov、Simon Peyton-Jones、Amr Sabry 著)。

于 2012-08-21T15:08:50.090 に答える
14

の詳細に取り組む多くの回答を得ていますhead . sort。さらに一般的なステートメントをいくつか追加します。

熱心な評価により、さまざまなアルゴリズムの計算の複雑さが単純な方法で構成されます。たとえば、の最小上限（LUB）は、とのLUBf . gの合計である必要がfありgます。fしたがって、LUBの観点からのみ、ブラックボックスおよびg推論として扱うことができます。

ただし、遅延評価では、とf . gのLUBの合計よりも優れたLUBを持つことができます。LUBを証明するためにブラックボックス推論を使用することはできません。実装とその相互作用を分析する必要があります。fg

したがって、遅延評価の複雑さは、熱心な評価よりも推論するのがはるかに難しいというよく言われる事実。次のことを考えてみてください。フォームが。であるコードの漸近的パフォーマンスを改善しようとしていると仮定しますf . g。熱心な言語では、これを行うために従うことができる明白な戦略があります：とのより複雑なものを選び、f最初gにそれを改善します。それで成功すれば、あなたはその仕事で成功しf . gます。

一方、怠惰な言語では、次のような状況が発生する可能性があります。

  • fとのより複雑なものを改善しますが、g改善f . gしません（またはさらに悪化します）。
  • f . g役に立たない（または悪化する）方法で改善することができます。fg
于 2012-08-21T19:15:01.473 に答える
8

それほど神秘的ではありません。最初の要素を提供するために、どのくらいのリストをソートする必要がありますか? 線形時間で簡単に実行できる最小要素を見つける必要があります。たまたま、sort遅延評価の一部の実装ではこれが行われます。

于 2012-08-21T15:08:25.217 に答える
7

これを実際に見る興味深い方法の 1 つは、比較関数をトレースすることです。

import Debug.Trace
import Data.List

myCmp x y = trace (" myCmp " ++ show x ++ " " ++ show y) $ compare x y

xs = [5,8,1,3,0,54,2,5,2,98,7]

main = do
    print "Sorting entire list"
    print $ sortBy myCmp xs

    print "Head of sorted list"
    print $ head $ sortBy myCmp xs

まず、リスト全体の出力がトレース メッセージとインターリーブされる方法に注意してください。2 番目に、頭部を計算するだけの場合のトレース メッセージがどのように類似しているかに注意してください。

これを Ghci で実行したところ、正確には O(n) ではありません。最初の要素を見つけるには、必要な 10 回ではなく、15 回の比較が必要です。しかし、それでも O(n log n) 未満です。

編集: Vitus が以下で指摘しているように、10 回ではなく 15 回の比較を行うことは、O(n) ではないということと同じではありません。理論上の最小値よりも多くかかることを意味しました。

于 2012-08-21T16:43:06.877 に答える
6

Paul Johnson の回答に触発されて、2 つの関数の成長率をプロットしました。最初に、比較ごとに 1 文字を出力するように彼のコードを変更しました。

import System.Random
import Debug.Trace
import Data.List
import System.Environment

rs n = do
    gen <- newStdGen
    let ns = randoms gen :: [Int]
    return $ take n ns

cmp1 x y = trace "*" $ compare x y
cmp2 x y = trace "#" $ compare x y

main = do
    n <- fmap (read . (!!0)) getArgs
    xs <- rs n
    print "Sorting entire list"
    print $ sortBy cmp1 xs

    print "Head of sorted list"
    print $ head $ sortBy cmp2 xs

*および文字をカウントすると#、等間隔のポイントで比較カウントをサンプリングできます (私の python を許してください):

import matplotlib.pyplot as plt
import numpy as np
import envoy

res = []
x = range(10,500000,10000)
for i in x:
    r = envoy.run('./sortCount %i' % i)
    res.append((r.std_err.count('*'), r.std_err.count('#')))

plt.plot(x, map(lambda x:x[0], res), label="sort")
plt.plot(x, map(lambda x:x[1], res), label="minimum")
plt.plot(x, x*np.log2(x), label="n*log(n)")
plt.plot(x, x, label="n")
plt.legend()
plt.show()

スクリプトを実行すると、次のグラフが表示されます。

成長率

下の線の傾きは..

>>> import numpy as np
>>> np.polyfit(x, map(lambda x:x[1], res), deg=1)
array([  1.41324057, -17.7512292 ])

..1.41324057 (線形関数であると仮定)

于 2012-08-24T06:05:48.460 に答える