从数据集创建一个非常大的唯一列表以适应内存

Question

我有一个包含1.2亿条记录的列表,每条记录大约40/50字节,大约是5.5/6千兆字节的原始内存空间,不包括将阵列保存在内存中所需的任何额外存储空间.

我想确保此列表是唯一的.我尝试这样做的方法是创建一个Hashset <string>并逐个添加所有条目.

当我得到大约3300万条记录时,我内存不足,列表创建速度慢下来.

有没有更好的方法及时对这个庞大的条目列表进行排序？我能想到的唯一解决方案是使用Amazon EC2高内存四倍超大型实例一小时.

谢谢

Answer 1

如果您只是想检查唯一性,我只需将输入序列拆分为桶,然后分别检查每个桶.

例如,假设您正在从文件加载数据,您可以将输入流入,并将其写入26个不同的文件,每个文件对应一个记录开头的字母(我天真地假设每个记录以AZ开头 - 请根据您的实际情况进行调整).然后,您可以使用类似现有代码的内容检查每个较小的文件的唯一性 - 因为它们中的任何一个都不会太大而无法一次装入内存.初始存储保证不存在任何存在于不同存储桶中的重复条目.

当然,有各种不同的方法可以执行分段,不同的方法对不同的数据集有效.例如,您可以通过哈希代码进行存储 - 获取哈希代码的底部5位以创建32个不同的存储桶.这可能会在桶之间获得相当平等的记录分布,并且不会对输入数据做出任何假设.我只提到了上面的"采取第一个字母的方法",因为这是一个更简单的方法来掌握这个概念:)