我正在寻找有关将哪种数据结构用于 OCaml 中可扩展的超大型结构的建议。
通过很好的扩展，我不希望堆栈溢出或指数堆增长，假设有足够的内存。所以这几乎消除了标准库的 List.map 函数。速度不是什么大问题。
但对于初学者来说，假设我在 2^10 - 2^100 个项目的范围内操作。
我对结构只执行了三个“操作”：
(1) 结构子集上的映射函数，它增加或减少结构
(2)扫描结构
(3) 删除结构中满足特定标准的特定项目对
最初我使用的是常规列表，这仍然是非常可取的，因为结构在不断变化。通常在执行完所有操作之后，该结构最多要么在大小上翻倍（或大约一倍），要么缩小为空列表 []。也许翻倍从一开始就注定了我，但这是不可避免的。
无论如何，大约 2^15 --- 2^40 个项目开始引起严重问题（可能是由于我也使用了简单的列表函数）。该程序使用了 100% 的 cpu，但几乎没有内存，并且通常在一两天后堆栈溢出。
如果可能的话，我宁愿开始使用更多内存，以便继续在更大的空间中运行。
无论如何，如果有人有任何建议，将不胜感激。
如果理论上您有足够的空间来包含数据结构的所有项目，那么您应该查看具有高效内存表示的数据结构，并且尽可能少地进行簿记。动态数组（当您需要更多空间时以指数方式调整大小）比列表（支付一个完整的单词来存储每个单元格的尾部）更有效地存储，因此对于相同的内存使用，您将获得大约两倍的元素。
如果您无法将所有元素都保存在内存中（这就是您的数字的样子），您应该使用更抽象的表示。如果没有更多关于您的元素是什么的信息，很难说出更多信息。但也许抽象表示的一个例子可以帮助你设计你需要的东西。
想象一下，我想记录一组整数。我想制作这些集合的并集、交集，以及一些更时髦的操作，例如“获取所有多重元素”。我希望能够为非常大的集合（无数不同的整数）做到这一点，然后我希望能够在我构建的这个集合中选择一个元素，任何一个。我可以做的是存储与这些集合的定义相对应的逻辑公式，而不是尝试存储整数列表、整数集或布尔数组：整数集的特征是这样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) 函数将不允许您轻松地对结果进行推理，也许您可以将该映射操作表述为一个具体的组合操作），更准确地说，您将能够在这个抽象级别上处理它们，而无需实际计算元素。