4

Vectorたとえば、並べ替えられた値があります

fromList [1, 2, 4, 5]

ここで、別の値を挿入したいと思います。たとえば3、新しいベクトルを作成してみましょう。命令型言語では、サイズ 5 の配列を割り当て、元のベクトルをループし、古い値をコピーして、新しい値を適切な位置に挿入します。

fromList [1, 2, 3, 4, 5]

ベクターAPIを使用してそれを行うことができます

let (pre, post) = span (< x) n
in V.concat [pre, pure x, post]

これは機能しますが、元のベクトルを 2 回トラバースします。分割を検索するときに 1 回、結合するときに 1 回です。ワンパスでそれを行う方法はありますか？(別の解決策は、バイナリ検索を使用して分割点を検索することですが、本物のシングルパス ソリューションを作成できるかどうかに興味があります。)

4

2 に答える 2

3

user5402の答えはそれを行うための非常にきれいな方法ですが、Data.Vector ドキュメントに記載されている効率の問題の犠牲になります。具体的には、挿入スポットを見つけてやみくもにコピーすると、ソースベクターから実際に値を読み取ることを強制しなくなります。代わりに、強制的にソース ベクターから読み取ったサンクでデスティネーション ベクターを埋めます。

オリジナルソリューション

注：これは私が思いついた最初の解決策です。理解するのは非常に簡単ですが、 のストリーム フュージョン システムではうまく機能せず、vectorパフォーマンスが比較的低下する可能性があります。以下の解決策は、一般的に優れています。

ドキュメントで説明されているように、1 つの解決策は、モナドindexM演算を使用してこれらのブラインド読み取りを実行することです。これにより、読み取りが強制的に実行されますが、読み取り値は強制されません。したがって、ポインター (場合によってはサンクへのポインター) をソース ベクターから宛先ベクターにコピーします。unsafe最大限の効率を得るには、以下のすべてをそのバリアント ( unsafeIndexM、unsafeIndex、およびunsafeWrite特に)に置き換える必要があります。

{-# Language ScopedTypeVariables #-}
module Insert where
import qualified Data.Vector as V
import Data.Vector (Vector)
import qualified Data.Vector.Mutable as MV
import Data.Vector.Mutable (MVector)
import Control.Monad.ST

insertElem :: forall a . Ord a => a -> Vector a -> Vector a
insertElem e v = V.create act
 where
  act :: forall s . ST s (MVector s a)
  act = do
    mv <- MV.new (V.length v + 1)
    let
      start :: Int -> ST s (MVector s a)
      start i
        | i == V.length v ||
          e <= v V.! i = MV.write mv i e >> finish i
        | otherwise = MV.write mv i (v V.! i) >> start (i+1)
      finish :: Int -> ST s (MVector s a)
      finish i
        | i == V.length v = return mv
        | otherwise = do
             V.indexM v i >>= MV.write mv (i+1)
             finish (i+1)
      in start 0

insertElemInt :: Int -> Vector Int -> Vector Int
insertElemInt = insertElem

actアクションに名前を付けて使用するScopedTypeVariables必要は実際にはありませんが、間違いを追跡するのに非常に役立つことがわかりました.

ストリームベースのソリューション

上記のコードは、ストリーム フュージョンではうまく機能しません。インデックスがあちこちに飛んでいるためです。次のアプローチは適切に融合し、不要なサンクの作成を回避する必要があります。ストリームフュージョンコードに触れるのはこれが初めてなので、改善できる点があるかもしれません。この最初のストリーム ベース バージョンの唯一の問題は、融合した場合、入力ストリームのステップ関数が要素の 1 つで 2 回実行されることです。これは通常は問題になりませんが、ステップ関数が非常に高価な (まれな) 場合は、問題になる可能性があります。したがって、その場合により適切に機能する代替手段を提供します。これらのどちらが実際にいつより優れているかはわかりませんので、両方を含めます。

これらのストリームベースのソリューションのいずれかを使用すると、コードは

testEnum :: Word -> Word -> Word -> Word
testEnum ins low high = V.product $
  insertElem ins $ V.enumFromStepN low 1 (fromIntegral high)

定数空間で実行されるループにコンパイルされ、実際にはベクターはまったく作成されません。

1つのシードを2回ステップ

{-# Language ScopedTypeVariables #-}
module Insert where

import Data.Vector (Vector)
import Data.Word (Word)
import qualified Data.Vector.Fusion.Stream.Monadic as S
import qualified Data.Vector.Generic as G
import Data.Vector.Fusion.Util (Id(..))

-- To check on unboxing and such
insertElemWord :: Word -> Vector Word -> Vector Word
insertElemWord = insertElem

{-# INLINE insertElem #-}
insertElem :: forall a . Ord a => a -> Vector a -> Vector a
insertElem a v = G.unstream (insertElemS a (G.stream v))

{-# INLINE [1] insertElemS #-}
insertElemS :: forall a . Ord a => a -> S.Stream Id a -> S.Stream Id a
insertElemS e (S.Stream step (state::s) size) = S.Stream step' (state, False) (size + 1)
  where
    {-# INLINE [0] step' #-}
    step' :: (s, Bool) -> Id (S.Step (s, Bool) a)
    step' (s, True) = Id $ case unId (step s) of
       S.Yield a s' -> S.Yield a (s', True)
       S.Skip s' -> S.Skip (s', True)
       S.Done -> S.Done
    step' (s, False) = Id $ case unId (step s) of
       S.Yield a s' ->
          if e <= a
          then S.Yield e (s, True)
          else S.Yield a (s', False)
       S.Skip s' -> S.Skip (s', False)
       S.Done -> S.Yield e (s, True)

ルックアップ/ステップを繰り返さない、正確に 1 つのパス

{-# Language ScopedTypeVariables #-}
module Insert where

import Data.Vector (Vector)
import Data.Word (Word)
import qualified Data.Vector.Fusion.Stream.Monadic as S
import qualified Data.Vector.Generic as G
import Data.Vector.Fusion.Util (Id(..))

data Status s a = Pre s | During s a | Post s | End

insertElemWord :: Word -> Vector Word -> Vector Word
insertElemWord = insertElem

{-# INLINE insertElem #-}
insertElem :: forall a . Ord a => a -> Vector a -> Vector a
insertElem a v = G.unstream (insertElemS a (G.stream v))

{-# INLINE [1] insertElemS #-}
insertElemS :: forall a . Ord a => a -> S.Stream Id a -> S.Stream Id a
insertElemS e (S.Stream step (state::s) size) = S.Stream step' (Pre state) (size+1)
  where
    {-# INLINE [0] step' #-}
    step' :: Status s a -> Id (S.Step (Status s a) a)
    step' (Post s) = Id $ case unId (step s) of
      S.Yield a s' -> S.Yield a (Post s')
      S.Skip s' -> S.Skip (Post s')
      S.Done -> S.Done
    step' (Pre s) = Id $ case unId (step s) of
      S.Yield a s'
        | e <= a    -> S.Yield e (During s' a)
        | otherwise -> S.Yield a (Pre s')
      S.Skip s' -> S.Skip (Pre s')
      S.Done -> S.Yield e End
    step' (During s a) = Id (S.Yield a (Post s))
    step' End = Id S.Done
于 2015-02-23T00:44:03.473 に答える
3

利用できると思われる最良のツールはunfoldr、たとえば次のとおりです。

import qualified Data.Vector as V
import Data.Vector (Vector)

insertElem :: Int -> Vector Int -> Vector Int
insertElem e v = V.unfoldrN (len+1) go (0,False)
  where
    len = V.length v
    go (i,found)
      | i >= len  = if found then Nothing else Just (e, (i+1, True))
      | found     = Just (x, (i+1, True))
      | x <= e    = Just (x, (i+1, False))
      | otherwise = Just (e, (i, True))
      where x = v V.! i


test1 = insertElem 3 (V.fromList [1,2,4,5])
test2 = insertElem 0 (V.fromList [1,2,4,5])
test3 = insertElem 6 (V.fromList [1,2,4,5])

go関数内のロジックを重複排除しようとはしませんでした。

于 2015-02-22T15:43:34.780 に答える