昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
这是基于比较的模型中的Omega（n log n）下限。（唯一有效的操作是比较两只袜子。）
假设你知道你的2n只袜子是这样排列的：
p1 p2 p3。。。pn pf（1）pf（2）。。。功率因数（n）
其中f是集合{1,2，…，n}的未知排列。知道这一点不会使问题变得更难。有n个！可能的输出（上半部分和下半部分之间的匹配），这意味着您需要log（n！）=Omega（n log n）比较。这可通过分类获得。
由于您对元素区别性问题的连接感兴趣：证明元素区别性的Omega（n log n）界限比较困难，因为输出是二进制的yes/no。这里，输出必须是匹配的，并且可能输出的数量足以获得一个合适的界限。然而，有一个变量与元素的区别有关。假设你有2n只袜子，想知道它们是否可以唯一配对。您可以通过将（a1，a2，…，an）发送到（a1，a1，a2、a2，…、an，an）来获得ED的缩减。（附带地，通过拓扑结构，ED的硬度证明非常有趣。）
我认为，如果只允许等式测试，那么原始问题应该有一个Omega（n2）边界。我的直觉是：考虑一个测试后添加边的图形，并认为如果图形不密集，则输出不是唯一确定的。
其他回答
由于人脑的结构与现代CPU完全不同，所以这个问题毫无实际意义。
人类可以利用“找到匹配的对”这一事实来战胜CPU算法，这对于一个不太大的集合来说是一个操作。
我的算法：
spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
// Thanks to human visual SIMD, this is one, quick operation.
pair = notice_any_matching_pair();
remove_socks_pair_from_surface(pair);
}
至少这是我在现实生活中使用的，我发现它非常有效。缺点是它需要一个平坦的表面，但通常很丰富。
正如许多作者所指出的，基数排序是一种有效的袜子排序方法。尚未提出的是一种完美的哈希方法。用每双袜子买来的时间来计算真是太麻烦了。在你购买袜子时，只需按顺序给袜子编号，就可以让你在整理袜子时把它们放在自己编号的抽屉里。
最多24双袜子的示例。请注意，较大的袜子隔层消除了将袜子卷在一起的需要，这就是所谓的速度/存储权衡。
成本：移动袜子->高，查找/搜索袜子排成一排->小
我们想做的是减少移动次数，并用搜索次数进行补偿。此外，我们还可以利用智人的多威胁环境，在解密缓存中保存更多的东西。
X=您的，Y=您的配偶
从所有袜子的A堆开始：
选择两个袜子，将相应的X袜子放在X线上，将Y袜子放在Y线上的下一个可用位置。
直到A为空。
对于每行X和Y
选择行中的第一只袜子，沿着行搜索，直到找到相应的袜子。放入相应的袜子成品线。可选当您搜索线条时，当前正在查看的袜子与之前的袜子相同，请对这些袜子执行步骤2。
可选地，在第一步中，您从该行中拾取两个袜子，而不是两个，因为缓存内存足够大，我们可以快速识别其中一个袜子是否与您正在观察的行上的当前袜子匹配。如果你有幸拥有三只手臂，那么考虑到受试者的记忆足够大，你可以同时解析三只袜子。
直到X和Y都为空。
Done
然而，由于这与选择排序具有相似的复杂性，由于I/O（移动袜子）和搜索（搜索袜子的行）的速度，所花费的时间要少得多。
理论上的限制是O（n），因为你需要触摸每一只袜子（除非有些袜子已经配对）。
你可以用基数排序实现O（n）。你只需要为桶选择一些属性。
首先你可以选择（她的，我的）-把它们分成两堆，然后使用颜色（可以有任何颜色的顺序，例如按颜色名称的字母顺序）-按颜色将它们分成一堆（记住对同一堆中的所有袜子保持步骤1中的初始顺序），然后袜子的长度，然后是纹理，....
如果您可以选择有限数量的属性，但有足够多的属性可以唯一地标识每对属性，则应该使用O（k*n），如果我们可以考虑k是有限的，则使用O（n）。
排序解决方案已经提出，但排序有点太多了：我们不需要排序；我们只需要平等团体。
所以散列就足够了（而且更快）。
对于每种颜色的袜子，形成一堆。重复输入篮中的所有袜子，并将它们分配到颜色堆上。在每个桩上循环，并通过其他度量（例如模式）将其分配到第二组桩中递归地应用此方案，直到您将所有袜子分发到非常小的堆上，您可以立即进行可视化处理
当SQL Server需要对庞大的数据集进行哈希连接或哈希聚合时，这种递归哈希分区实际上是由它完成的。它将其构建输入流分配到许多独立的分区中。该方案可线性扩展到任意数量的数据和多个CPU。
如果您可以找到一个分发密钥（哈希密钥），该密钥提供足够的存储桶，使得每个存储桶足够小，可以快速处理，那么您就不需要递归分区。不幸的是，我认为袜子没有这种特性。
如果每只袜子都有一个名为“PairID”的整数，那么可以根据PairID%10（最后一位）轻松地将它们分配到10个桶中。
我能想到的现实世界中最好的分区是创建一个堆积的矩形：一个维度是颜色，另一个是图案。为什么是长方形？因为我们需要O（1）随机访问桩。（3D长方体也可以，但这不太实用。）
更新：
并行性呢？多人能更快地匹配袜子吗？
最简单的并行化策略是让多个工人从输入篮中取出袜子，然后将袜子放到堆上。这只会增加这么多——想象100人在10个桩上战斗。同步成本（表现为手部碰撞和人类通信）破坏了效率和加速（参见通用可扩展性定律！）。这是否容易陷入僵局？不，因为每个工人一次只需要访问一堆。只有一个“锁”，就不会出现死锁。活锁可能是可能的，这取决于人类如何协调对桩的访问。他们可能只是使用随机退避，就像网卡在物理级别上那样，以确定什么卡可以独占地访问网络线路。如果它适用于NIC，那么它也应该适用于人类。如果每个工人都有自己的一组桩，它几乎可以无限扩展。然后，工人可以从输入篮中取出大块袜子（很少有人争抢，因为他们很少这样做），而且他们在分发袜子时根本不需要同步（因为他们有线程局部堆）。最后，所有工人都需要联合他们的桩组。我相信，如果工人形成一个聚合树，这可以在O（log（工人计数*每个工人的桩数））中完成。
元素的清晰度问题呢？正如文章所述，元素区别问题可以用O（N）来解决。袜子问题也是如此（如果你只需要一个分发步骤（我提出了多个步骤，只是因为人类不擅长计算-如果你在md5上分发（颜色、长度、图案…），即所有属性的完美哈希），那么一个步骤就够了）。
显然，一个速度不能比O（N）快，所以我们已经达到了最佳下限。
虽然输出不完全相同（在一种情况下，只是布尔值。在另一种情况中，是袜子对），但渐近复杂性是相同的。
