21

熱心な評価とは対照的に、遅延評価にはどのような利点がありますか？

どのようなパフォーマンスのオーバーヘッドがありますか？遅延評価は遅くなりますか、それとも速くなりますか？なぜ（または実装に依存するのですか？）？

遅延評価は、ほとんどの実装で実際にどのように機能しますか？私には、変数は数値だけでなく操作も格納する必要があるため、はるかに遅く、メモリを大量に消費するように思われます。それで、それはHaskellのような言語でどのように機能しますか（注、私は実際にはその言語を知りません）？怠惰が大幅に遅くなったり、より多くのスペースを消費したりしないように、怠惰はどのように実装および実行されますか？

4

4 に答える 4

14

遅延評価は、効率的な償却範囲を持つデータ構造の作成に非常に役立ちます。

例を挙げると、不変のスタッククラスがあります。

class Stack<T>
{
    public static readonly Stack<T> Empty = new Stack<T>();
    public T Head { get; private set; }
    public Stack<T> Tail { get; private set; }
    public bool IsEmpty { get; private set; }

    private Stack(T head, Stack<T> tail)
    {
        this.Head = head;
        this.Tail = tail;
        this.IsEmpty = false;
    }

    private Stack()
    {
        this.Head = default(T);
        this.Tail = null;
        this.IsEmpty = true;
    }

    public Stack<T> AddFront(T value)
    {
        return new Stack<T>(value, this);
    }

    public Stack<T> AddRear(T value)
    {
        return this.IsEmpty
            ? new Stack<T>(value, this)
            : new Stack<T>(this.Head, this.Tail.AddRear(value));
    }
}

スタックの前にアイテムを追加することはできますが、後ろにアイテムを追加するO(1)にはO(n)時間がかかります。データ構造全体を再構築する必要がAddRearあるため、これはモノリシック操作です。

これは同じ不変のスタックですが、遅延評価されています。

class LazyStack<T>
{
    public static readonly LazyStack<T> Empty = new LazyStack<T>();

    readonly Lazy<LazyStack<T>> innerTail;
    public T Head { get; private set; }
    public LazyStack<T> Tail { get { return innerTail.Value; } }
    public bool IsEmpty { get; private set; }

    private LazyStack(T head, Lazy<LazyStack<T>> tail)
    {
        this.Head = head;
        this.innerTail = tail;
        this.IsEmpty = false;
    }

    private LazyStack()
    {
        this.Head = default(T);
        this.innerTail = null;
        this.IsEmpty = true;
    }

    public LazyStack<T> AddFront(T value)
    {
        return new LazyStack<T>(value, new Lazy<LazyStack<T>>(() => this, true));
    }

    public LazyStack<T> AddRear(T value)
    {
        return this.IsEmpty
            ? new LazyStack<T>(value, new Lazy<LazyStack<T>>(() => this, true))
            : new LazyStack<T>(this.Head, new Lazy<LazyStack<T>>(() => this.Tail.AddRear(value), true));
    }
}

これで、AddRear関数がO(1)時間内に明確に実行されるようになりました。プロパティにアクセスすると、ヘッドノードを返すのに十分なTailレイジー値が評価されてから停止するため、モノリシック関数ではなくなります。

于 2010-01-28T01:49:22.373 に答える
11

遅延評価は、純粋に関数型プログラミング言語の一般的な特性であり、「パフォーマンスを取り戻す」ことができます。これは非常に簡単に機能し、必要なときにのみ式を評価します。たとえば、Haskellで考えてみましょう

if x == 1 then x + 3 else x + 2

厳密な（先行）評価では、xが実際に2に等しい場合、x + 3が評価されて返されます。それ以外の場合、Haskellではx + 2は発生しません。たとえば、x+3は式に合成されます。私が持っていると言う：

let x = if x == 1 then x + 3 else x + 2

それでは、それを変数に格納しますが、他の条件が原因でその変数を使用したことがない場合はどうなりますか？CPUで非常に高価な整数の加算を無駄にしました。（大丈夫、実際にはこれに勝つことはありませんが、より大きな表現でアイデアを得ることができます）

次に、質問は、なぜすべての言語が怠惰ではないのかということです。単純な理由は、純粋に関数型言語では、式に副作用がまったくないことが保証されているからです。もしそうなら、私たちはそれらを正しい順序で評価しなければならないでしょう。そのため、ほとんどの言語で熱心に評価されています。式に副作用がない言語では、遅延評価のリスクがないため、他の領域で失われがちなパフォーマンスを取り戻すのが論理的な選択です。

もう1つの興味深い副作用は、Haskellのif-then-elseが実際にはタイプの関数であるということですBool -> a -> a -> a。Haskellでは、これはブール型の引数、任意の型の引数、最初の型と同じ型の引数を取り、その型を再び返すことを意味します。値は必要なときにのみ評価されるため、さまざまな制御ブランチの無限の評価に遭遇することはありません。これは通常、プログラムの最後で、巨大な式が作成され、最終結果が評価されて破棄されます。コンパイラーが最終結果に必要でないと考えるすべてのもの。たとえば、非常に複雑な式を単独で分割すると、両方の部分を評価せずに、「1」の代わりに使用できます。

違いは、伝統的に厳密に評価されているSchemeに見られますが、Lazy Schemeと呼ばれるレイジーバリアントがあります。Schemeは関数ではない(display (apply if (> x y) "x is larger than y" "x is not larger than y"))ためエラーでifあり、特殊な構文です（ただし、Schemeでは構文はまったく特殊ではないと言う人もいます）。 ）必ずしもすべての引数を評価するわけではないため、たとえば階乗を計算しようとすると、メモリが不足します。Lazy Schemeでは、関数が表示のように評価を続行するために結果を本当に必要とするまで、これらの引数はまったく評価されないため、問題なく機能します。

于 2010-05-19T18:24:26.610 に答える
9

これは、構文木の評価を指します。構文木を怠惰に評価する場合（つまり、構文木が表す値が必要な場合）、計算の前のステップ全体を実行する必要があります。これは、遅延評価のオーバーヘッドです。ただし、2つの利点があります。1）結果が使用されない場合、ツリーを不必要に評価することはありません。2）評価するのではなく、必要な深さまでしか評価しないため、再帰形式で無限構文ツリーを表現して使用できます。 （熱心に）全体として、それは不可能でしょう。

私はハスケルを知りませんが、私が知る限り、PythonやMLのようなプログラミング言語は熱心に評価されます。たとえば、MLで遅延評価をシミュレートするには、パラメーターを受け取らないが結果を返すダミー関数を作成する必要があります。この関数は、空の引数リストを使用して呼び出すことにより、いつでも遅延評価できる構文ツリーです。

于 2010-01-27T23:50:52.537 に答える
1

rubyでは、通常「once」と呼ばれる関数修飾子を使用して、遅延評価を行うようにメソッドをラップします。このようなメソッドは一度だけ評価され、値がキャッシュされ、後続の呼び出しでその値が返されます。

遅延評価の1つの使用（または誤用）は、オブジェクトの初期化の順序を明示的ではなく暗黙的にすることです。前：

def initialize
  setup_logging  # Must come before setup_database
  setup_database  # Must come before get_addresses
  setup_address_correction  # Must come before get_addresses
  get_addresses
end

def setup_logging
  @log = Log.new
end

def setup_database
  @db = Db.new(@log)
end

def setup_address_correction
  @address_correction = AddressCorrection.new
end

def get_addresses
  @log.puts ("Querying addresses")
  @addresses = @address_correction.correct(query_addresses(@db))
end

遅延評価あり：

def initialize
  get_addresses
end

def log
  Log.new
end
once :log

def db
  Db.new(log)
end
once :db

def address_corrector
  AddressCorrection.new
end
once :address_corrector

def get_addresses
  log.puts ("Querying addresses")
  @addresses = address_corrector.correct(query_addresses(db))
end

さまざまな相互依存オブジェクトの初期化の順序は、（1）暗黙的、および（2）自動になりました。欠点として、このトリックに過度に依存していると、制御の流れが不透明になる可能性があります。

于 2010-01-28T00:38:13.597 に答える