在关键服务器（数十亿个文件名）上，对字符串进行内存受限的外部排序，合并并计算重复项
Memory-constrained external sorting of strings, with duplicates combined&counted, on a critical server (billions of filenames)
我们的服务器在其日志文件夹中生成类似 {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)，space 复杂度 O(m).
我的朋友建议对名称模板进行排序，然后计算一遍中出现的次数，因为现在同名模板都在一起了。时间复杂度 O(m log m)，space 复杂度 O(m).
我们不能互相说服。你们看到这两种方法有什么问题吗？
一个很好的问题。
考虑到您打算分批处理 5000 个结果，我认为 内存优化 不会特别重要所以我们可能会像 Adam Sandler 电影一样忽略那个方面，然后转向更令人兴奋的东西。此外，仅仅因为某些计算使用更多 RAM 并不一定意味着它是一个糟糕的算法。没有人抱怨 查找 表格。
但是，我同意计算 字典方法更好，因为它更快。关于备选方案，为什么执行不必要的排序，即使它很快？后者的 "O(m log m)" 最终比 "O(m)".
慢
真正的问题？
不考虑 RAM，问题本质上是计算。算法中的任何 "performance problem" 可以说是 无关紧要 到 首先遍历文件系统所花费的时间 。
这可以说是真正的挑战所在。也许下次再遇到问题？
编辑：displayName 很好地说明了使用 Hadoop - 非常适合并发作业和计算
祝你好运！
您的问题非常适合 Map-Reduce。好消息：您不需要 从 C# 迁移到 Java (Hadoop)，因为 Map-Reduce is possible in .NET framework!
通过 LINQ，您已经具备了在 C# 中执行 Map Reduce 的基本执行元素。这可能是优于外部排序的一个优势，尽管对外部排序背后的观察毫无疑问。 This link 已经使用 LINQ 在 C# 中实现了 Map-Reduce 'Hello World!'，应该可以帮助您入门。
如果您转到 Java，最全面的教程之一是 here。 Google 关于 Hadoop 和 Map-Reduce，您将获得大量信息和大量优秀的在线视频教程。
此外，如果您想搬到 Java，您的要求是：
- 排序结果
- 严重的 RAM 使用率
肯定会满足，因为它们是您从 Hadoop 中的 Map-Reduce 作业中获得的内置实现。
您"merge the group files"的方法如何？在最坏的情况下，每一行都有不同的名称模板，因此每个组文件中有 5,000 行，每次合并都会使行数加倍，直到内存溢出。
您的朋友更接近答案，需要对这些中间文件进行排序，以便您可以逐行读取它们并合并它们以创建新文件，而不必将它们全部保存在内存中。这是一个众所周知的问题，是 external sort。排序后，您可以计算结果。
IDK 如果已研究 count-merging 重复项的外部排序。我确实找到了一篇 1983 年的论文（见下文）。通常，排序算法的设计和研究都是假设按键对对象进行排序，因此重复的键具有不同的对象。可能有一些关于此的现有文献，但这是一个非常有趣的问题。可能它只是被认为是紧凑型词典与外部 merge-sorting.
相结合的应用程序
用于在小内存中存储大量字符串的高效字典是一个经过深入研究的问题。大多数有用的数据结构都可以包含每个单词的辅助数据（在我们的例子中是重复计数）。
TL:DR 有用想法的摘要，因为我在这个答案的主体中对许多事情的细节过多地漫谈：
当您的字典大小达到阈值时的批次边界，而不是在固定数量的输入文件之后。如果一组 5000 个字符串中有很多重复项，您仍然不会使用太多内存。您可以通过这种方式在第一遍中找到更多重复项。
排序的批次使合并快得多。您可以而且应该合并 many->one 而不是二进制合并。使用 PriorityQueue 确定哪个输入文件包含您接下来应该使用的行。
为了避免在散列 table 中对键进行排序时内存使用量激增，请使用可以对键进行 in-order 遍历的字典。 （即即时排序。）有 SortedDictionary<TKey, TValue>（二进制 tree-based）。这也交织了 CPU 排序的用法与 I/O 等待获取输入字符串。
Radix-sort 每批按 first-character 输出（a-z，non-alphabetic 排序在 A 之前，non-alphabetic 排序在 z 之后）。或者其他一些可以很好地分配密钥的分桶选择。为每个基数桶使用单独的字典，当你达到内存上限时，只将最大的一个清空到一个批次中。 （比 "biggest" 更高级的驱逐启发式可能值得。）
throttle I/O（尤其是合并时），并检查系统 CPU 负载和内存压力。相应地调整行为以确保您不会在服务器最繁忙时造成影响。
对于以 CPU 时间为代价的较小的临时文件，使用 common-prefix 编码，或者可能是 lz4.
A space-efficient 字典将允许更大的批量大小（因此更大的 duplicate-finding window）用于相同的内存上限。 Trie (or better, Radix Trie) might be ideal, because it stores the characters within the tree nodes, with common prefixes only stored once. Directed Acyclic Word Graphs 甚至更紧凑（在不是前缀的公共子串之间找到冗余）。使用一个作为字典是棘手的，但可能是可行的（见下文）。
利用您不需要删除任何树节点或字符串这一事实，直到您要清空整个字典。使用一个可增长的节点数组，以及另一个可增长的字符数组，将字符串从头到尾打包。 （对于 Radix Trie（multi-char 个节点）很有用，但不是每个节点都是单个字符的常规 Trie。）
根据重复项的分布方式，您可能会或可能无法在第一遍中找到很多。这有一些影响，但并没有真正改变你最终合并的方式。
我假设您心中有一些目录遍历的想法，它可以有效地为您的代码提供要唯一化和计数的字符串流。所以我只说"strings"或"keys"，来谈谈输入。
Trim 尽可能多地删除不必要的字符（例如，如果它们都是 .xml，则丢失 .xml）。
在单独的机器上完成 CPU/memory 密集型工作可能会很有用，具体取决于您拥有哪些其他硬件，这些硬件与您的关键生产服务器具有快速网络连接。
您可以 运行 服务器上的一个简单程序，它通过 TCP 连接将文件名发送到另一台计算机上的程序 运行ning，这样可以安全地使用更多内存。服务器上的程序仍然可以进行小批量字典处理，并将它们存储在远程文件系统中。
现在，由于 none 的其他答案确实将所有部分放在一起，这里是我的实际答案：
内存使用的上限很容易。编写您的程序以使用恒定的内存上限，而不管输入大小。更大的输入将导致更多的合并阶段，而不是任何时候更多的内存使用。
临时文件存储的最佳估计 space 您可以在不查看输入的情况下进行 非常 保守的上限，假设每个输入字符串都是唯一的。您需要一些方法来估计将有多少个输入字符串。 （大多数文件系统知道它们包含多少个单独的文件，而无需遍历目录树并计算它们。）
您可以对重复项的分布做出一些假设以做出更好的猜测。
如果暂存文件的数量而不是大小是个问题，您可以将多个批次一个接一个地存储在同一个输出文件中。将 length-headers 放在每个的开头以允许按批次向前跳过，或者将字节偏移量写入单独的数据流。如果大小也很重要，请参阅我关于使用 frcode-style common-prefix 压缩的段落。
正如 Ian Mercer 在他的回答中指出的那样，对批次进行排序将使它们的合并更加高效。如果你不这样做，你要么冒着撞墙的风险，让你的算法无法取得进展，要么你需要做一些事情，比如加载一批，扫描另一批以查找第一批中的条目，然后重写第二批只删除了 potentially-few 个匹配条目。
不对您的批次进行排序会使第一遍的时间复杂度为 O(N)，但要么您必须在稍后的某个时间点进行排序，要么您的后期阶段有一个 worst-case 界限，这会变得更糟。您希望对输出进行全局排序，因此除了 RadixSort 方法之外，无法避免某处的 O(N log N)。
由于批处理大小有限，预计合并步骤为 O(log N)，因此您的原始分析忽略了在写入第 1 阶段批处理后需要发生的事情，从而错过了方法的 O(N log N) 复杂性。
适当的设计选择会发生很大变化，具体取决于我们的内存上限是否足够大以在一批中找到许多重复项。如果即使像 Trie 这样复杂的紧凑数据结构也无济于事，那么将数据放入 Trie 中并再次将其取出来写入批处理是浪费 CPU 时间。
如果您无论如何不能在每个批次中做很多 duplicate-elimination，那么您需要优化以将 possibly-matching 键放在一起以供下一阶段使用。您的第一阶段可以将输入字符串按第一个字节分组，分成 up-to 252 个左右的输出文件（并非所有 256 个值都是合法的文件名字符），或者分成 27 个左右的输出文件（字母 + 杂项），或者 26+26 +1 upper/lower 案例 + non-alphabetic。临时文件可以省略每个字符串的公共前缀。
那么这些第一阶段批次中的大多数应该具有更高的重复密度。实际上，这种将输入分配到输出桶中的基数分布在任何情况下都是有用的，请参见下文。
您仍应按块对 first-stage 输出进行排序，以便为相同的 RAM 提供更宽的下一次传递 dup-find window。
在用完 ~100MiB RAM 或您选择的任何上限之前，我将花更多时间在域上，您可以在初始流中找到有用数量的重复项。
显然，我们将字符串添加到某种字典中以动态查找和计算重复项，同时只需要足够的存储空间来存储唯一字符串集。仅存储字符串然后 然后 对它们进行排序效率会大大降低，因为如果没有 on-the-fly 重复检测，我们会更快地达到 RAM 限制。
为了尽量减少 phase2 的工作，phase1 应该找到并计算尽可能多的重复项，从而减少 p2 数据的总大小。减少 phase2 的合并工作量也很好。 更大的批次有助于解决这两个因素，因此在阶段 1 中尽可能接近内存上限非常有用。当你的内存消耗接近你选择的上限时，不要在输入字符串数量不变后写一个批处理。重复项被计算并丢弃，不占用任何额外存储空间。
准确内存统计的替代方法是跟踪字典中的唯一字符串，这很容易（并且由库实现为您完成）。累积添加的字符串的长度也可以很好地估计用于存储字符串的内存。或者只是对字符串长度分布做出假设。让你的散列 table 最初大小合适，这样它就不必在你添加元素时增长，所以当它满 60%（负载因子）或其他东西时你就停止。
字典的space-efficient 数据结构增加了我们对给定内存限制的dup-finding window。散列 table 的负载因子过高时效率极低，但散列 table 本身只需要存储指向字符串的指针。这是最熟悉的字典，并有一个库实现。
我们知道，一旦我们看到足够多的唯一键，我们就会希望对批处理进行排序，因此使用可以按排序顺序遍历的字典可能是有意义的。 动态排序很有意义，因为键会慢慢进入，因为我们正在从文件系统元数据中读取，所以受磁盘 IO 限制。一个缺点是，如果我们看到的大多数键都是重复的，那么我们将进行大量 O(log batchsize) 查找，而不是大量 O(1) 查找。而且当字典很大时，键更有可能是重复的，因此大多数 O(log batchsize) 查询的批处理大小接近最大值，而不是均匀分布在 0 和最大值之间。一棵树为每次查找支付 O(log n) 的排序开销，无论键是否唯一。散列 table 只在去重后最后支付排序成本。所以对于一棵树来说，它是 O(total_keys * log unique_keys)，hash table 是 O(unique_keys * log unique_keys) 来排序一批。
最大负载因子设置为 0.75 的散列 table 可能非常密集，但在写出批处理之前必须对 KeyValuePair 进行排序可能会阻碍使用标准字典.您不需要字符串的副本，但您可能最终将所有指针（refs）复制到 scratch space 以进行 non-in-place 排序，也许在将它们从哈希中取出时table 排序前。 （或者不仅仅是指针，KeyValuePair，以避免必须返回并查找散列 table 中的每个字符串）。如果大内存消耗的短暂峰值是可以容忍的，并且不会导致您交换/页面到磁盘，那么您可能没问题。如果您可以在哈希 table 使用的缓冲区中进行 in-place 排序，这是可以避免的，但我怀疑 standard-library 容器会发生这种情况。
使用 CPU 的恒定滴流来维护排序的字典，在速度键可用时，可能比 CPU 使用的不频繁的爆发来排序所有批次的键，除了爆发内存消耗。
.NET 标准库有 SortedDictionary<TKey, TValue>，文档说它是用二叉树实现的。我没有检查它是否具有重新平衡功能，或使用 red-black 树来保证 O(log n) 最坏情况下的性能。我不确定它会有多少内存开销。如果这是一个 one-off 任务，那么我绝对推荐使用它来快速轻松地实现它。并且还针对第一个版本进行了更优化的设计以供重复使用。你可能会发现它已经足够好了，除非你能找到一个很好的 Tries 库实现。
memory-efficient 排序字典的数据结构
出字典的内存效率越高，我们在必须写出一批并删除字典之前可以找到的重复项越多。此外，如果它是一个排序的字典，即使找不到重复项，我们的批次也可以越大。
数据结构选择的次要影响是我们在 运行在关键服务器上运行时产生了多少内存流量。排序数组（具有 O(log n) 查找时间（二进制搜索）和 O(n) 插入时间（随机排列元素以腾出空间））将是紧凑的。但是，它不仅速度慢，而且会在很多时候使用 memmove 使内存带宽饱和。 100% CPU 使用这样做对服务器性能的影响比搜索二叉树的 100% CPU 使用更大。在加载当前节点之前，它不知道从哪里加载下一个节点，因此它无法通过管道传输内存请求。树搜索中比较的分支错误预测也有助于适度消耗所有内核共享的内存带宽。 （没错，一些 100%-CPU-usage 的程序比其他程序更糟糕！）
如果清空我们的字典不会在我们清空它时留下内存碎片，那就太好了。不过，树节点的大小将保持不变，因此一堆分散的空洞将可用于未来的树节点分配。但是，如果我们有多个基数桶的单独字典（见下文），与其他字典关联的键字符串可能会与树节点混合在一起。这可能会导致 malloc 难以重用所有释放的内存，可能会增加一些小的实际 OS-visible 内存使用量。 （除非 C# 运行time garbage collection 进行压缩，在这种情况下会处理碎片。）
由于在清空字典并将它们全部删除之前永远不需要删除节点，因此可以将 Tree 节点存储在可增长的数组中。因此内存管理只需要跟踪一个大的分配，与每个节点单独的 malloc 相比减少了簿记开销。左/右子指针可以是数组索引，而不是真正的指针。这让您只能为它们使用 16 或 24 位。 （Heap是另一种存储在数组中的二叉树，但不能作为字典高效使用。它是树，但不是search树） .
存储字典的字符串键通常是将每个字符串作为一个 separately-allocated 对象，并在数组中指向它们。再一次，在准备好将它们全部删除之前，您永远不需要删除、增长甚至修改一个，您可以将它们从头到尾打包在一个 char 数组中，每个数组的末尾都有一个终止符 zero-byte一。这再次节省了大量 book-keeping，并且还可以轻松跟踪键字符串使用了多少内存，让您安全地接近您选择的内存上限。
用于更紧凑存储的 Trie / DAWG
为了更密集地存储一组字符串，我们可以消除存储每个字符串的所有字符的冗余，因为可能有很多共同的前缀。
A Trie stores the strings in the tree structure, giving you common-prefix compression. It can be traversed in sorted order, so it sorts on the fly. Each node has as many children as there are different next-characters in the set, so it's not a binary tree. A C# Trie partial implementation (delete not written) can be found in this SO answer，一个类似于此但不需要批处理/外部排序的问题。
Trie 节点可能需要存储许多子指针，因此每个节点都可能很大。或者每个节点可以是 variable-size，在节点内保存 nextchar:ref 对的列表，如果 C# 允许的话。或者如维基百科文章所说，节点实际上可以是 linked-list 或二叉搜索树，以避免在子节点很少的节点中浪费 space。 （树的较低级别会有很多。）End-of-word 需要标记/节点来区分不是单独的字典条目的子字符串和那些是的子字符串。我们的计数字段可以达到这个目的。 Count=0 表示此处结尾的子字符串不在字典中。 count>=0 表示是。
更紧凑的 Trie 是 Radix Tree, or PATRICIA Tree，每个节点存储多个字符。
这个想法的另一个扩展是 Deterministic acyclic finite state automaton (DAFSA), sometimes called a Directed Acyclic Word Graph (DAWG), but note that the DAWG wikipedia article 是关于同名的不同事物。我不确定是否可以按排序顺序遍历 DAWG 以在最后取出所有键，并且正如维基百科指出的那样，存储关联数据（如重复计数）需要修改。我也不确定它们是否可以增量构建，但我认为您可以在不压缩的情况下进行查找。新添加的条目将像 Trie 一样存储，直到每 128 个新键的压缩步骤将它们合并到 DAWG 中。 （或者 运行 对于更大的 DAWG，压缩的频率较低，所以你不会做太多，比如当散列必须增长而不是线性增长时，将其大小加倍 table 以摊销昂贵的操作。）
当没有任何分支/收敛时，您可以通过在单个节点中存储多个字符来使 DAWG 更加紧凑。 This page 还提到了 Huffman-coding 压缩 DAWG 的方法，并且有一些其他链接和文章引用。
JohnPaul Adamovsky's DAWG implementation (in C) 看起来不错，并描述了它使用的一些优化。我没有仔细看它是否可以将字符串映射到计数。它经过优化，可以将所有节点存储在一个数组中。
This answer to the dup-count words in 1TB of text 问题建议使用 DAWG，并且有几个链接，但我不确定它有多大用处。
写入批次：第一个字符的基数
您可以启用 RadixSort，并为每个起始字符保留单独的字典（或 a-z，non-alphabetic 排序在 a 之前，non-alphabetic 排序在 z 之后）。每个字典写出到不同的临时文件。如果您有多个计算节点可用于 MapReduce 方法，这将是将合并工作分配给计算节点的方法。
这允许一个有趣的修改：不是一次写入所有基数桶，只将最大的字典作为一个批次写入。这可以防止每次您将小批量放入某些桶中。这将减少每个桶内合并的宽度，加快 phase2。
对于二叉树，这会将每棵树的深度减少大约 log2(num_buckets)，从而加快查找速度。对于 Trie，这是多余的（each 节点使用下一个字符作为基数来对子树进行排序）。使用 DAWG，这实际上会伤害您的 space-efficiency，因为您无法找到具有不同开头但后来共享部分的字符串之间的冗余。
如果有几个 infrequently-touched 桶持续增长，但通常不会成为最大的桶，这可能会表现不佳。它们可能会耗尽您总内存的很大一部分，从而从 commonly-used 个存储桶中生成小批量。您可以实施更智能的驱逐算法，记录上次清空桶（字典）的时间。桶的 NeedsEmptying 分数类似于大小和年龄的乘积。或者可能是一些年龄函数，比如 sqrt(age)。一些记录每个桶自上次清空以来找到的重复项数量的方法也很有用。如果您在输入流中有一个桶有很多重复的位置，那么您最不想做的就是经常清空它。也许每次你在桶中找到重复项时，增加一个计数器。看看年龄与 dups-found 的比例。 Low-use 坐在那里的桶会从其他桶中带走 RAM，当它们的大小开始逐渐增加时，这样很容易找到。 Really-valuable 如果发现大量重复项，即使桶是当前最大的桶也可能会保留。
如果您找到的用于跟踪年龄和重复项的数据结构是 struct-of-arrays，则可以使用向量浮点有效地完成 (last_emptied[bucket] - current_pos) / (float)dups_found[bucket] 除法。一个整数除法比一个 FP 除法慢。一个 FP 分区的速度与 4 个 FP 分区的速度相同，编译器可以 auto-vectorize 如果你像这样让编译器变得容易的话。
在装满桶之间有很多工作要做，所以除非您使用 很多 个桶，否则除法会是一个小问题。
选择如何存储
有了一个好的驱逐算法，一个理想的分桶选择是将很少有重复的键放在一些桶中，而将有很多重复的桶放在其他桶中。如果您知道数据中的任何模式，这将是一种利用它的方法。拥有一些主要是 low-dup 的桶意味着所有这些唯一键不会将有价值的键冲刷到输出批次中。一种驱逐算法根据每个唯一密钥发现的重复项来查看存储桶的价值，将自动找出哪些存储桶有价值且值得保留，即使它们的大小正在逐渐增加。
有许多 种方法可以将字符串以基数形式放入桶中。有些人会确保桶中的每个元素都比后面每个桶中的每个元素都少，因此生成 fully-sorted 输出很容易。有些不会，但有其他优点。在分桶选择之间会有权衡，所有这些都是 data-dependent:
- 擅长在第一遍中找到大量重复项（例如，通过将 high-dup 模式与 low-dup 模式分开）
- 在桶之间均匀分配批次数量（因此没有桶有大量批次需要在第 2 阶段 multi-stage 合并），可能还有其他因素。
- 与您的数据集上的逐出算法结合使用时会产生不良行为。
- 产生globally-sorted输出所需的between-bucket合并量。这个的重要性与唯一字符串的总数成比例，而不是输入字符串的数量。
我敢肯定，聪明的人已经在我之前想到了存储字符串的好方法，所以如果 by-first-character 的明显方法不理想，这可能值得搜索。这种特殊的 use-case（在 eliminating/counting 重复时排序）并不典型。我认为大多数关于排序的工作只考虑保留重复项的排序。因此，您可能找不到太多有助于为 dup-counting 外部排序选择好的分桶算法的信息。无论如何，它将是 data-dependent.
一些 concrete-options 用于分桶的是： Radix = 前两个字节在一起（仍然组合 upper/lower 大小写，并组合 non-alphabetic 字符）。或者 Radix = 哈希码的第一个字节。 （需要 global-merge 来生成排序输出。）或者 Radix = (str[0]>>2) << 6 + str[1]>>2。即忽略前 2 个字符的低 2 位，将 [abcd][abcd].* 放在一起，[abcd][efgh].* 放在一起，等等。这也需要在一些桶组之间合并排序结果。例如daxxx 将在第一个桶中，但 aexxx 将在第二个桶中。但是只有 first-char high-bits 相同的 bucket 需要相互合并才能产生排序后的最终输出。
一个处理分桶选择的想法，该选择提供了很好的 dup-finding 但在分桶之间需要 merge-sorting：在写入 phase2 输出时，将第一个字符作为基数分桶以产生排序订购你想要的。作为全局排序的一部分，每个 phase1 桶将输出分散到 phase2 桶中。处理完所有可以包含以 a 开头的字符串的阶段 1 批次后，将 a 阶段 2 桶合并到最终输出中并删除这些临时文件。
Radix = 前 2 个字节（结合 non-alphabetic）将构成 282 = 784 个桶。使用 200MiB 的 RAM，平均输出文件大小仅为 ~256k。一次只清空一个桶将是最少的，而且你通常会得到更大的批次，所以这可行。 （你的驱逐算法可能会遇到一个病态案例，让它保留很多大桶，并为新桶编写一系列小批量。如果你不仔细测试，聪明的启发式方法会有危险）。
将多个批次打包到同一个输出文件中可能对许多小桶最有用。你会有例如784 个输出文件，每个文件包含一系列批次。希望你的文件系统有足够的连续空闲 space，并且足够聪明，能够在分散 small-ish 写入许多文件时做好不要碎片太严重的工作。
正在合并：
在合并阶段，对于已排序的批次，我们不需要字典。只需从具有最低的批次中取出下一行，在找到它们时合并重复项。
MergeSort 通常合并对，但是 when doing external sorting (i.e. disk -> disk)，更宽的输入是常见的以避免读取和 re-writing 输出很多次。打开 25 个输入文件并合并到一个输出文件应该没问题。使用 PriorityQueue 的库实现（通常实现为堆）从许多排序列表中选择下一个输入元素。也许添加以字符串为优先级的输入行，并将计数和输入文件编号作为有效负载。
如果你在第一遍中使用了基数分布first-character，然后将所有a批次合并到最终输出文件中（即使这个过程需要多个合并阶段），然后所有 b 批次等 您不需要检查 starts-with-a 存储桶中的任何批次与任何其他存储桶中的批次 ，所以这节省了 lot 的合并工作，特别是。如果您的密钥按第一个字符分布良好。
最大限度地减少对生产服务器的影响：
合并期间限制磁盘 I/O，以避免在磁盘预取生成巨大的 I/O 读取队列深度时让您的服务器瘫痪。限制 I/O，而不是更窄的合并，可能是更好的选择。如果服务器忙于其正常工作，则可能。即使您只读取几个文件，也不会进行大量顺序读取。
运行宁时不时检查系统负载。如果它很高，请先睡 1 秒钟，然后再做一些工作并再次检查。如果它真的很高，在平均负载下降之前不要再做任何工作（检查之间休眠 30 秒）。
还要检查系统内存使用情况，如果生产服务器上的内存紧张，请降低批处理阈值。 （或者，如果真的很紧张，请刷新您的部分批处理并休眠，直到内存压力降低。）
如果 temp-file 大小是个问题，您可以 common-prefix compression like frcode from updatedb/locate 显着减小已排序字符串列表的文件大小。可能在批次中使用 case-sensitive 排序，但使用 case-insensitive 基数。因此 a 桶中的每个批次都将包含所有 A，然后是所有 a。甚至 LZ4 可以即时压缩/解压缩它们。使用十六进制计数，而不是十进制。它比 encode/decode.
更短、更快
在键和计数之间使用不合法的文件名字符分隔符，例如 /。字符串解析可能会在合并阶段占用大量 CPU 时间，因此值得考虑。如果您可以将字符串留在 per-file 输入缓冲区中，然后将您的 PQueue 指向它们，那可能会很好。 （并告诉您字符串来自哪个输入文件，而不单独存储。）
性能调整：
如果初始未排序的字符串非常快地可用，那么具有适合 CPU L3 缓存中的字典的小批量散列 table 可能是一个胜利，除非更大的 window 可以包含更多的键，并找到更多的重复项。这取决于 100k 文件中典型的重复次数。阅读时在 RAM 中构建小的排序批次，然后将它们合并到磁盘批次中。这可能比进行大型 in-memory 快速排序更有效，因为在您最初阅读输入之前，您无法随机访问输入。
由于 I/O 可能是限制，不适合 CPU 的数据缓存的大批量可能是一个胜利，找到更多重复项并（大大？）减少要完成的合并工作量。
在从 OS 获得的每个文件名块之后或在每个子目录或其他任何地方之后检查散列 table 大小/内存消耗可能很方便。只要您选择了一个保守的大小界限，并且确保您不会在不检查的情况下花费太长时间，您就不需要在每次迭代时都进行检查。
This paper from 1983 检查外部 merge-sorting 消除遇到的重复项，还建议使用散列函数和位图消除重复项。对于长输入字符串，存储 duplicate-elimination 的 MD5 或 SHA1 哈希可以节省很多 space.
我不确定他们对位图的想法是什么。 collision-resistant 足以在不返回检查原始字符串的情况下使用将需要太多位的哈希码来索引 reasonable-size 位图。 （例如 MD5 是 128 位散列）。
我们的服务器在其日志文件夹中生成类似 {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)，space 复杂度 O(m).
我的朋友建议对名称模板进行排序，然后计算一遍中出现的次数，因为现在同名模板都在一起了。时间复杂度 O(m log m)，space 复杂度 O(m).
我们不能互相说服。你们看到这两种方法有什么问题吗？
一个很好的问题。
考虑到您打算分批处理 5000 个结果，我认为 内存优化 不会特别重要所以我们可能会像 Adam Sandler 电影一样忽略那个方面，然后转向更令人兴奋的东西。此外，仅仅因为某些计算使用更多 RAM 并不一定意味着它是一个糟糕的算法。没有人抱怨 查找 表格。
但是，我同意计算 字典方法更好，因为它更快。关于备选方案，为什么执行不必要的排序，即使它很快？后者的 "O(m log m)" 最终比 "O(m)".
慢真正的问题？
不考虑 RAM，问题本质上是计算。算法中的任何 "performance problem" 可以说是 无关紧要 到 首先遍历文件系统所花费的时间 。
这可以说是真正的挑战所在。也许下次再遇到问题？
编辑：displayName 很好地说明了使用 Hadoop - 非常适合并发作业和计算
祝你好运！
您的问题非常适合 Map-Reduce。好消息：您不需要 从 C# 迁移到 Java (Hadoop)，因为 Map-Reduce is possible in .NET framework!
通过 LINQ，您已经具备了在 C# 中执行 Map Reduce 的基本执行元素。这可能是优于外部排序的一个优势，尽管对外部排序背后的观察毫无疑问。 This link 已经使用 LINQ 在 C# 中实现了 Map-Reduce 'Hello World!'，应该可以帮助您入门。
如果您转到 Java，最全面的教程之一是 here。 Google 关于 Hadoop 和 Map-Reduce，您将获得大量信息和大量优秀的在线视频教程。
此外，如果您想搬到 Java，您的要求是：
- 排序结果
- 严重的 RAM 使用率
肯定会满足，因为它们是您从 Hadoop 中的 Map-Reduce 作业中获得的内置实现。
您"merge the group files"的方法如何？在最坏的情况下，每一行都有不同的名称模板，因此每个组文件中有 5,000 行，每次合并都会使行数加倍，直到内存溢出。
您的朋友更接近答案，需要对这些中间文件进行排序，以便您可以逐行读取它们并合并它们以创建新文件，而不必将它们全部保存在内存中。这是一个众所周知的问题，是 external sort。排序后，您可以计算结果。
IDK 如果已研究 count-merging 重复项的外部排序。我确实找到了一篇 1983 年的论文（见下文）。通常，排序算法的设计和研究都是假设按键对对象进行排序，因此重复的键具有不同的对象。可能有一些关于此的现有文献，但这是一个非常有趣的问题。可能它只是被认为是紧凑型词典与外部 merge-sorting.
相结合的应用程序用于在小内存中存储大量字符串的高效字典是一个经过深入研究的问题。大多数有用的数据结构都可以包含每个单词的辅助数据（在我们的例子中是重复计数）。
TL:DR 有用想法的摘要，因为我在这个答案的主体中对许多事情的细节过多地漫谈：
当您的字典大小达到阈值时的批次边界，而不是在固定数量的输入文件之后。如果一组 5000 个字符串中有很多重复项，您仍然不会使用太多内存。您可以通过这种方式在第一遍中找到更多重复项。
排序的批次使合并快得多。您可以而且应该合并 many->one 而不是二进制合并。使用 PriorityQueue 确定哪个输入文件包含您接下来应该使用的行。
为了避免在散列 table 中对键进行排序时内存使用量激增，请使用可以对键进行 in-order 遍历的字典。 （即即时排序。）有
SortedDictionary<TKey, TValue>（二进制 tree-based）。这也交织了 CPU 排序的用法与 I/O 等待获取输入字符串。Radix-sort 每批按 first-character 输出（a-z，non-alphabetic 排序在
A之前，non-alphabetic 排序在z之后）。或者其他一些可以很好地分配密钥的分桶选择。为每个基数桶使用单独的字典，当你达到内存上限时，只将最大的一个清空到一个批次中。 （比 "biggest" 更高级的驱逐启发式可能值得。）throttle I/O（尤其是合并时），并检查系统 CPU 负载和内存压力。相应地调整行为以确保您不会在服务器最繁忙时造成影响。
对于以 CPU 时间为代价的较小的临时文件，使用 common-prefix 编码，或者可能是 lz4.
A space-efficient 字典将允许更大的批量大小（因此更大的 duplicate-finding window）用于相同的内存上限。 Trie (or better, Radix Trie) might be ideal, because it stores the characters within the tree nodes, with common prefixes only stored once. Directed Acyclic Word Graphs 甚至更紧凑（在不是前缀的公共子串之间找到冗余）。使用一个作为字典是棘手的，但可能是可行的（见下文）。
利用您不需要删除任何树节点或字符串这一事实，直到您要清空整个字典。使用一个可增长的节点数组，以及另一个可增长的字符数组，将字符串从头到尾打包。 （对于 Radix Trie（multi-char 个节点）很有用，但不是每个节点都是单个字符的常规 Trie。）
根据重复项的分布方式，您可能会或可能无法在第一遍中找到很多。这有一些影响，但并没有真正改变你最终合并的方式。
我假设您心中有一些目录遍历的想法，它可以有效地为您的代码提供要唯一化和计数的字符串流。所以我只说"strings"或"keys"，来谈谈输入。
Trim 尽可能多地删除不必要的字符（例如，如果它们都是 .xml，则丢失 .xml）。
在单独的机器上完成 CPU/memory 密集型工作可能会很有用，具体取决于您拥有哪些其他硬件，这些硬件与您的关键生产服务器具有快速网络连接。
您可以 运行 服务器上的一个简单程序，它通过 TCP 连接将文件名发送到另一台计算机上的程序 运行ning，这样可以安全地使用更多内存。服务器上的程序仍然可以进行小批量字典处理，并将它们存储在远程文件系统中。
现在，由于 none 的其他答案确实将所有部分放在一起，这里是我的实际答案：
内存使用的上限很容易。编写您的程序以使用恒定的内存上限，而不管输入大小。更大的输入将导致更多的合并阶段，而不是任何时候更多的内存使用。
临时文件存储的最佳估计 space 您可以在不查看输入的情况下进行 非常 保守的上限，假设每个输入字符串都是唯一的。您需要一些方法来估计将有多少个输入字符串。 （大多数文件系统知道它们包含多少个单独的文件，而无需遍历目录树并计算它们。）
您可以对重复项的分布做出一些假设以做出更好的猜测。
如果暂存文件的数量而不是大小是个问题，您可以将多个批次一个接一个地存储在同一个输出文件中。将 length-headers 放在每个的开头以允许按批次向前跳过，或者将字节偏移量写入单独的数据流。如果大小也很重要，请参阅我关于使用 frcode-style common-prefix 压缩的段落。
正如 Ian Mercer 在他的回答中指出的那样，对批次进行排序将使它们的合并更加高效。如果你不这样做，你要么冒着撞墙的风险，让你的算法无法取得进展，要么你需要做一些事情，比如加载一批，扫描另一批以查找第一批中的条目，然后重写第二批只删除了 potentially-few 个匹配条目。
不对您的批次进行排序会使第一遍的时间复杂度为 O(N)，但要么您必须在稍后的某个时间点进行排序，要么您的后期阶段有一个 worst-case 界限，这会变得更糟。您希望对输出进行全局排序，因此除了 RadixSort 方法之外，无法避免某处的 O(N log N)。
由于批处理大小有限，预计合并步骤为 O(log N)，因此您的原始分析忽略了在写入第 1 阶段批处理后需要发生的事情，从而错过了方法的 O(N log N) 复杂性。
适当的设计选择会发生很大变化，具体取决于我们的内存上限是否足够大以在一批中找到许多重复项。如果即使像 Trie 这样复杂的紧凑数据结构也无济于事，那么将数据放入 Trie 中并再次将其取出来写入批处理是浪费 CPU 时间。
如果您无论如何不能在每个批次中做很多 duplicate-elimination，那么您需要优化以将 possibly-matching 键放在一起以供下一阶段使用。您的第一阶段可以将输入字符串按第一个字节分组，分成 up-to 252 个左右的输出文件（并非所有 256 个值都是合法的文件名字符），或者分成 27 个左右的输出文件（字母 + 杂项），或者 26+26 +1 upper/lower 案例 + non-alphabetic。临时文件可以省略每个字符串的公共前缀。
那么这些第一阶段批次中的大多数应该具有更高的重复密度。实际上，这种将输入分配到输出桶中的基数分布在任何情况下都是有用的，请参见下文。
您仍应按块对 first-stage 输出进行排序，以便为相同的 RAM 提供更宽的下一次传递 dup-find window。
在用完 ~100MiB RAM 或您选择的任何上限之前，我将花更多时间在域上，您可以在初始流中找到有用数量的重复项。
显然，我们将字符串添加到某种字典中以动态查找和计算重复项，同时只需要足够的存储空间来存储唯一字符串集。仅存储字符串然后 然后 对它们进行排序效率会大大降低，因为如果没有 on-the-fly 重复检测，我们会更快地达到 RAM 限制。
为了尽量减少 phase2 的工作，phase1 应该找到并计算尽可能多的重复项，从而减少 p2 数据的总大小。减少 phase2 的合并工作量也很好。 更大的批次有助于解决这两个因素，因此在阶段 1 中尽可能接近内存上限非常有用。当你的内存消耗接近你选择的上限时，不要在输入字符串数量不变后写一个批处理。重复项被计算并丢弃，不占用任何额外存储空间。
准确内存统计的替代方法是跟踪字典中的唯一字符串，这很容易（并且由库实现为您完成）。累积添加的字符串的长度也可以很好地估计用于存储字符串的内存。或者只是对字符串长度分布做出假设。让你的散列 table 最初大小合适，这样它就不必在你添加元素时增长，所以当它满 60%（负载因子）或其他东西时你就停止。
字典的space-efficient 数据结构增加了我们对给定内存限制的dup-finding window。散列 table 的负载因子过高时效率极低，但散列 table 本身只需要存储指向字符串的指针。这是最熟悉的字典，并有一个库实现。
我们知道，一旦我们看到足够多的唯一键，我们就会希望对批处理进行排序，因此使用可以按排序顺序遍历的字典可能是有意义的。 动态排序很有意义，因为键会慢慢进入，因为我们正在从文件系统元数据中读取，所以受磁盘 IO 限制。一个缺点是，如果我们看到的大多数键都是重复的，那么我们将进行大量 O(log batchsize) 查找，而不是大量 O(1) 查找。而且当字典很大时，键更有可能是重复的，因此大多数 O(log batchsize) 查询的批处理大小接近最大值，而不是均匀分布在 0 和最大值之间。一棵树为每次查找支付 O(log n) 的排序开销，无论键是否唯一。散列 table 只在去重后最后支付排序成本。所以对于一棵树来说，它是 O(total_keys * log unique_keys)，hash table 是 O(unique_keys * log unique_keys) 来排序一批。
最大负载因子设置为 0.75 的散列 table 可能非常密集，但在写出批处理之前必须对 KeyValuePair 进行排序可能会阻碍使用标准字典.您不需要字符串的副本，但您可能最终将所有指针（refs）复制到 scratch space 以进行 non-in-place 排序，也许在将它们从哈希中取出时table 排序前。 （或者不仅仅是指针，KeyValuePair，以避免必须返回并查找散列 table 中的每个字符串）。如果大内存消耗的短暂峰值是可以容忍的，并且不会导致您交换/页面到磁盘，那么您可能没问题。如果您可以在哈希 table 使用的缓冲区中进行 in-place 排序，这是可以避免的，但我怀疑 standard-library 容器会发生这种情况。
使用 CPU 的恒定滴流来维护排序的字典，在速度键可用时，可能比 CPU 使用的不频繁的爆发来排序所有批次的键，除了爆发内存消耗。
.NET 标准库有 SortedDictionary<TKey, TValue>，文档说它是用二叉树实现的。我没有检查它是否具有重新平衡功能，或使用 red-black 树来保证 O(log n) 最坏情况下的性能。我不确定它会有多少内存开销。如果这是一个 one-off 任务，那么我绝对推荐使用它来快速轻松地实现它。并且还针对第一个版本进行了更优化的设计以供重复使用。你可能会发现它已经足够好了，除非你能找到一个很好的 Tries 库实现。
memory-efficient 排序字典的数据结构
出字典的内存效率越高，我们在必须写出一批并删除字典之前可以找到的重复项越多。此外，如果它是一个排序的字典，即使找不到重复项，我们的批次也可以越大。
数据结构选择的次要影响是我们在 运行在关键服务器上运行时产生了多少内存流量。排序数组（具有 O(log n) 查找时间（二进制搜索）和 O(n) 插入时间（随机排列元素以腾出空间））将是紧凑的。但是，它不仅速度慢，而且会在很多时候使用 memmove 使内存带宽饱和。 100% CPU 使用这样做对服务器性能的影响比搜索二叉树的 100% CPU 使用更大。在加载当前节点之前，它不知道从哪里加载下一个节点，因此它无法通过管道传输内存请求。树搜索中比较的分支错误预测也有助于适度消耗所有内核共享的内存带宽。 （没错，一些 100%-CPU-usage 的程序比其他程序更糟糕！）
如果清空我们的字典不会在我们清空它时留下内存碎片，那就太好了。不过，树节点的大小将保持不变，因此一堆分散的空洞将可用于未来的树节点分配。但是，如果我们有多个基数桶的单独字典（见下文），与其他字典关联的键字符串可能会与树节点混合在一起。这可能会导致 malloc 难以重用所有释放的内存，可能会增加一些小的实际 OS-visible 内存使用量。 （除非 C# 运行time garbage collection 进行压缩，在这种情况下会处理碎片。）
由于在清空字典并将它们全部删除之前永远不需要删除节点，因此可以将 Tree 节点存储在可增长的数组中。因此内存管理只需要跟踪一个大的分配，与每个节点单独的 malloc 相比减少了簿记开销。左/右子指针可以是数组索引，而不是真正的指针。这让您只能为它们使用 16 或 24 位。 （Heap是另一种存储在数组中的二叉树，但不能作为字典高效使用。它是树，但不是search树） .
存储字典的字符串键通常是将每个字符串作为一个 separately-allocated 对象，并在数组中指向它们。再一次，在准备好将它们全部删除之前，您永远不需要删除、增长甚至修改一个，您可以将它们从头到尾打包在一个 char 数组中，每个数组的末尾都有一个终止符 zero-byte一。这再次节省了大量 book-keeping，并且还可以轻松跟踪键字符串使用了多少内存，让您安全地接近您选择的内存上限。
用于更紧凑存储的 Trie / DAWG
为了更密集地存储一组字符串，我们可以消除存储每个字符串的所有字符的冗余，因为可能有很多共同的前缀。
A Trie stores the strings in the tree structure, giving you common-prefix compression. It can be traversed in sorted order, so it sorts on the fly. Each node has as many children as there are different next-characters in the set, so it's not a binary tree. A C# Trie partial implementation (delete not written) can be found in this SO answer，一个类似于此但不需要批处理/外部排序的问题。
Trie 节点可能需要存储许多子指针，因此每个节点都可能很大。或者每个节点可以是 variable-size，在节点内保存 nextchar:ref 对的列表，如果 C# 允许的话。或者如维基百科文章所说，节点实际上可以是 linked-list 或二叉搜索树，以避免在子节点很少的节点中浪费 space。 （树的较低级别会有很多。）End-of-word 需要标记/节点来区分不是单独的字典条目的子字符串和那些是的子字符串。我们的计数字段可以达到这个目的。 Count=0 表示此处结尾的子字符串不在字典中。 count>=0 表示是。
更紧凑的 Trie 是 Radix Tree, or PATRICIA Tree，每个节点存储多个字符。
这个想法的另一个扩展是 Deterministic acyclic finite state automaton (DAFSA), sometimes called a Directed Acyclic Word Graph (DAWG), but note that the DAWG wikipedia article 是关于同名的不同事物。我不确定是否可以按排序顺序遍历 DAWG 以在最后取出所有键，并且正如维基百科指出的那样，存储关联数据（如重复计数）需要修改。我也不确定它们是否可以增量构建，但我认为您可以在不压缩的情况下进行查找。新添加的条目将像 Trie 一样存储，直到每 128 个新键的压缩步骤将它们合并到 DAWG 中。 （或者 运行 对于更大的 DAWG，压缩的频率较低，所以你不会做太多，比如当散列必须增长而不是线性增长时，将其大小加倍 table 以摊销昂贵的操作。）
当没有任何分支/收敛时，您可以通过在单个节点中存储多个字符来使 DAWG 更加紧凑。 This page 还提到了 Huffman-coding 压缩 DAWG 的方法，并且有一些其他链接和文章引用。
JohnPaul Adamovsky's DAWG implementation (in C) 看起来不错，并描述了它使用的一些优化。我没有仔细看它是否可以将字符串映射到计数。它经过优化，可以将所有节点存储在一个数组中。
This answer to the dup-count words in 1TB of text 问题建议使用 DAWG，并且有几个链接，但我不确定它有多大用处。
写入批次：第一个字符的基数
您可以启用 RadixSort，并为每个起始字符保留单独的字典（或 a-z，non-alphabetic 排序在 a 之前，non-alphabetic 排序在 z 之后）。每个字典写出到不同的临时文件。如果您有多个计算节点可用于 MapReduce 方法，这将是将合并工作分配给计算节点的方法。
这允许一个有趣的修改：不是一次写入所有基数桶，只将最大的字典作为一个批次写入。这可以防止每次您将小批量放入某些桶中。这将减少每个桶内合并的宽度，加快 phase2。
对于二叉树，这会将每棵树的深度减少大约 log2(num_buckets)，从而加快查找速度。对于 Trie，这是多余的（each 节点使用下一个字符作为基数来对子树进行排序）。使用 DAWG，这实际上会伤害您的 space-efficiency，因为您无法找到具有不同开头但后来共享部分的字符串之间的冗余。
如果有几个 infrequently-touched 桶持续增长，但通常不会成为最大的桶，这可能会表现不佳。它们可能会耗尽您总内存的很大一部分，从而从 commonly-used 个存储桶中生成小批量。您可以实施更智能的驱逐算法，记录上次清空桶（字典）的时间。桶的 NeedsEmptying 分数类似于大小和年龄的乘积。或者可能是一些年龄函数，比如 sqrt(age)。一些记录每个桶自上次清空以来找到的重复项数量的方法也很有用。如果您在输入流中有一个桶有很多重复的位置，那么您最不想做的就是经常清空它。也许每次你在桶中找到重复项时，增加一个计数器。看看年龄与 dups-found 的比例。 Low-use 坐在那里的桶会从其他桶中带走 RAM，当它们的大小开始逐渐增加时，这样很容易找到。 Really-valuable 如果发现大量重复项，即使桶是当前最大的桶也可能会保留。
如果您找到的用于跟踪年龄和重复项的数据结构是 struct-of-arrays，则可以使用向量浮点有效地完成 (last_emptied[bucket] - current_pos) / (float)dups_found[bucket] 除法。一个整数除法比一个 FP 除法慢。一个 FP 分区的速度与 4 个 FP 分区的速度相同，编译器可以 auto-vectorize 如果你像这样让编译器变得容易的话。
在装满桶之间有很多工作要做，所以除非您使用 很多 个桶，否则除法会是一个小问题。
选择如何存储
有了一个好的驱逐算法，一个理想的分桶选择是将很少有重复的键放在一些桶中，而将有很多重复的桶放在其他桶中。如果您知道数据中的任何模式，这将是一种利用它的方法。拥有一些主要是 low-dup 的桶意味着所有这些唯一键不会将有价值的键冲刷到输出批次中。一种驱逐算法根据每个唯一密钥发现的重复项来查看存储桶的价值，将自动找出哪些存储桶有价值且值得保留，即使它们的大小正在逐渐增加。
有许多 种方法可以将字符串以基数形式放入桶中。有些人会确保桶中的每个元素都比后面每个桶中的每个元素都少，因此生成 fully-sorted 输出很容易。有些不会，但有其他优点。在分桶选择之间会有权衡，所有这些都是 data-dependent:
- 擅长在第一遍中找到大量重复项（例如，通过将 high-dup 模式与 low-dup 模式分开）
- 在桶之间均匀分配批次数量（因此没有桶有大量批次需要在第 2 阶段 multi-stage 合并），可能还有其他因素。
- 与您的数据集上的逐出算法结合使用时会产生不良行为。
- 产生globally-sorted输出所需的between-bucket合并量。这个的重要性与唯一字符串的总数成比例，而不是输入字符串的数量。
我敢肯定，聪明的人已经在我之前想到了存储字符串的好方法，所以如果 by-first-character 的明显方法不理想，这可能值得搜索。这种特殊的 use-case（在 eliminating/counting 重复时排序）并不典型。我认为大多数关于排序的工作只考虑保留重复项的排序。因此，您可能找不到太多有助于为 dup-counting 外部排序选择好的分桶算法的信息。无论如何，它将是 data-dependent.
一些 concrete-options 用于分桶的是： Radix = 前两个字节在一起（仍然组合 upper/lower 大小写，并组合 non-alphabetic 字符）。或者 Radix = 哈希码的第一个字节。 （需要 global-merge 来生成排序输出。）或者 Radix = (str[0]>>2) << 6 + str[1]>>2。即忽略前 2 个字符的低 2 位，将 [abcd][abcd].* 放在一起，[abcd][efgh].* 放在一起，等等。这也需要在一些桶组之间合并排序结果。例如daxxx 将在第一个桶中，但 aexxx 将在第二个桶中。但是只有 first-char high-bits 相同的 bucket 需要相互合并才能产生排序后的最终输出。
一个处理分桶选择的想法，该选择提供了很好的 dup-finding 但在分桶之间需要 merge-sorting：在写入 phase2 输出时，将第一个字符作为基数分桶以产生排序订购你想要的。作为全局排序的一部分，每个 phase1 桶将输出分散到 phase2 桶中。处理完所有可以包含以 a 开头的字符串的阶段 1 批次后，将 a 阶段 2 桶合并到最终输出中并删除这些临时文件。
Radix = 前 2 个字节（结合 non-alphabetic）将构成 282 = 784 个桶。使用 200MiB 的 RAM，平均输出文件大小仅为 ~256k。一次只清空一个桶将是最少的，而且你通常会得到更大的批次，所以这可行。 （你的驱逐算法可能会遇到一个病态案例，让它保留很多大桶，并为新桶编写一系列小批量。如果你不仔细测试，聪明的启发式方法会有危险）。
将多个批次打包到同一个输出文件中可能对许多小桶最有用。你会有例如784 个输出文件，每个文件包含一系列批次。希望你的文件系统有足够的连续空闲 space，并且足够聪明，能够在分散 small-ish 写入许多文件时做好不要碎片太严重的工作。
正在合并：
在合并阶段，对于已排序的批次，我们不需要字典。只需从具有最低的批次中取出下一行，在找到它们时合并重复项。
MergeSort 通常合并对，但是 when doing external sorting (i.e. disk -> disk)，更宽的输入是常见的以避免读取和 re-writing 输出很多次。打开 25 个输入文件并合并到一个输出文件应该没问题。使用 PriorityQueue 的库实现（通常实现为堆）从许多排序列表中选择下一个输入元素。也许添加以字符串为优先级的输入行，并将计数和输入文件编号作为有效负载。
如果你在第一遍中使用了基数分布first-character，然后将所有a批次合并到最终输出文件中（即使这个过程需要多个合并阶段），然后所有 b 批次等 您不需要检查 starts-with-a 存储桶中的任何批次与任何其他存储桶中的批次 ，所以这节省了 lot 的合并工作，特别是。如果您的密钥按第一个字符分布良好。
最大限度地减少对生产服务器的影响：
合并期间限制磁盘 I/O，以避免在磁盘预取生成巨大的 I/O 读取队列深度时让您的服务器瘫痪。限制 I/O，而不是更窄的合并，可能是更好的选择。如果服务器忙于其正常工作，则可能。即使您只读取几个文件，也不会进行大量顺序读取。
运行宁时不时检查系统负载。如果它很高，请先睡 1 秒钟，然后再做一些工作并再次检查。如果它真的很高，在平均负载下降之前不要再做任何工作（检查之间休眠 30 秒）。
还要检查系统内存使用情况，如果生产服务器上的内存紧张，请降低批处理阈值。 （或者，如果真的很紧张，请刷新您的部分批处理并休眠，直到内存压力降低。）
如果 temp-file 大小是个问题，您可以 common-prefix compression like frcode from updatedb/locate 显着减小已排序字符串列表的文件大小。可能在批次中使用 case-sensitive 排序，但使用 case-insensitive 基数。因此 a 桶中的每个批次都将包含所有 A，然后是所有 a。甚至 LZ4 可以即时压缩/解压缩它们。使用十六进制计数，而不是十进制。它比 encode/decode.
在键和计数之间使用不合法的文件名字符分隔符，例如 /。字符串解析可能会在合并阶段占用大量 CPU 时间，因此值得考虑。如果您可以将字符串留在 per-file 输入缓冲区中，然后将您的 PQueue 指向它们，那可能会很好。 （并告诉您字符串来自哪个输入文件，而不单独存储。）
性能调整：
如果初始未排序的字符串非常快地可用，那么具有适合 CPU L3 缓存中的字典的小批量散列 table 可能是一个胜利，除非更大的 window 可以包含更多的键，并找到更多的重复项。这取决于 100k 文件中典型的重复次数。阅读时在 RAM 中构建小的排序批次，然后将它们合并到磁盘批次中。这可能比进行大型 in-memory 快速排序更有效，因为在您最初阅读输入之前，您无法随机访问输入。
由于 I/O 可能是限制，不适合 CPU 的数据缓存的大批量可能是一个胜利，找到更多重复项并（大大？）减少要完成的合并工作量。
在从 OS 获得的每个文件名块之后或在每个子目录或其他任何地方之后检查散列 table 大小/内存消耗可能很方便。只要您选择了一个保守的大小界限，并且确保您不会在不检查的情况下花费太长时间，您就不需要在每次迭代时都进行检查。
This paper from 1983 检查外部 merge-sorting 消除遇到的重复项，还建议使用散列函数和位图消除重复项。对于长输入字符串，存储 duplicate-elimination 的 MD5 或 SHA1 哈希可以节省很多 space.
我不确定他们对位图的想法是什么。 collision-resistant 足以在不返回检查原始字符串的情况下使用将需要太多位的哈希码来索引 reasonable-size 位图。 （例如 MD5 是 128 位散列）。