algorithm - 如何有效地从一堆 socks 中配对？

Question

昨天我把洗干净的 socks 放在一起，发现我这样做的方式效率不高。我正在做一个天真的搜索 - 挑选一只 socks 并“迭代”一堆以找到它的一双。这需要平均迭代 n/2 * n/4 = n2/8 个 socks 。

作为一名计算机科学家，我在想我能做什么？排序(根据大小/颜色/...)当然会想到实现 O(NlogN) 解决方案。

散列或其他非就地解决方案不是一种选择，因为我无法复制我的 socks (尽管如果可以的话可能会很好)。

所以，问题基本上是:

给定一堆n双 socks ，内含2n元素(假设每只 socks 正好有一对匹配)，将它们有效配对并最多对数额外空间的最佳方法是什么？ (如果需要，我相信我能记住那么多信息。)

我将感谢解决以下方面的答案:

大量 socks 的通用理论解决方案。

socks 的实际数量并没有那么大，我不相信我和我的配偶有30多双。 (而且很容易区分我的 socks 和她的 socks ；这也可以使用吗？)

是否相当于element distinctness problem ?

Answer 1

排序方案已经提出，但是排序有点太多了 :我们不需要排序； 我们只需要相等组 。

所以 散列 就足够了(而且速度更快)。

对于每种颜色的 socks ， 组成一堆 。遍历输入篮 中的所有 socks 并将它们分配到颜色堆 上。

迭代每堆， 通过其他一些度量 (例如模式)将其分配到第二组堆

递归地应用这个方案 直到你将所有的 socks 分配到 非常小的堆上，你可以立即进行视觉处理

这种递归散列分区实际上是由 SQL Server 完成的，当它需要对庞大的数据集进行散列连接或散列聚合时。它将其构建输入流分发到许多独立的分区中。该方案可线性扩展到任意数量的数据和多个 CPU。

如果您能找到一个分布键(散列键)， 提供了足够的存储桶 ，每个存储桶都足够小，可以非常快速地处理，则您不需要递归分区。不幸的是，我不认为 socks 有这样的属性。

如果每只 socks 都有一个名为“PairID”的整数，则可以根据 PairID % 10(最后一位数字)轻松地将它们分配到 10 个桶中。

我能想到的最好的现实世界分区是创建一个 矩形的桩 :一个维度是颜色，另一个维度是图案。为什么是长方形？因为我们需要 O(1) 随机访问堆。 (3D cuboid 也可以使用，但这不太实用。)

更新:

并行度 怎么样？多人可以更快地匹配 socks 吗？

最简单的并行化策略是让多个 worker 从输入篮中取出 socks 并将 socks 放在堆上。这只会放大这么多 - 想象一下 100 人在 10 堆上战斗。 同步成本 (表现为手部碰撞和人类交流) 破坏效率和加速 (参见 Universal Scalability Law !)。这是否容易出现 死锁 ？不，因为每个 worker 一次只需要访问一堆。只有一个“锁”就不会出现死锁。 Livelocks 可能是可能的，这取决于人类如何协调对桩的访问。他们可能只使用 random backoff 就像网卡在物理层面上那样做，以确定什么卡可以专门访问网络线路。如果它适用于 NICs ，它也应该适用于人类。

如果 每个 worker 都有自己的一组桩 ，它几乎可以无限扩展。然后工作人员可以从输入篮中取出大块 socks (很少有争用，因为他们很少这样做)并且他们在分发 socks 时根本不需要同步(因为他们有线程本地堆)。最后，所有 worker 都需要联合他们的桩组。我相信如果工作人员形成 聚合树 ，则可以在 O(log (worker count * pies per worker)) 中完成。

element distinctness problem 怎么样？正如文章所述，元素差异性问题可以在 O(N) 中解决。这对于 socks 问题也是一样的(也是 O(N) ，如果你只需要一个分发步骤(我提出了多个步骤只是因为人类不擅长计算 - 如果你在 md5(color, length, pattern, ...) 上分发一个步骤就足够了，即所有的 完美散列 属性))。

显然，不能比 O(N) 更快，所以我们已经达到了 最佳下限 。

尽管输出并不完全相同(在一种情况下，只是一个 bool 值。在另一种情况下， socks 对)，渐近复杂性是相同的。