在关键服务器上(数十亿个文件名)对字符串进行内存约束的外部排序,并将重复数据组合在一起计算

我们的服务器在其日志文件夹中生成{c521c143-2a23-42ef-89d1-557915e2323a}-sign.xml文件。 第一部分是GUID; 第二部分是名称模板。

我想计算具有相同名称模板的文件数。 例如,我们有

 {c521c143-2a23-42ef-89d1-557915e2323a}-sign.xml {aa3718d1-98e2-4559-bab0-1c69f04eb7ec}-hero.xml {0c7a50dc-972e-4062-a60c-062a51c7b32c}-sign.xml 

结果应该是

 sign.xml,2 hero.xml,1 

可能的名称模板的总种类未知,可能超过int.MaxValue

服务器上的文件总数未知,可能超过int.MaxValue

要求

最终结果应按名称模板排序。

该工具将运行的服务器是超级关键的。 在运行工具之前,我们应该能够告诉内存使用情况(MB)和生成的临时文件的数量(如果有),并且不知道日志文件夹的任何特征。

我们使用C#语言。

我的想法

  • 对于前5000个文件,计算出现次数,将结果写入Group1.txt
  • 对于第二个5000个文件,计算出现次数,将结果写入Group2.txt
  • 重复,直到处理完所有文件。 现在我们有一堆组文件。

然后我合并所有这些组文件。

  Group1.txt Group2.txt Group3.txt Group4.txt \ / \ / Group1-2.txt Group3-4.txt \ / Group1-4.txt 

Group1-4.txt是最终结果。

我和我朋友之间的分歧是我们如何计算事件的数量。

我建议使用字典。 文件名模板是关键。 设m为分区大小。 (在这个例子中它是5000.)然后时间复杂度O(m),空间复杂度O(m)。

我的朋友建议对名称模板进行排序,然后在一次传递中对事件进行计数,因为相同的名称模板现在都在一起。 时间复杂度O(m log m),空间复杂度O(m)。

我们无法说服对方。 你们看到这两种方法有什么问题吗?

如果已经研究了具有重复计数合并的外部排序,则IDK。 我找到了1983年的论文(见下文)。 通常,在假设通过键对对象进行排序的情况下设计和研究排序算法,因此重复的键具有不同的对象。 可能有一些关于此的现有文献,但这是一个非常有趣的问题。 可能它只是被认为是紧凑字典的应用与外部合并排序相结合。

用于在小内存中存储大量字符串的高效字典是一个非常好的研究问题。 大多数有用的数据结构可以包括每个单词的辅助数据(在我们的例子中,是重复计数)。


TL:DR总结有用的想法,因为我在这个答案的主体中对许多事情进行了过多的详细讨论:

  • 字典大小达到阈值时的批次边界,而不是固定数量的输入文件之后。 如果一组5000个字符串中有很多重复项,你仍然不会使用很多内存。 你可以通过这种方式在第一次传递中找到更多重复的方法。

  • 分类批次使合并更快。 您可以并且应该合并多个 – >一个而不是二进制合并。 使用PriorityQueue确定哪个输入文件具有您接下来应该使用的行。

  • 为了避免在对哈希表中的键进行排序时出现内存使用突发,请使用可以按顺序遍历键的字典。 (即即时排序。)有SortedDictionary (基于二叉树)。 这也将排序的CPU使用与等待获取输入字符串的I / O交错。

  • Radix – 按照第一个字符对每个批次进行排序(az,在A之前排序的非字母,以及在z之后排序的非字母)。 或者其他一些可以很好地分配您的密钥的分组选择。 为每个基数桶使用单独的词典,并在达到内存上限时仅将最大的词典清空。 (发烧友驱逐启发式比“最大”可能是值得的。)

  • 节流I / O(特别是合并时),并检查系统CPU负载和内存压力。 相应地调整行为以确保在服务器最忙时不会产生影响。

  • 对于以CPU时间为代价的较小临时文件,请使用公共前缀编码,或者使用lz4。

  • 对于相同的高端内存绑定,节省空间的字典将允许更大的批量大小(因此更大的重复查找窗口)。 Trie (或更好的, Radix Trie )可能是理想的,因为它将字符存储在树节点中,公共前缀仅存储一次。 定向非循环字图更加紧凑(在不是前缀的公共子串之间找到冗余)。 使用一个作为字典是棘手的,但可能是可能的(见下文)。

  • 利用以下事实:在您要清空整个字典之前,不需要删除任何树节点或字符串。 使用可增长的节点数组,以及另一个可增长的char数组,它可以从头到尾包装字符串。 (对于Radix Trie(多字符节点)很有用,但不是常规Trie,其中每个节点都是一个char。)

  • 根据重复项的分发方式,您可能会或可能无法在第一次传递中找到很多重复项。 这有一些含义,但并没有真正改变你最终合并的方式。


我假设你有一些目录遍历的想法,它可以有效地为你的代码提供一个字符串流,以便进行统一和计算。 所以我只会说“字符串”或“键”,来谈谈输入。

修剪尽可能多的不必要的字符(例如,如果它们都是.xml则丢失.xml )。


在单独的计算机上执行CPU /内存密集型工作可能很有用,具体取决于您与关键生产服务器的快速网络连接所具有的其他硬件。

您可以在服务器上运行一个简单的程序,该程序通过TCP连接将文件名发送到另一台机器上运行的程序,在该程序中可以安全地使用更多的内存。 服务器上的程序仍然可以进行小型字典批处理,只需将它们存储在远程文件系统上即可。


而现在,由于其他答案都没有真正把所有部分放在一起,这是我的实际答案:

内存使用的上限很容易。 编写程序以使用恒定的内存上限,无论输入大小如何。 更大的输入将导致更多的合并阶段,而不是任何时候更多的内存使用。

您可以在不查看输入的情况下对临时文件存储空间进行最佳估计,这是一个非常保守的上限,假设每个输入字符串都是唯一的。 您需要一些方法来估计将有多少输入字符串。 (大多数文件系统知道它们包含多少单独的文件,而不必遍历目录树并计算它们。)

您可以对重复项的分布做出一些假设,以便做出更好的猜测。

如果临时文件的数量而不是大小是一个问题,您可以将多个批次存储在同一个输出文件中,一个接一个。 在每个开头放置长度标头以允许批量跳过,或者将字节偏移写入单独的数据流。 如果大小也很重要,请参阅我关于使用frcode样式的通用前缀压缩的段落。


正如Ian Mercer在他的回答中指出的那样,对您的批次进行分类将使它们更有效地合并。 如果不这样做,您可能会冒险进入算法无法前进的墙,或者您需要执行一些操作,例如加载一个批次,扫描另一个批次以查找第一个中的条目,然后重写第二个批次只删除了可能很少的匹配条目。

不对你的批次进行排序会导致第一次传递O(N)的时间复杂度,但要么你必须在某个时候进行排序,要么你的后期阶段的最坏情况会严重恶化。 您希望您的输出全局排序,因此除了RadixSort接近之外,在某处无法避免O(N log N)。

在批量大小有限的情况下,预计会有O(log N)合并步骤,因此您的原始分析会忽略您的方法的O(N log N)复杂性,而忽略了在编写phase1批次之后需要执行的操作。


适当的设计选择会发生很大变化,具体取决于我们的内存上限是否足够大,可以在一批中找到多个重复内容。 即使像Trie这样的复杂紧凑型数据结构也没有多大帮助,将数据放入Trie并再次将其写出来批量写入会浪费CPU时间。

如果您无法在每个批次中进行多次重复消除,那么您需要进行优化,以便将可能匹配的密钥放在一起用于下一阶段。 您的第一个阶段可以将输入字符串按第一个字节分组,最多252个输出文件(不是所有256个值都是合法的文件名字符),或者输入27个左右的输出文件(字母+ misc),或者26 + 26 + 1大写/小写+非字母。 临时文件可以省略每个字符串的公共前缀。

然后,这些第一阶段批次中的大多数应具有更高的重复密度。 实际上,这种输入到输出桶的Radix分配在任何情况下都是有用的,见下文。

您仍然应该以块的forms对第一阶段输出进行排序,以便为下一次传递为同一RAM提供更宽的重复查找窗口。


我将花更多的时间在你可以在初始流中找到有用数量的重复项的域中,然后使用~100MiB的RAM,或者你选择的任何上限。

显然,我们将字符串添加到某种字典中以便动态查找和计算重复项,同时只需要为该组唯一字符串提供足够的存储空间。 只是存储字符串然后对它们进行排序将大大降低效率,因为我们在没有动态重复检测的情况下更快地达到RAM限制。

为了最小化phase2的工作,phase1应该找到并计算尽可能多的重复项,从而减少p2数据的总大小。 减少阶段2的合并工作量也很好。 更大的批次有助于这两个因素 ,所以在第1阶段安全地接近你的记忆上限是非常有用的。 不要在一定数量的输入字符串后写一个批处理,而是在你的内存消耗接近你选择的上限时进行。 重复计算并丢弃,并且不会占用任何额外的存储空间。

准确的内存记帐的另一种方法是跟踪字典中的唯一字符串,这很容易(并且由库实现为您完成)。 累积添加的字符串长度也可以很好地估计用于存储字符串的内存。 或者只是假设字符串长度分布。 最初使哈希表的大小合适,这样在添加元素时就不必增长,所以当它满60%(加载因子)时就会停止。


字典的节省空间的数据结构增加了给定内存限制的重复查找窗口。 当加载因子太高时,散列表的效率非常低,但散列表本身只需要存储指向字符串的指针。 它是最熟悉的字典,并具有库实现。

我们知道,一旦我们看到足够的唯一键,我们就会希望我们的批量排序,因此使用可以按排序顺序遍历的字典可能是有意义的。 由于我们正在从文件系统元数据中读取数据, 所以动态排序是有意义的,因为密钥会缓慢进入 ,受磁盘IO的限制。 一个缺点是,如果我们看到的大多数密钥都是重复的,那么我们正在进行大量的O(日志批量化)查找,而不是大量的O(1)查找。 当字典较大时,密钥更可能是重复的,因此大多数O(日志批量大小)查询的批量大小接近最大值,而不是均匀分布在0和最大值之间。 无论密钥是否唯一,树都会为每次查找支付排序的O(log n)开销。 哈希表仅在删除重复项后最终支付分类成本。 因此,对于树,它是O(total_keys * log unique_keys),哈希表是O(unique_keys * log unique_keys)来对批处理进行排序。

最大加载因子设置为0.75或者其他东西的哈希表可能相当密集,但是在写出批处理之前必须对KeyValuePair进行排序可能会阻碍使用标准Dictionary。 您不需要字符串的副本,但您可能最终会将所有指针(refs)复制到临时空间以进行非就地排序,也可能在排序之前将它们从哈希表中删除。 (或者不仅仅是指针,KeyValuePair,以避免必须返回并查找哈希表中的每个字符串)。 如果可以容忍大内存消耗的短暂峰值,并且不会导致您交换/分页到磁盘,那么你可以没问题。 如果你可以在哈希表使用的缓冲区中进行就地排序,这是可以避免的,但我怀疑标准库容器会发生这种情况。

除了内存消耗的爆发之外,在速度密钥上维持排序字典的CPU使用率的持续涓流可能比不常用的CPU使用率突然排序所有批量密钥更好。

.NET标准库有SortedDictionary ,文档说这是用二叉树实现的。 我没有检查它是否具有重新平衡function,或者使用红黑树来保证O(log n)最差情况下的性能。 我不确定它会有多少内存开销。 如果这是一次性任务,那么我绝对建议使用它来快速轻松地实现它。 并且还针对重复使用的更优化设计的第一版本。 除非你能找到一个很好的Tries库实现,否则你可能会发现它已经足够好了。


内存高效排序词典的数据结构

字典的内存效率越高,在写出批处理和删除字典之前,我们可以找到的副本越多。 此外,如果它是一个排序的字典,我们的批次可以更大,即使他们找不到重复。

数据结构选择的次要影响是我们在关键服务器上运行时产生的内存流量。 排序数组(具有O(log n)查找时间(二进制搜索)和O(n)插入时间(用于腾出空间的随机元素))将是紧凑的。 但是,它不仅会很慢,而且会在很多时候使用memmove使内存带宽饱和。 执行此操作的100%CPU使用率对服务器性能的影响大于搜索二叉树的100%CPU使用率。 它不知道从哪里加载下一个节点,直到它加载当前节点,因此它无法管道内存请求。 分支在树搜索中的错误预测也有助于减少所有内核共享的内存带宽的消耗。 (这是正确的,一些100%-CPU使用程序比其他程序差!)

如果清空我们的字典,当我们清空它时不会留下碎片,这很好。 但是,树节点的大小将是恒定的,因此一堆分散的空洞将可用于将来的树节点分配。 但是,如果我们为多个基数桶提供单独的字典(见下文),则与其他字典关联的关键字符串可能会与树节点混合在一起。 这可能导致malloc难以重用所有释放的内存,可能会通过一些小因素增加实际的OS可见内存使用量。 (除非C#运行时垃圾收集执行压缩,否则会处理碎片。)

由于在您想要清空字典并将其全部删除之前,您永远不需要删除节点,因此可以将Tree节点存储在可增长的数组中。 因此,内存管理只需要跟踪一个大的分配,与每个节点的malloc分开减少簿记开销。 左/右子指针可以是数组索引而不是实际指针。 这使您只能使用16位或24位。 ( 堆是存储在数组中的另一种二叉树,但它不能有效地用作字典。它是树,但不是搜索树)。

存储字典的字符串键通常是将每个String作为单独分配的对象来完成,并在数组中指向它们。 再一次,你永远不需要删除,增长甚至修改它们,直到你准备好全部删除它们为止,你可以将它们从头到尾打包在一个char数组中,每个数组末尾都有一个终止的零字节。 这再次节省了大量的簿记,并且还可以轻松跟踪关键字符串使用了多少内存,让您安全地接近您选择的内存上限。

Trie / DAWG可实现更紧凑的存储

为了更加密集地存储一组字符串,我们可以消除存储每个字符串的所有字符的冗余,因为可能存在许多共同的前缀。

Trie将字符串存储在树结构中,为您提供通用前缀压缩。 它可以按排序顺序遍历,因此可以即时排序。 每个节点都有尽可能多的子节点,因为集合中有不同的下一个字符,所以它不是二叉树。 AC#Trie部分实现(删除未写入)可以在此SO答案中找到,类似于此但不需要批处理/外部排序的问题。

Trie节点需要存储潜在的许多子指针,因此每个节点都可能很大。 或者每个节点可以是可变大小的,如果C#允许,那么保持节点内的nextchar:ref对列表。 或者正如维基百科文章所说,节点实际上可以是链表或二进制搜索树,以避免在具有少数子节点的节点中浪费空间。 (树的较低级别将具有很多。)需要字词结束标记/节点来区分不是单独的字典条目的子字符串和那些字母条目的子字符串。 我们的计数领域可以达到这个目的。 Count = 0表示此处结尾的子字符串不在字典中。 count> = 0表示它是。

更紧凑的Trie是Radix Tree或PATRICIA Tree ,它为每个节点存储多个字符。

这个想法的另一个扩展是确定性非循环有限状态自动机(DAFSA) ,有时称为有向无环字图(DAWG),但请注意, DAWG维基百科文章是关于同名的另一件事。 我不确定是否可以按排序顺序遍历DAWG以在最后获得所有密钥,并且正如维基百科指出的那样,存储相关数据(如重复计数)需要修改。 我也不确定它们是否可以逐步构建,但我认为你可以在没有压缩的情况下进行查找。 新添加的条目将像Trie一样存储,直到压缩步骤每128个新密钥将它们合并到DAWG中。 (或者对于更大的DAWG来说,不那么频繁地运行压缩,所以你没有做太多,比如当哈希表必须增长时,将哈希表的大小加倍,而不是线性增长,以分摊昂贵的操作。)

当没有任何分支/聚合时,您可以通过在单个节点中存储多个字符来使DAWG更紧凑。 本页还提到了一种用于压缩DAWG的霍夫曼编码方法,并提供了一些其他链接和文章引用。

JohnPaul Adamovsky的DAWG实现(在C中)看起来很好,并描述了它使用的一些优化。 我没有仔细查看它是否可以将字符串映射到计数。 它经过优化,可以存储arrays中的所有节点。

对1TB文本问题中的重复计数单词的答案表明了DAWG,并且有几个链接,但我不确定它有多么有用。


编写批次:第一个字符的基数

您可以启用RadixSort,并为每个起始字符保留单独的字典(或者在z之前排序的非字母,非z之后排序的非字母)。 每个字典都写出一个不同的临时文件。 如果您有多个计算节点可用于MapReduce方法,那么这将是将合并工作分配给计算节点的方法。

这允许一个有趣的修改:不是一次写入所有基数桶,而只是将最大的字典作为批处理 。 这可以防止每次你进入一些水桶的小批量。 这将减少每个桶内合并的宽度,从而加快阶段2的速度。

使用二叉树,这会将每棵树的深度减少大约log2(num_buckets),从而加快查找速度。 使用Trie,这是多余的( 每个节点使用下一个字符作为基数来对子树进行排序)。 使用DAWG,这实际上会损害您的空间效率,因为您在找不到具有不同启动但后来共享部分的字符串之间的冗余时会失败。

如果有少数不经常接触的桶继续增长,这有可能表现不佳,但通常不会成为最大的桶。 它们可以占用总内存的很大一部分,从常用的桶中进行小批量生产。 您可以实现更智能的逐出算法,该算法记录最后清空存储桶(字典)的时间。 铲斗的NeedsEmptying得分类似于尺寸和年龄的产品。 或者也许是一些年龄函数,比如sqrt(年龄)。 记录自上次清空以来每个桶找到多少重复项的一些方法也是有用的。 如果您在输入流中的某个位置,其中一个存储桶有很多重复,那么您要做的最后一件事就是经常清空它。 也许每当你在一个桶中找到一个副本时,增加一个计数器。 看看年龄与重复发现的比率。 当它们的尺寸开始蠕动时,坐在那里的低用量铲斗将RAM从其他铲斗中取出将很容易找到。 即使它们是当前最大的,如果它们发现了很多重复的东西,也可以保留非常有价值的桶。

如果用于跟踪年龄和重复的数据结构是数组结构,则可以使用向量浮点有效地完成(last_emptied[bucket] - current_pos) / (float)dups_found[bucket]除法。 一个整数除法比一个FP除法慢。 一个FP分区与4个FP分区的速度相同,如果你让它们像这样容易,编译器可以自动进行自动矢量化。

铲斗填充之间还有很多工作要做,所以除非你使用大量的铲斗,否则划分会很小。

选择如何斗

通过良好的逐出算法,存储的理想选择将把很少有重复的密钥放在一些桶中,并且在其他桶中具有许多重复的桶。 如果您了解数据中的任何模式,这将是一种利用它的方法。 使用一些大多数低重复的存储桶意味着所有这些唯一键不会将有价值的密钥冲洗到输出批处理中。 一种驱逐算法,根据每个唯一密钥发现的重复数据来查看存储桶的价值,它将自动确定哪些存储桶有价值且值得保留,即使它们的大小正在逐渐增加。

很多方法可以将字符串扩展到存储桶中。 有些将确保存储桶中的每个元素都比每个后续存储桶中的每个元素都要少,因此生成完全排序的输出很容易。 有些人不会,但有其他优势。 在各种选择之间会有权衡,所有选择都依赖于数据:

  • 善于在第一遍中找到大量重复项(例如,通过将高重复模式与低重复模式分开)
  • 在桶之间统一分配批次数(因此在阶段2中没有桶需要大量批次需要多阶段合并),也可能是其他因素。
  • 与数据集上的逐出算法结合使用时会产生不良行为。
  • 产生全局排序输出所需的桶之间合并量。 它的重要性与唯一字符串的总数而不是输入字符串的数量成比例。

我确信聪明的人已经考虑过在我之前敲击字符串的好方法,所以如果第一个字符的明显方法不理想,这可能值得一试。 这种特殊用例(在排除/计算重复项时进行排序)并不典型。 我认为大多数关于排序的工作只考虑保留重复的排序。 所以你可能找不到太多帮助选择一个好的分组算法进行重复计数外部排序。 无论如何,它将取决于数据。

用于分组的一些具体选项是:Radix =前两个字节在一起(仍然组合大写/小写,并组合非字母字符)。 或者Radix =哈希码的第一个字节。 (需要全局合并才能生成有序输出。)或者Radix = (str[0]>>2) << 6 + str[1]>>2 。 即忽略前2个字符的低2位,将[abcd][abcd].*放在一起, [abcd][efgh].*在一起,等等。这也需要在某些集合之间合并排序结果。桶。 例如, daxxx将在第一个桶中,但aexxx将在第二个桶中。 但只有具有相同first-char高位的存储桶才需要相互合并以产生排序的最终输出。

处理分段选择的想法可以提供很好的重复查找但需要在存储桶之间进行合并排序:在编写phase2输出时,将第一个字符作为基数进行存储,以生成所需的排序顺序。 每个phase1存储桶将输出分散到phase2存储桶中,作为全局排序的一部分。 一旦处理了包含以a开头的字符串的所有phase1批处理,就将a phase2-bucket合并到最终输出中并删除这些临时文件。

Radix =前2个字节(组合非字母)将产生28 2 = 784个桶。 使用200MiB的RAM,平均输出文件大小仅为~25.5k。 一次只清空一个桶将使其最小化,并且通常会获得更大的批次,因此这可以起作用。 (你的驱逐算法可能会遇到一个病态的案例,它会使它保留很多大桶,并为新的桶编写一系列小批量。如果你不仔细测试,那么聪明的启发式方法就有危险)。

打包到同一输出文件中的多个批次可能对许多小存储桶最有用。 您将拥有784个输出文件,每个文件包含一系列批次。 希望您的文件系统具有足够的连续可用空间,并且足够智能,以便在散布小写入许多文件时不会出现过于严重的碎片。


合并:

在合并阶段,使用已排序的批次,我们不需要字典。 只需从具有最低值的批次中获取下一行,并在找到它们时组合重复项。

MergeSort通常合并成对,但在进行外部排序(即磁盘 – >磁盘)时 ,通常会有更宽的输入,以避免多次读取和重写输出。 打开25个输入文件以合并到一个输出文件应该没问题。 使用PriorityQueue的库实现(通常实现为堆)从许多排序列表中选择下一个输入元素。 也许添加输入行,字符串作为优先级,计数和输入文件号作为有效负载。

如果您在第一次传递中使用了radix distribute-by-first-character,那么将所有批次合并到最终输出文件中(即使此过程需要多个合并阶段),然后是所有b批次,等等。 需要检查从a桶开始的任何批次与任何其他桶的批次 ,这样可以节省大量的合并工作,尤其是。 如果你的密钥是由第一个字符分配好的。


最大限度地减少对生产服务器的影响:

在合并期间调整磁盘I / O,以避免在磁盘预取生成巨大的I / O队列读取深度时使服务器陷入困境。 限制你的I / O,而不是更窄的合并,可能是一个更好的选择。 如果服务器正忙于正常工作,那么它就是问题。 即使你只是阅读几个文件,也不会做很多大的顺序读取。

在运行时偶尔检查系统负载。 如果它很高,请在再做一些工作并再次检查之前rest1秒。 如果它真的很高,那么在负载平均值下降之前不要再做任何工作(在检查之间rest30秒)。

检查系统内存使用情况,如果生产服务器上的内存不足,请降低批次阈值。 (或者,如果非常紧,请冲洗您的部分批次并睡觉,直到内存压力降低。)

如果临时文件大小是个问题,您可以像updatedb / locate中的frcode那样执行通用前缀压缩,以显着减少排序的字符串列表的文件大小。 可能在批处理中使用区分大小写的排序,但不区分大小写的基数。 因此, a桶中的每个批次都将拥有所有的A ,然后是所有的s。 或者甚至LZ4即时压缩/解压缩它们。 使用hex计数,而不是十进制。 它更短,编码/解码速度更快。

在密钥和计数之间使用不是合法文件名字符的分隔符,例如/ 。 字符串解析可能会占用合并阶段的大量CPU时间,因此值得考虑。 如果您可以在每个文件的输入缓冲区中保留字符串,并将PQueue指向它们,那可能会很好。 (并告诉您哪个输入文件来自一个字符串,而不单独存储。)


性能调整:

如果初始未排序的字符串非常快,那么一个小批量的哈希表适合CPU L3缓存中的字典可能是一个胜利,除非更大的窗口可以包含更大比例的密钥,并找到更多的重复。 这取决于100k文件中典型的重复次数。 在读取时在RAM中构建小的已排序批次,然后将它们合并到磁盘批次中。 这可能比执行大内存快速排序更有效,因为在您最初读取输入之前,您没有随机访问输入。

由于I / O可能是限制,因此不适合CPU数据缓存的大批量可能是一个胜利,可以找到更多的重复项,并且(极大地?)减少了要完成的合并工作量。

It might be convenient to check the hash table size / memory consumption after every chunk of filenames you get from the OS, or after every subdirectory or whatever. As long as you choose a conservative size bound, and you make sure you can’t go for too long without checking, you don’t need to go nuts checking every iteration.


This paper from 1983 examines external merge-sorting eliminating duplicates as they’re encountered, and also suggests duplicate elimination with a hash function and a bitmap. With long input strings, storing MD5 or SHA1 hashes for duplicate-elimination saves a lot of space.

I’m not sure what they had in mind with their bitmap idea. Being collision-resistant enough to be usable without going back to check the original string would require a hash code of too many bits to index a reasonable-size bitmap. (eg MD5 is a 128bit hash).

How do you “merge the group files” in your approach? In worst case every line had a different name template so each group file had 5,000 lines in it and each merge doubles the number of lines until you overflow memory.

Your friend is closer to the answer, those intermediate files need to be sorted so you can read them line by line and merge them to create new files without having to hold them all in memory. This is a well-known problem, it’s an external sort . Once sorted you can count the results.

A jolly good problem.

Considering that you intend to process the results in batches of 5000 , I don’t believe memory optimisations will be of particular importance so we could probably ignore that aspect like a bad Adam Sandler film and move onto the more exciting stuff. Besides, just because some computation uses more RAM does not necessarily imply it’s a bad algorithm. No one ever complained about look-up tables.

However, I do agree computationally the dictionary approach is better because it’s faster . With respect to the alternative, why perform an unnecessary sort even if its quick? The latter, with its “O(m log m)” is ultimately slower than “O(m)”.

The Real Problem?

With RAM out of the equation, the problem is essentially that of computation . Any “performance problem” in the algorithm will arguably be insignificant to the time it takes to traverse the file system in the first place .

That’s arguably where the real challenge will be. A problem for another time perhaps?

EDIT : displayName makes a good point about using Hadoop – quite ideal for concurrent jobs and compute

祝好运!

Your problem is a very good candidate for Map-Reduce . Great news: You don’t need to move from C# to Java (Hadoop) as Map-Reduce is possible in .NET framework!

Through LINQs you have the basic elements of execution in place already for performing Map Reduce in C#. This might be one advantage over going for External Sort though there is no question about the observation behind External Sort. This link has the ‘Hello World!’ of Map-Reduce already implemented in C# using LINQs and should get you started.


If you do move to Java, one of the most comprehensive tutorial about it is here . Google about Hadoop and Map-Reduce and you will get plenty of information and numerous good online video tutorials.

Further, if you wish to move to Java, your requirements of:

  • Sorted results
  • critical RAM usage

will surely be met as they are inbuilt fulfillments you get from a Map-Reduce job in Hadoop.