8

高速インデックス作成と高速追加の両方をサポートする Haskell のデータ構造を探しています。これは、再帰から生じるメモ化の問題です。

ベクトルが c++ で動作する方法 (これは変更可能ですが、この場合は問題にならないはずです) から、(償却された) O(1) 追加と O(1) インデックス作成の両方を持つ不変ベクトルが可能であるように思われます (わかりました、そうではありません、この質問へのコメントを参照してください)。これは Haskell で可能ですか、それとも (AFAICT とにかく) O(1) 追加と O(log(min(i,ni))) インデックスを持つ Data.Sequence を使用する必要がありますか?

これに関連して、Haskell の初心者として、Haskell のデータ構造に関する実用的で簡潔なガイドを切望していることに気づきました。理想的には、これにより、最も実用的なデータ構造のかなり包括的な概要と、パフォーマンス特性、およびそれらが実装されている Haskell ライブラリへのポインタが得られるでしょう。たくさんの情報が飛び交っているように見えますが、少し散らかっていることに気付きました。求めすぎですか？

4

3 に答える 3

10

単純なメモ化の問題の場合、通常、テーブルを一度作成してから後で変更しないようにします。その場合、メモ化テーブルの構築を 1 つの操作として考えると、追記を気にする必要がなくなります。

1 つの方法は、遅延評価を利用して、作成中にテーブルを参照することです。

import Data.Array
fibs = listArray (0, n-1) $ 0 : 1 : [fibs!(i-1) + fibs!(i-2) | i <- [2..n-1]]
  where n = 100

この方法は、テーブルの要素間の依存関係により、それらを事前に評価する単純な順序を考え出すことが困難な場合に特に役立ちます。ただし、ボックス化された配列またはベクトルを使用する必要があるため、オーバーヘッドが増えるため、このアプローチは大きなテーブルには適さない場合があります。

ボックス化されていないベクトルの場合、その下でミューテーションconstructNを使用してテーブルを効率的にしながら、純粋な方法でテーブルを構築できるような操作があります。これは、これまでに構築されたベクトルの接頭辞の不変ビューを渡した関数に与えることによって行われます。これを使用して、次の要素を計算できます。

import Data.Vector.Unboxed as V
fibs = constructN 100 f
  where f xs | i < 2 = i
             | otherwise = xs!(i-1) + xs!(i-2)
             where i = V.length xs
于 2012-05-03T22:40:56.417 に答える
9

メモリが機能する場合、C++ ベクトルは境界とサイズ情報を持つ配列として実装されます。挿入によって境界がサイズを超えて増加する場合、サイズは 2 倍になります。これは償却された O(1) 回の挿入 (あなたが主張する O(1) ではない) であり、Haskell でArrayタイプを使用して、おそらく適切なIOまたはST先頭に追加して、うまくエミュレートできます。

于 2012-05-03T21:59:59.313 に答える
7

これを見て、何を使用すべきかをより多くの情報に基づいて選択してください。

しかし、単純なことは、C++ のベクトルに相当するものが必要な場合は、 を使用することData.Vectorです。

于 2012-05-03T22:06:23.537 に答える