Data.Vectorから償却されたO（n）連結を確実にする方法はありますか？

Question

私は、コードの一部にベクトルを使うのが効率的なアプリケーションを持っています。しかし、計算中にいくつかの要素を追跡する必要があります。私は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)) 

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

Answer 1

私はベクターライブラリーもよく知らないので、一般的な原則に固執する必要があります。それをベンチマークして、アプリケーションで期待するものと似た一連の追加を実行し、どのようなパフォーマンスが得られるかを確認します。それが「十分に良い」ならば、シンプルなコードに固執してください。そうでない場合は、(forall s. MVector s Int)を状態に保存する前に（タプルはすべての型を保持できないため、ラップする必要があります）、可変ビヘイビアに変換して追加ビヘイビアを改善し、フリーズする前に連結して、もう一度不変ベクトルを得ることができます。

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）の動作は保証されません。

新しいベクトルが最後に空きスペースに収まる場合は、

すぎた状態で使用スロットの数を格納

1. によって償却O（n）の動作を得ることができ、解凍、コピー、各要素は平均