ocaml非常に大きなデータ構造の提案

Question

OCamlの非常に大きな構造のためにどのようなデータ構造を使うべきかについての提案を探しています。

スケールでは、十分なメモリがあると仮定して、スタックオーバーフローや指数関数的なヒープの成長を望んでいません。これにより、標準libのList.map関数がほとんどなくなります。スピードはそれほど問題ではありません。

しかし、私は2^10-2^100個の領域で操作しているとしましょう。

Iは、構造上の実行3つだけ「操作」がある：

（1）構造のサブセットにマップ関数を、（2）構造を走査た増加または減少のいずれかの構造

が

（3）特定の基準を満たす構造内のアイテムの特定ペアの除去

構造は常にCであるため、もともとは、依然として非常に望まれており、定期的なリストを使用しました。吊るす。通常、すべての操作が実行された後、構造体は最大でサイズが2倍（またはその付近で）か、または空のリスト[]に縮小されます。多分倍増は私を最初から苦しめるでしょうが、やむを得ないことです。

いずれにしても、約2^15 --- 2^40個のアイテムが重大な問題を引き起こします（恐らく私が使用していた素朴なリスト機能によるものかもしれません）。プログラムはCPUの100％を使用しますが、メモリはほとんどありません。通常、1日か2日後にスタックオーバーフローします。

可能であれば、より大きなスペースで操作を続けるために、もっと多くのメモリを使い始めることをお勧めします。

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

Answer 1

理論上、データ構造のすべての項目を格納するのに十分な領域がある場合は、効率的なメモリ表現を持つデータ構造を見て、できるだけ少ない論理をとる必要があります。ダイナミックアレイ（余分なスペースが必要なときに指数関数的にサイズを変更する）はリストよりも効率的に格納されます（各セルの末尾を格納するための完全な単語を消費します）ので、同じメモリの使用で約2倍の要素が得られます。

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

整数のセットを記録したいとします。私は、ユニオン、それらのセットの交差点、さらには「複数の要素をすべて取得する」などのいくつかのファンキーな操作を作成したいと思います。私は本当に大きなセット（別々の整数のzillions）のためにそれを行うことができるようにしたい、そして、私は構築したこのセットの中の1つの要素、いずれかを選ぶことができるようにしたい。整数リスト、整数セット、またはブール値の配列を格納しようとするのではなく、それらのセットの定義に対応する論理式を格納することができます。PはFのような式で表されます。F(n) ⇔ n∈P 。したがって、私はpredicationsの種類（条件）を定義することができます。これらの式の保存

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）関数を保存すると、結果に簡単に理由を付けることはできません。実際に要素を計算することなく、より抽象的なレベルでより正確に作業することができます。