5

Haskell には、次のようなコンテナがあります。

data Container a = Container { length :: Int, buffer :: Unboxed.Vector (Int,a) }

このコンテナは平坦化されたツリーです。そのアクセサは、が格納されている適切なバケットを見つけるために、ベクトルを介して(!)バイナリ ( ) 検索を実行します。log(N)index

(!) :: Container a -> Int -> a
container ! index = ... binary search ...

連続したアクセスは同じバケットにある可能性が高いため、これは次の方法で最適化できます。

if `index` is on the the last accessed bucket, skip the search

難点はそのlast accessed bucket部分です。JavaScript では、コンテナ オブジェクトの隠し変数を不純に変更するだけです。

function read(index,object){

    var lastBucket = object.__lastBucket;

    // if the last bucket contains index, no need to search
    if (contains(object, lastBucket, index))
        var bucket = lastBucket;

    // if it doesn't
    else {
        // then we search the bucket
        var bucket = searchBucket(index,object);

        // And impurely annotate it on the container, so the
        // next time we access it we could skip the search.
        container.__lastBucket = bucket;
    }

    return object.buffer[bucket].value;
}

これは単なる最適化であり、実行された分岐に関係なく結果は同じであるため、参照透過性が損なわれることはないと思います。Haskell で、ランタイム値に関連付けられた状態を純粋に変更できないのはどうしてですか?

〜

私は2つの可能な解決策を考えました。

  1. ポインターを値にリンクするグローバルで変更可能なハッシュマップlastBucketであり、unsafePerformIO を使用してそれに書き込みます。しかし、オブジェクトのランタイム ポインタ、または少なくとも何らかの一意の ID を取得する方法が必要です (方法は?)。

  2. 、 に追加のフィールドを追加し、Container何らかのlastBucket :: Int方法で 内(!)で純粋に変更せず、そのフィールドを内部と見なします (明らかに参照透過性を壊すため)。

4

2 に答える 2

2

(これは、回答というよりも拡張されたコメントです。)

最初に、これが時期尚早の最適化の場合ではないかどうかを確認することをお勧めします。結局のところ、O(log n)はそれほど悪くはありません。

この部分が実際にパフォーマンスにとって重要である場合、あなたの意図は間違いなく有効です。通常の警告unsafePerformIOは、「自分が何をしているのかを知っている場合にのみ使用してください」です。これは明らかにそうしており、物事を純粋かつ高速にするのに役立ちます。docs のすべての注意事項、特に適切なコンパイラ フラグの設定に従ってください (プラグマを使用するOPTIONS_GHCことをお勧めします)。

IOまた、操作がスレッドセーフであることを確認してください。それを確実にする最も簡単な方法は、 とIORef一緒に使用することですatomicModifyIORef。

内部ミュータブル状態の欠点は、複数のスレッドが異なる要素をルックアップすると、キャッシュのパフォーマンスが低下することです。

解決策の 1 つは、内部の変更可能な状態を使用する代わりに、更新された状態を明示的にスレッド化することです。これは明らかに避けたいことですが、プログラムがモナドを使用している場合は、別のモナド層を追加して内部的に状態を保持し、ルックアップ操作をモナド アクションとして公開することができます。

最後に、配列の代わりにスプレー ツリーを使用することを検討できます。それでも（償却された）O（log n）の複雑さがありますが、それらの大きな利点は、設計により、頻繁にアクセスされる要素を上部に移動することです。したがって、サイズkの要素のサブセットにアクセスする場合、それらはすぐに一番上に移動されるため、ルックアップ操作はO(log k) (単一の繰り返しアクセスされる要素に対して一定) になります。繰り返しになりますが、これらはルックアップで構造を更新しますが、同じアプローチをunsafePerformIOアトミック更新で使用IORefして、外部インターフェイスを純粋に保つことができます。

于 2015-08-27T13:38:50.330 に答える