内容来自 DOC https://q.houxu6.top/?s=如何高效地配对一堆袜子？
昨天我在整理干净的衣服时，发现自己配对袜子的方法效率不高。我的做法是简单地搜索——拿起一只袜子，然后按照顺序“迭代”一堆袜子来找到它的配对。平均来说，这需要遍历 n/2 * n/4 = n2/8 的袜子。
作为一名计算机科学家，我开始思考我能做什么？当然，排序（根据尺寸、颜色等）就出现在我的脑海里，以实现O(NlogN)的解决方案。
哈希或其他非原地解决方案不在我的考虑范围内，因为我无法复制我的袜子（尽管如果可以的话会很有用）。
所以，问题基本上是：
给定一堆n双袜子，包含2n个元素（假设每只袜子都有唯一一对匹配的袜子），如何高效地配对它们，最多需要对数级额外空间？（我相信如果我需要记住这个数量的信息，我是可以做到的。）
我希望回答以下方面的问题：
- 对于大量袜子的一般性 理论 解决方案。
- 实际的袜子数量并不多，我相信我和我的配偶不会超过30双。这是否可以用于区分我的袜子和她的袜子？
- 它是否等同于元素差异问题?
排序方案已经被提出，但排序有点过多了：我们不需要顺序；我们只需要相等的组。
因此，哈希就足够了（而且更快）。
- 对于每种颜色的袜子，形成一个堆。遍历输入篮子中的所有袜子并将其分配到颜色堆中。
- 遍历每个堆并通过某种其他度量（例如图案）将其分配到第二组堆中。
- 递归应用此方案，直到您将所有袜子分发到立即可以视觉处理的非常小的堆中。
实际上，当 SQL Server 需要对大型数据集进行哈希连接或哈希聚合时，它正在执行这种递归哈希分区。它将构建输入流分配到许多独立的独立分区中。该方案线性扩展到任意数量的数据和多个 CPU。
如果您能找到提供足够数量的桶的分配键（哈希键），即每个桶都足够小以非常快速地处理，那么您就不需要递归分区。不幸的是，我认为袜子没有这样的属性。
如果每只袜子都有一个名为“PairID”的整数，那么可以轻松地根据PairID % 10（个位数）将它们分成10个桶。
我认为最好的实际分区是创建一个矩形堆：一个维度是颜色，另一个维度是图案。为什么是矩形？因为我们需要 O(1) 随机访问堆。（3D 长方体 也可以工作，但这不太实用。）
更新：
那么并行性呢？多个人能否更快地匹配袜子？
- 最简单的并行化策略是让多个工作者从输入篮子中取出袜子并将其放在堆中。这只能扩展得这么多 - 想象有100个人争夺10个堆。同步成本（表现为手部碰撞和人类交流）破坏了效率和加速（参见通用可扩展性定律！）。这容易死锁吗？不，因为每个工作者一次只需要访问一个堆。只有一个“锁”，就不可能发生死锁。活锁可能是可能的，具体取决于人类如何协调对堆的访问。他们可能只是使用类似于网络卡在物理层面上确定的随机退避算法来确定哪个网卡可以独占网络线。如果它在 NICs 上有效，那么对人类也应该有效。
- 如果每个工作者都有其自己的一组堆，那么它可以无限扩展。工作者可以从输入篮子中取出大量袜子（由于很少发生争用），并且在分发袜子时根本不需要同步（因为它们具有线程局部堆）。最后，所有工作者都需要联合它们的堆集。我相信，如果工作者形成聚合树，那么可以在 O(log(worker count * piles per worker)) 内完成。
那么关于元素不同问题呢？正如文章所述，元素不同问题可以在 O(N) 内解决。这对于袜子问题也是相同的（同样为 O(N)，如果您只需要一个分布步骤（我提出了多个步骤，只是因为人类在计算方面很糟糕 - 如果您在 md5(color, length, pattern, ...) 上进行分布，即所有属性的完美哈希，那么一个步骤就足够了），也就是说）。
显然，我们无法走得比 O(N) 更快，因此我们已经达到了最佳下界。
尽管输出不完全相同（在一种情况下，只是一个布尔值。在另一种情况下，是袜子对），但它们的渐进复杂度是相同的。