11

このような構造は、リアルタイムアプリケーション（ユーザーインターフェイスなど）に必要です。（ユーザーは、ボタンのクリックに0.1秒または0.2秒かかるかどうかは気にしませんが、100回目のクリックで卓越した遅延計算が強制され、続行するのに10秒かかるかどうかは気になります。）

私は岡崎の論文「純粋関数型データ構造」を読んでいました。彼は、償却された境界を持つ怠惰なデータ構造を、すべての操作で同じ最悪の場合の境界を持つ構造に変換するための興味深い一般的な方法について説明しています。アイデアは、各更新で未評価のサンクの一部が強制されるように計算を分散することです。

Haskellに標準コレクション（、、など）のそのような実装はありますMapか？Set

コンテナパッケージには

各操作の宣言されたコストは、最悪の場合または償却されますが、構造が共有されている場合でも有効です。

したがって、単一の操作の最悪の場合の範囲は保証されません。のような厳密なバリアントがありますがData.Map.Strict、キーと値は厳密です。

キーと値の引数はWHNFに対して評価されます。キーと値は、マップに保存される前にWHNFに評価されます。

その構造の（可能な）厳密さについては何もありません。

4

1 に答える 1

11

その構造の（可能な）厳密さについては何もありません。

ソースを探しに行きます、例えばのためにData.Map.Map

-- See Note: Order of constructors
data Map k a  = Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
              | Tip

aMapが完全にスパインに厳密であることがわかります（そして、キーが厳密であってもData.Map.Lazy）。WHNFに評価すると、完全なスパインが強制されます。IntMap同じことがs、Sets 、sにも当てはまりますIntSet。

したがって、すべての操作の前にコンテナをWHNFに強制することで、大きなサンク（マップされた値/含まれた値を除く）の構築を簡単に防ぐことができます。含まれている値の大きなサンクの防止[時間（およびスペース）リークの一般的な原因]は、Data.XYZ.Strictバリアントに対して自動的に行われます（注意：値はWHNFに対してのみ評価されます。さらに必要な場合は、たとえば、自分で行う必要があります。deepseq操作の直後に変更された値を使用する場合）、Data.XYZ.Lazyバリアントを使用して自分で処理する必要があります。

したがって

ユーザーは、ボタンのクリックに0.1秒かかるか0.2秒かかるかは気にしませんが、100回目のクリックで卓越した遅延計算が強制され、続行するのに10秒かかるかどうかは気になります。

これらのコンテナで簡単に回避できる問題です。

ただし、100回目のクリックの処理には、未処理の遅延計算ではなく、アルゴリズムが原因で、平均よりもはるかに長い時間がかかる可能性があります（2つのリストを使用した従来のキューの実装を検討してくださいdequeue (Q (x:xs) ys) = (x, Q xs ys)。 O（1）、およびO（1）の後ろ。enqueue y (Q xs ys) = Q xs (y:ys)ただし、前のリストが空で、後ろを最初に反転する必要がある場合、デキューはO（size）を取りますが、それでもO（1）は償却されます）償却原価を変更せずに。

コンテナで使用されているアルゴリズムにそのようなケースがあるかどうかはわかりませんが、注意が必要です。

于 2012-09-12T17:53:18.357 に答える