3

我需要建立查找表。我使用 Dictionary 它包含 45M long 和 45M int 。只要 key 和 int 作为 value 。集合的大小为 (45M*12) 其中 long 为 8 字节， int 为 4 字节 大小约为 515 Mbyte 。但实际上进程的大小是 1.3 Gbyte 。该过程仅包含此查找表。Mat be，有没有字典的替代品？

谢谢

4

5 回答 5

3

你愿意付出多少努力？
你可以使用一个

KeyValuePair<long,int>[] table = new KeyValuePair<long,int> [45 M];

然后在第一列 ( long Key) 上对其进行排序并使用二进制搜索来查找您的值。

于 2012-05-24T17:36:31.033 回答
1

如果您的范围限制为 10^12 的最大 long 值，那么空间方面的问题是您必须使用 long，因为您只需要比 int 可以容纳的多几位。如果是这种情况，您可以执行以下操作：将数据存储在 512 Dictionary 的数组中

 var myData = new Dictionary<int,int>[512];

要引用与 long 值关联的 int（在此示例中我将其称为“key”），您可以执行以下操作：

myData[key & 511].Add((int) (key >> 9), intValue);
int result = myData[(int) (key & 511)][(int) (key >> 9)];

您创建的字典数量以及位摆弄中使用的位数可能需要调整以适应数据的真实约束。使用这种方法可以减少大约三分之一的内存使用量

于 2012-05-24T18:26:32.883 回答
1

您可以使用 SortedList 而不是 Dictionary，这将提高内存效率，但 CPU 效率可能会稍低，忽略有关测量内存的问题以及为什么首先需要一次性加载这么多数据:)

于 2012-05-24T17:35:40.453 回答
1

字典有一个保存数据的底层数组，但数组的大小必须大于你拥有的项目数，这就是字典查找速度的来源。事实上，底层数组的大小应该比项目数（25+%）大很多。结合这一点，当您添加项目时，该底层数组正在被取消分配和重新创建（以使其更大），您可能有相当多的内存准备好进行垃圾收集（这意味着如果您实际上需要更多内存GC 会回收它，但既然你现在有足够的东西，它不会打扰）。

这个字典消耗的内存是否超出了您的允许范围，或者您只是好奇为什么它比您想象的要多？您可以使用其他选项（其他答案和评论列出了一些），它们将使用更少的内存但也会更慢。您是否遇到内存不足的问题？

于 2012-05-24T17:39:21.707 回答
0

另一种方法，假设数据是静态的：使用两个排序的数组——一个是long，一个是int。确保一个索引 N 处的项目是另一个索引 N 处的键的值。使用Array.BinarySearch查找您要查找的键值。

于 2012-05-24T17:38:57.700 回答