c# - 有效地将超过 180 亿个输入值映射到几个输出值

Question

似乎下面(行)给出的信息不够清楚，所以我试图更清楚和简洁。

我需要关于如何将数十亿个 ulong 值映射到几个 int 值的建议。在最坏的情况下，我有超过 110 亿个(基本上是随机的 ulong 值)需要映射到 40 个 int 值。映射是已知的，字典可以工作，但需要的内存量除外。目前，估计在使用字典时大约 199GB 的 RAM 将用于所有需要的映射。

有谁知道可以使用任何类型的算法或过程来完成此映射而不消耗那么多 RAM？

---

我正在开发一个 C# - .NET 4.5 程序来帮助过滤我的数据，但遇到了效率问题。我目前正在通过 8 个(我最终需要做 20 个)不同的过滤器运行我的数据，每个过滤器都以相同的方式但在不同的级别过滤数据。在过滤过程的某个时刻，每个级别都有许多值必须编码到最终输出值中。

一些例子:

在第 3 级，有 23 个值被编码为 6 个可能的输出值 (0-5)。

在第 7 级，有 2,576 个值要编码为 14 个可能的输出值 (0-13)。

在第 10 级，有 88,215 个值被编码为 20 个可能的输出值 (0-19)。

当我达到 20 级时，我将有超过 110 亿个值被编码为 40 个输出值 (0-39)。

要为每个过滤器编码的值都是事先已知的，我正在从文件中读取此信息并为每个过滤器(当前为 1 到 8)填充一个单独的字典。按照这个速度，到我过滤 20 个时，将有超过 165 亿个字典条目，其中大部分是 ulong 值。

从长远来看，这不是解决方案。

有谁知道可以更有效地将数百万个唯一输入值映射到几个唯一输出值的方法吗？

是否有一种算法可以将输入映射到输出？

我正在寻找任何可能为我指明正确方向的想法。

Answer 1

如果输入 CSV 文件中的值已排序，并且数据永远不会改变，我们可以放弃注释中的桶方法，只需将所有数据对塞入文件中的一个大数组中。目标是更好地组织数据，实现快速读取，从而避免将整个数据集存储在内存中。您必须将 CSV 文件转换为新的二进制格式，并在此过程中在内存中创建索引数组。这个索引数组也应该保存到某个索引文件中，以便程序重新启动时可以使用。在内存中，您只会保存其值以项目索引开头的第一个数据对的位置数组。在文件中，您将只有一个巨大的 32 位(4 字节)数字数组，其中每个数字的前 3 个字节是内存中索引项的剩余部分，最后一个字节是我们的输出。

要创建索引数组，您需要逐行读取 CSV 文件。为每个数据对(input_int、output_int)创建新的数据对(index、32 位值)。 Index 采用 input_int 的前 2 个字节，32 位值 是通过连接 input_int 的最后 3 个字节创建的，并且output_int 的唯一字节。如果 index 与之前的数据对发生了变化，则将文件的位置存储到新索引处的数组中。在任何情况下，将 32 位值 附加到文件。重复直到 CSV 文件结束。

假设我们有一个输入值 0x1234567890 并且需要相应的输出值。算法将在内存中找到索引为 0x1234 和 0x1235 的数组中的项。这将为您提供我们的项目可能在文件中的开始和结束位置。在此范围内，我们对值 0x567890 执行 binary search 并获取其后的字节。这就是我们的产值。