3

私は、OCaml の非常に大規模な構造に対して、どのような種類のデータ構造を使用するかについての提案を探しています。

十分なメモリがあると仮定すると、適切にスケーリングすることで、スタック オーバーフローや指数関数的なヒープの増加は望ましくありません。したがって、これにより、標準ライブラリの List.map 関数がほとんどなくなります。速度はそれほど問題ではありません。

しかし、まず、2^10 から 2^100 アイテムの領域で作業していると仮定しましょう。

構造に対して実行する「操作」は 3 つだけです。

(1) 構造を増加または減少させる、構造のサブセットに対するマップ関数

(2)構造のスキャン

(3) 特定の基準を満たす構造内のアイテムの特定のペアの削除

もともと私は通常のリストを使用していましたが、構造が常に変化しているため、これは依然として非常に望ましいものです。通常、すべての操作が実行された後、構造体のサイズはせいぜい 2 倍 (またはその程度) になるか、空のリスト [] に縮小されます。おそらく、倍増は最初から私を運命づけますが、それは避けられません.

いずれにせよ、約 2^15 --- 2^40 個のアイテムが深刻な問題を引き起こし始めます (おそらく、私が使用していた単純なリスト関数も原因です)。プログラムは CPU を 100% 使用しますが、メモリはほとんど使用せず、通常は 1 日か 2 日後にスタック オーバーフローが発生します。

より大きなスペースでの操作を継続するために、可能であれば、より多くのメモリの使用を開始したいと考えています。

とにかく、誰かが何か提案があれば、それは大歓迎です。

4

1 に答える 1

2

理論的には、データ構造のすべての項目を含めるのに十分なスペースがある場合は、ブックイーピングをできるだけ少なくして、効率的なメモリ表現を備えたデータ構造を検討する必要があります。動的配列（より多くのスペースが必要なときに指数関数的にサイズ変更する）は、リスト（各セルの末尾を格納するために完全な単語を支払う）よりも効率的に格納されるため、同じメモリ使用量で約2倍の要素を取得できます。

すべての要素をメモリに保持できない場合（これはあなたの番号がどのように見えるかです）、より抽象的な表現を選択する必要があります。あなたの要素が何であるかについてのより多くの情報なしでより多くを伝えることは難しいです。しかし、抽象的な表現の例は、必要なものを考案するのに役立つかもしれません。

整数のセットを記録したいとします。和集合、それらのセットの共通部分、および「複数のすべての要素を取得する」などのよりファンキーな操作を作成したいと思います。非常に大きなセット（数十億の異なる整数）に対してそれを実行できるようにしたいので、次に、作成したこのセット内の1つの要素（任意の1つ）を選択できるようにします。整数のリスト、整数のセット、またはブール値の配列を格納しようとする代わりに、私ができることは、それらのセットの定義に対応する論理式を格納することです。整数のセットは、次のようなP式によって特徴付けられます。したがって、述語（条件）のタイプを定義できます。FF(n) ⇔ n∈P

type predicate =
  | Segment of int * int   (* n ∈ [a;b] *)
  | Inter of predicate * predicate
  | Union of predicate * predicate
  | Multiple of int  (* n mod a = 0 *)

これらの数式を保存するには、メモリはほとんど必要ありません（合計で適用する操作の数に比例します）。交差点や組合の建設には一定の時間がかかります。次に、式を満たす要素を見つけるためにいくつかの作業を行います。基本的に、これらの式が何を意味するのかを推論し、それらから通常の形式を取得し（これらはすべて、「いくつかのモジュロ基準を満たす区間の有限和の要素」の形式です）、そこからいくつかの要素を抽出する必要があります。

一般的なケースでは、「このサブセットにマッピングの結果を追加する」など、データセットで「コマンド」を取得すると、このコマンドを実際に評価する代わりに、これをデータとして保存できます。これは、構造。これらのコマンドをより正確に説明できます（たとえば、「map」と言いますが、（elem-> elem）関数を格納すると、結果を簡単に推論できません。おそらく、そのマッピング操作を次の具体的な組み合わせとして定式化できます。操作）、より正確には、実際に要素を計算することなく、この抽象的なレベルでそれらに取り組むことができます。

于 2012-04-24T09:55:30.460 に答える