我有一个大文件，其中一行像ID|VALUE一次通过。
在 ID 重复的情况下，必须忽略行。
如何有效地进行这种检查？
补充：ID 很长（8 个字节）。我需要一个使用最少内存的解决方案。
谢谢你们的帮助。我现在能够增加堆空间并使用 Set。
6 回答
4
您可以将数据存储在 TLongObjectHashMap 中或使用 TLongHashSet。这些类有效地存储基于基元的信息。
500 万个长值将在 TLongHashSet 中使用 < 60 MB，但是 TLongObjectHashMap 也将有效地存储您的值。
要了解有关这些课程的更多信息
于 2011-07-06T10:11:56.837 回答
2
无论如何，您都必须将 ID 存储在某个地方以检测重复项。在这里，我将使用 aHashSet<String>及其contains方法。
于 2011-07-06T09:58:31.030 回答
2
您必须读取整个文件，一次一行。您必须保留一组 ID，并将传入的 ID 与 Set 中已有的值进行比较。如果出现值，请跳过该行。
您自己编写了用例；这里没有魔法。
于 2011-07-06T09:58:59.600 回答
2
对我来说，这看起来像是一个典型的数据库任务。如果您的应用程序中使用了数据库，则可以利用它来完成您的任务。创建一个具有 UNIQUE INTEGER 字段的表并开始添加行；你会在重复的 ID 上得到一个例外。数据库引擎将负责光标窗口和缓存，因此它适合您的内存预算。然后在你完成后放下那张桌子。
于 2011-07-06T11:06:32.367 回答
2
有两种基本解决方案；
首先，正如上面 duffymo 和 Andreas_D 所建议的，您可以将所有值存储在Set. 这为您提供了 O(n) 时间复杂度和 O(n) 内存使用量。
其次，如果O(n)内存太多，可以牺牲速度在O(1)内存中做。对于文件中的每一行，读取它之前的所有其他行，如果 ID 出现在当前行之前，则丢弃。
于 2011-07-06T11:19:23.490 回答
1
概率算法呢？
Bloom filter ... 是一种节省空间的概率数据结构，用于测试元素是否是集合的成员。假阳性是可能的，但假阴性是不可能的。
于 2011-07-06T10:50:44.057 回答