6

コンストラクター配列を使用してhaskellで配列を作成するにはどうすればよいですか？つまり、最初の要素などを作成しますか？その場合、関連するリストをどのように読み取りますか？

たとえば、次の2つのプログラムを検討する場合：-

ar :: Int->(Array Int Int)
ar n = array (0,(n-1)) (((n-1),1):[(i,((ar n)!(i+1))) | i<-[0..(n-2)]])

ar :: Int->(Array Int Int)
ar n = array (0,(n-1)) ((0,1):[(i,((ar n)!(i-1))) | i<-[1..(n-1)]])

これら2つは時間計算量が異なりますか？

4

1 に答える 1

5

それは実装に依存しますが、合理的な実装では、両方とも同じ複雑さ (配列サイズの線形) を持ちます。

GHCの配列実装では、コードを見ると

array (l,u) ies
    = let n = safeRangeSize (l,u)
      in unsafeArray' (l,u) n
                      [(safeIndex (l,u) n i, e) | (i, e) <- ies]

{-# INLINE unsafeArray' #-}
unsafeArray' :: Ix i => (i,i) -> Int -> [(Int, e)] -> Array i e
unsafeArray' (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
    case newArray# n# arrEleBottom s1# of
        (# s2#, marr# #) ->
            foldr (fill marr#) (done l u n marr#) ies s2#)

{-# INLINE fill #-}
fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
-- NB: put the \s after the "=" so that 'fill' 
--     inlines when applied to three args 
fill marr# (I# i#, e) next 
 = \s1# -> case writeArray# marr# i# e s1# of 
             s2# -> next s2#

最初に新しいメモリのチャンクが配列に割り当てられ、それが順次埋められarrEleBottom(これはerrorメッセージ「undefined array element」を伴う呼び出しです)、次にリストで提供された要素がそれぞれのインデックスに書き込まれます。リストに表示される順序で。

一般に、ボックス化された配列であるため、構築時に配列に書き込まれるのは、必要なときに値を計算する方法を指定するサンクです (明示的に指定された値は、例のリテラルのよう1に、直接ポインターになります)配列に書き込まれたその値に)。

このようなサンクの評価が強制されると、ここのように、サンクが他の配列要素を参照する場合、配列内のさらなるサンクの評価も強制される場合があります。ここの特定の例では、任意のサンクを強制すると、後ですべてのサンクが強制されます。別の配列要素を参照しないエントリの最後に到達するまで、配列の前に移動します。最初の例では、強制される最初の配列要素がインデックス 0 の要素である場合、配列の長さに比例するサイズのサンクが作成され、それが縮小されるため、最初の配列要素を強制すると複雑さが O(n) になります。それ以降のすべての要素はすでに評価されており、それらを強制するのは O(1) です。2 番目の例では、状況は対称的であり、最後の要素を最初に強制すると、合計評価コストが発生します。要素が別の順序で要求される場合、すべてのサンクを評価するコストは、さまざまな要素のリクエストに分散されますが、総コストは同じです。まだ評価されていないサンクを評価するコストは、評価済みの次のサンクからの距離に比例し、その間のすべてのサンクの評価が含まれます。

配列アクセスは一定時間であるため (キャッシュ効果を除くが、配列を順方向または逆方向に埋めても違いはないはずです。インデックスがランダムな順序であれば大きな違いが生じる可能性がありますが、それでも影響はありません)時間の複雑さ)、両方とも同じ複雑さを持ちます。

ただし、ar n配列要素を定義するために使用すると、複数の配列が割り当てられるリスクがあることに注意してください(最適化なしでコンパイルされた場合、GHCはそれを行います-テスト済み:最適化が発生する可能性があります)。1 つだけが構築されるようにするには、次のようにします。

ar n = result
  where
    result = array (0,n-1) (... result!index ...)
于 2012-10-27T18:36:07.813 に答える