如何有效地将袜子配对？

昨天我从干净的洗衣店里给袜子配对，发现我做这件事的方式不是很有效。我一直在天真地搜寻-挑选一只袜子，然后“反复”寻找那双袜子。这需要遍历的n / 2 * N

/ 4 = N 2平均/ 8的袜子。

作为计算机科学家，我在想我能做什么？当然会想到进行排序（根据大小/颜色/ …）以实现O（NlogN）解决方案。

不能选择散列或其他非现场解决方案，因为我无法复制袜子（尽管如果可以的话，可能会很好）。

给定一堆n成对的袜子，其中包含2n元素（假设每只袜子都有一对完全匹配的袜子），最好的方法是用对数的额外空间有效地将它们配对在一起？（我相信我可以记住该信息的数量，如果需要的话。）

我希望能从以下几个方面回答这个问题：

已经提出了排序解决方案，但是：我们不需要订单；。

因此就足够了（并且更快）。

这种递归哈希分区实际上是由SQL

Server在需要对大型数据集进行哈希联接或哈希聚合时完成的。它将其构建输入流分配到许多独立的分区中。该方案可线性扩展到任意数量的数据和多个CPU。

如果您可以找到一个

的分发密钥（哈希密钥），而每个存储桶足够小，可以非常快速地进行处理，则不需要递归分区。不幸的是，我认为袜子没有这种特性。

如果每个袜子都有一个称为“ PairID”的整数，则可以根据PairID % 10（最后一位）轻松地将它们分配到10个存储桶中。

我能想到的最好的现实分区是创建一个：一个维是颜色，另一个维是图案。为什么是矩形？因为我们需要O（1）对堆的随机访问。（3D

长方体也可以，但这不是很实际。）

更新：

那么呢？可以让多个人更快地匹配袜子吗？

最简单的并行化策略是让多名工人从输入筐中取出并将袜子放在堆上。这只会如此之大-想象一下有100个人在10堆土地上进行战斗。（表现为手工冲突和人际交流）（请参阅《通用可扩展性法则》！）。这容易造成吗？否，因为每个工人一次只需要访问一堆。只有一个“锁”就不会出现死锁。取决于人类如何协调对堆的访问，可能会出现。他们可能只是使用随机退避就像网卡在物理级别上所做的那样，以确定哪些卡可以独占访问网络线路。如果它适用于NIC，它也应适用于人类。

如果它几乎可以无限扩展。然后，工人可以从输入筐中取出大块的袜子（很少有竞争，因为他们很少这样做），并且在分配袜子时根本不需要同步（因为他们有局部线程堆）。最后，所有工人都需要结合他们的桩组。我相信，如果工人形成一个，可以用O（log（工人数*每个工人的堆数））来完成。

怎么样的元素明显的问题？如文章所述，可以在中解决元素差异性问题O(N)。袜子问题也是O(N)如此（同样，如果只需要一个分配步骤（我提议多个步骤只是因为人类在计算上很差-

如果分配在一个步骤上就足够了md5(color, length, pattern, ...)，即所有属性的））。

显然，没有人能比O(N)这快，所以我们已经达到了。

尽管输出并不完全相同（在一种情况下，只是布尔值。在另一种情况下，是成对的袜子），则渐进复杂度是相同的。