3

コードの一部にベクトルを使用すると効率的なアプリケーションがあります。ただし、計算中にいくつかの要素を追跡する必要があります。Data.Vectors から O(n) 償却連結を取得できると聞いたことがあります (通常の配列成長トリックによって) が、私はそれを正しく行っていないと思います。したがって、次の設定があるとしましょう。

import Data.Vector((++),Vector)
import Prelude hiding ((++))
import Control.Monad.State.Strict

data App = S (Vector Int)

add :: Vector Int -> State App ()
add v1 = modify (\S v2 -> S (v2 ++ v1))

addこの場合、償却された O(n) 時間で実行されますか? そうでない場合、どうすればそれをadd行うことができますか (状態に保存する必要があり(forall s. MVector s Int)ますか?)。より効率的な実装方法はありますaddか?

4

1 に答える 1

2

ベクトルライブラリもよくわからないので、ほとんど一般的な原則に固執する必要があります。それをベンチマークし、アプリケーションで期待するものと同様の一連の追加を実行し、どのようなパフォーマンスが得られるかを確認してください。それが「十分」であれば、単純なコードに固執してください。そうでない場合は、a を状態に格納する前に(forall s. MVector s Int)(これを直接行うことはできません。タプルは forall 型を保持できないため、ラップする必要があります)、変更可能なベクトルに変換して追加動作を改善し、フリーズする前にそこに連結して、大まかに不変のベクトルを再び取得します

add v1 = do
    S v2 <- get
    let v3 = runST $ do
                m1 <- unsafeThaw v2
                m2 <- unsafeGrow m1 (length v1)
                -- copy contents of v1 behind contents of v2
                unsafeFreeze m2
    put (S v3)

そこにいくらかの厳密さを挿入する必要があるかもしれません。ただし、unsafeGrow をコピーする必要がある場合、償却された O(n) の動作は保証されません。

償却された O(n) 動作を取得するには、次のようにします。

  1. 使用済みスロット数も状態に保存する
  2. 新しいベクターが最後の空き領域に収まる場合は、解凍、コピー、成長せずにフリーズします
  3. 空き領域に収まらない場合は、少なくとも 2 倍に拡大します。これにより、各要素が平均して最大 2 回コピーされることが保証されます。
于 2011-10-27T12:43:38.057 に答える