昨天我在整理干净的衣服中的袜子，发现我所做的方法不太高效。 我正在进行一个朴素搜索——选取一只袜子并“迭代”堆以找到它的配对。这需要平均遍历n/2 * n/4 = n2/8只袜子。
作为一名计算机科学家，我在思考我该怎么做？排序（按照大小/颜色/...）当然是想到了实现O(NlogN)解决方案的方法。
哈希或其他非就地解决方案不是选择，因为我无法复制我的袜子（虽然如果我能这样做那会很好）。
所以，问题基本上是：
给定一个包含n对袜子的堆，其中包含2n个元素（假设每只袜子恰好有一个匹配对），使用多达对数额外空间有效地将它们配对的最佳方法是什么？ （如果需要，我相信我可以记住那些信息的数量。）
我将感激回答以下方面的答案：
已经提出了排序方案，但是排序有点过头了：我们不需要顺序；我们只需要相等的组。
因此，哈希就足够了（而且更快）。
当SQL Server需要在巨大数据集上进行哈希连接或哈希聚合时，实际上正在执行这种递归哈希分区。它将其构建输入流分发到许多独立的分区中。该方案可线性地扩展到任意数量的数据和多个 CPU。
你不需要递归分区，如果你能找到一个分布密钥（哈希密钥），它提供了足够的桶，每个桶都足够小，可以非常快速地处理。不幸的是，我认为袜子没有这样的属性。
PairID％10（最后一位）将它们轻松地分配到10个桶中。更新：
并行计算怎么样？多个人可以更快地匹配袜子吗？
关于元素不同性问题呢？正如文章所述，元素不同性问题可以在O(N)时间内解决。对于袜子问题来说也是一样的（如果只需要一个分配步骤，它也是O(N)，我提出多个步骤仅因人类计算能力有限——如果你在md5(color, length, pattern, ...)上进行分配，即所有属性的完美哈希），一个步骤就足够了）。
显然，我们无法比O(N)更快，因此我们已经达到了最优下界。
尽管输出不完全相同（在一个情况下只有一个布尔值，在另一个情况下是袜子的成对），但渐近复杂度是相同的。
由于人脑的结构与现代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);
}
至少这是我在现实生活中使用的，我发现它非常高效。缺点是需要平坦的表面，但通常很丰富。
案例1：所有袜子都是相同的（这就是我在现实生活中做的事情）。
选择任意两只袜子组成一双。常数时间。
案例2：有固定数量的组合（所有权、颜色、大小、纹理等）。
使用基数排序(radix sort)。由于不需要比较，因此仅需线性时间。
案例3：未知组合数（一般情况）。
我们必须进行比较以检查两只袜子是否成对。选择其中一个基于比较的排序算法 O(n log n)。
然而，在现实生活中，当袜子数量相对较小（恒定）时，这些理论上最优的算法可能效果不佳。它甚至可能比顺序搜索更花费时间，尽管在理论上需要二次时间。
非算法性答案，但我这样做时“高效”：
步骤1）丢弃您现有的所有袜子
步骤2）去沃尔玛，按10个一包的数量购买它们-n包白色和m包黑色。日常生活中不需要其他颜色。
然而，有时我不得不再次这样做（丢失袜子，损坏的袜子等），我也不喜欢经常丢弃完好无损的袜子（我希望他们继续销售同样的袜子参考！），所以我最近采取了不同的方法。
算法性答案：
考虑到如果您只为第二堆袜子拿起一只袜子，那么像您这样进行简单搜索找到相匹配的袜子的几率是相当低的。
为什么是五个？通常人类在工作记忆中记住五到七个不同元素时表现良好——有点像RPN栈的人类等价物——五是一个安全的默认值。
从2n-5的堆栈中选择一个。
现在在你画的五个里找一个匹配（视觉模式匹配——人类在小型堆栈上做得很好），如果你没有找到，那么将其添加到你的五个中。
随机从堆栈中选取袜子，并将其与你的5+1双进行比较。随着你的堆栈增长，它会降低你的性能，但提高你的胜算。速度更快。
可以自由地写下计算抽取多少样本才能获得50%匹配率的公式。如果我没记错的话，这是一个超几何定理。
我每天早上都这样做，很少需要超过三次抽取——但我有n双相似的m形白色袜子（大约10双左右）。现在你可以估计我的股票堆栈的大小了 :-)
顺便说一下，我发现每次需要一双袜子时对所有袜子进行排序的交易成本总和远远小于只做一次并绑起袜子。及时制造更好，因为这样你就不必绑袜子了，并且还有边际收益递减（也就是说，你继续寻找那两三只袜子，当它们在洗衣房里或其他地方时，你需要花费时间来匹配袜子）。
我的做法是首先拿起第一只袜子并放下（比如，放在洗衣盆的边缘）。然后我拿起另一只袜子并检查它是否与第一只袜子相同。如果相同，我就把它们都拿走。如果不同，我就把它放在第一只袜子旁边。接着我拿起第三只袜子并将其与前两只（如果它们还在）进行比较，以此类推。
这种方法可以在数组中相对容易地实现，假设“删除”袜子是一种选项。 实际上，您甚至不需要“删除”袜子。如果您不需要对袜子进行排序（参见下文），那么您可以只是移动它们并最终得到一个数组，其中所有袜子都排成一对。
假设袜子唯一的操作是比较相等，那么该算法基本上仍然是一个n2算法，尽管我不知道平均情况（从未学过如何计算）。
当然，排序可以提高效率，特别是在现实生活中，您可以轻松地在两只其他袜子之间“插入”一只袜子。在计算机领域中，可以通过树来实现相同的效果，但需要额外的空间。当然，我们回到了NlogN（如果有几只袜子按排序标准不同但不出自同一对，则会更多）。
除此之外，我想不出其他什么，但这种方法在现实生活中似乎相当有效。 ：）
另一个步骤3的替代方案可能涉及比较逐年以几对更便宜的袜子购买相同数量的成本，并添加分类袜子的成本，但请相信我：批量购买更便宜！此外，存储的袜子价值按股票价格通胀率增加，这比你在许多投资中获得的回报要高。然而，也存在存储成本，但袜子确实不占衣柜顶部多少空间。
问题解决了。所以，只需购买新袜子，扔掉/捐赠旧袜子，每天为你余生节省金钱和时间，从此过上幸福快乐的生活。
理论上最大的时间复杂度是O(n)，因为你需要碰到每只袜子（除非有些已经配对好了）。
你可以用基数排序来实现O(n)的效率。你只需要为桶选择一些属性即可。
如果你能选择有限数量但足以唯一标识每对袜子的属性，那么你应该在O(k*n)内完成，如果我们考虑k是有限的，则为O(n)。
如果您有1000只袜子，8种颜色和平均分布，则可以在c * n时间内制作每个125只袜子的4堆。 如果阈值为5，则您可以在6次运行中对每个堆进行排序。 （计算将袜子扔到正确堆上需要2秒钟，请耗时不到4小时。）
如果您只有60只袜子，3种颜色和2种类型的袜子（你的/你妻子的），则可以在1次运行中对每个10只袜子的堆进行排序。 （再次阈值= 5）。 （计算将袜子扔到正确堆上需要2秒钟，所需时间为2分钟。）
初始桶排序将加速您的过程，因为它在c * n时间内将n只袜子分成k个桶，因此您只需要做c * n * log（k）的工作。 （不考虑阈值）。 因此，总之，您大约需要做n * c *（1 + log（k））的工作，其中c是将袜子扔到堆上的时间。
与任何 c * x * n + O（1）方法相比，此方法将更具优势，前提是log(k) <x-1。
在计算机科学中，这可能会有所帮助：
我们有一个包含 n 个物品的集合，它们有一个顺序（长度）和一个等价关系（额外信息，例如袜子的颜色）。等价关系使我们可以对原始集合进行划分，在每个等价类中，我们的顺序仍然保持不变。将物品映射到其等价类可以在 O(1) 内完成，因此只需要 O(n) 就可以将每个项分配到类中。现在我们已经使用了额外的信息，并且可以以任何方式继续排序每个类。优点是数据集已经显着变小。如果我们有多个等价关系，该方法也可以嵌套->在每个堆中按颜色划分，然后按纹理排序，再按长度排序。任何创建具有大约相同大小的2个以上元素的分区的等价关系都将比排序带来速度提高（前提是我们可以直接将一只袜子分配到它的堆中），并且在较小的数据集上可以快速进行排序。
你正在试图解决错误的问题。
解决方案1：每次将脏袜子放入洗衣篮中，都打一个小结。这样洗衣后就不需要额外分类了。可以将其视为在Mongo数据库中注册索引。事先付出一些工作量以节省未来一些CPU开销。
解决方案2：如果是冬天，你不必穿配对的袜子。我们是程序员，只要它起作用，没人需要知道。
解决方案3：分散工作。你希望以异步方式执行这种复杂的CPU处理，而不会阻塞用户界面。把那堆袜子塞进一个袋子里。只有在需要时才寻找一双袜子。这样所需的工作量就少得多。
希望能对你有所帮助！
Let N be the set of socks that are still unpaired, initially empty
for each sock s taken from the dryer
if s matches a sock t in N
remove t from N, bundle s and t together, and throw them in the basket
else
add s to N
s总是会产生其配对袜子t的记忆，包括足够的信息（在熨衣板上的位置），以便在常数时间内定位t。具有摄影记忆的人可以始终在常数时间内完成1和2。所以，“最佳”的算法取决于运行它的生物硬件/软件的特性和我们愿意通过对成对数据施加完全顺序来“作弊”的意愿。当然，“最佳”元-算法是雇用世界上最好的袜子分类器：一个能够获得并快速存储大量袜子属性集N的人或机器，与常数时间查找、插入和删除的1-1关联内存。这样的人或机器都可以采购到。如果你有这样的一个，你可以在O（N）时间内配对所有的袜子，对于N对来说这是最优的。总序标签允许您使用标准哈希来得到相同的结果，无论是使用人还是硬件计算机。
waitpid函数，这样作为父进程，你甚至不需要亲自整理任何袜子？ - Mxyk