我所做的是拿起第一只袜子，然后把它放下（比如说，在洗衣碗的边缘）。然后我拿起另一只袜子，检查它是否和第一只袜子一样。如果是，我会将它们都删除。如果不是，我把它放在第一只袜子旁边。然后我拿起第三只袜子，把它和前两只袜子进行比较（如果它们还在的话）。等。

这种方法可以很容易地在数组中实现，假设“移除”袜子是一种选择。实际上，您甚至不需要“脱掉”袜子。如果你不需要对袜子进行排序（见下文），那么你可以移动它们，最终得到一个数组，该数组将所有袜子成对排列在数组中。

假设袜子的唯一操作是比较相等性，这个算法基本上仍然是一个 n² 算法，尽管我不知道平均情况（从未学会计算）。

当然，分拣可以提高效率，尤其是在现实生活中，您可以轻松地将袜子“插入”另外两只袜子之间。在计算中，一棵树也可以实现同样的效果，但这是额外的空间。而且，当然，我们又回到了 NlogN（或者更多，如果有几只袜子在排序标准上是相同的，但不是来自同一双袜子）。

除此之外，我想不出任何东西，但这种方法在现实生活中似乎确实非常有效。:)

理论限制是 O（n），因为您需要触摸每只袜子（除非有些袜子已经以某种方式配对）。

您可以使用基数排序实现 O（n）。您只需要为存储桶选择一些属性即可。

1. 首先你可以选择（她的，我的） - 将它们分成 2 堆，
2. 然后使用颜色（可以对颜色进行任何排序，例如按颜色名称的字母顺序） - 按颜色将它们分成一堆（记住保持同一堆中所有袜子的初始顺序 1），
3. 然后是袜子的长度，
4. 然后是纹理， ....

如果你可以选择有限数量的属性，但有足够的属性可以唯一地标识每对，你应该在 O（k * n） 中完成，如果我们可以认为 k 是有限的，那就是 O（n）。

案例1：所有的袜子都是一样的（顺便说一句，这是我在现实生活中所做的）。

选择其中任何两个来制作一对。恒定时间。

情况 2：组合数量恒定（所有权、颜色、大小、质地等）。

使用基数排序。这只是线性时间，因为不需要比较。

情况3：事先不知道组合的数量（一般情况）。

我们必须进行比较以检查两只袜子是否成对。选择一种基于比较的排序算法。O(n log n)

然而，在现实生活中，当袜子的数量相对较少（恒定）时，这些理论上最优的算法将无法很好地工作。它可能比顺序搜索需要更多的时间，理论上需要二次时间。

成本：移动袜子 - >高，在排队中查找/搜索袜子 - >小

我们要做的是减少移动次数，并用搜索次数进行补偿。此外，我们可以利用智人的多重环境在解密缓存中保存更多东西。

X = 你的，Y = 你的配偶

从所有袜子的 A 堆：

选择两只袜子，将相应的 X 袜子放在 X 线中，将 Y 袜子放在下一个可用位置的 Y 线。

直到 A 为空。

对于每行 X 和 Y

1. 选择第一只袜子，沿着这条线搜索，直到找到相应的袜子。

2. 放入相应的成品袜子线。

3. 自选当您搜索该行并且您正在查看的当前袜子与前一个袜子相同时，请对这些袜子执行步骤 2。

第一步（可选）从该行中拿起两只袜子而不是两只袜子，因为缓存内存足够大，我们可以快速确定其中一只袜子是否与您正在观察的行上的当前袜子匹配。如果你有幸拥有三只手臂，你可能会同时解析三只袜子，因为受试者的记忆足够大。

直到 X 和 Y 都为空。

做

然而，由于这与选择排序具有相似的复杂性，因此由于 I/O（移动袜子）和搜索（在生产线上搜索袜子）的速度，所花费的时间要少得多。

每当你拿起袜子时，把它放在一个地方。然后你拿起的下一只袜子，如果它与第一只袜子不匹配，就把它放在第一只袜子旁边。如果是这样，就有一对。这样一来，有多少种组合并不重要，而且你捡到的每只袜子只有两种可能性——要么它有一个匹配项已经在你的袜子阵列中，要么它没有，这意味着你把它添加到数组中的某个位置。

这也意味着你几乎肯定永远不会把所有的袜子都放在阵列中，因为袜子在匹配时会被移除。

已经提出了分拣解决方案，但分拣有点过分了：我们不需要排序;我们只需要平等团体。

因此，散列就足够了（而且更快）。

1. 对于每种颜色的袜子，形成一堆。遍历输入篮中的所有袜子，并将它们分布到颜色堆上。
2. 遍历每个桩，并通过其他指标（例如模式）将其分配到第二组桩中
3. 递归应用此方案，直到您将所有袜子分布到可以立即进行视觉处理的非常小的堆上

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

如果您能找到一个分配键（哈希键），该键提供足够的存储桶，使每个存储桶足够小，可以非常快速地进行处理，则不需要递归分区。不幸的是，我不认为袜子有这样的特性。

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

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

---

更新：

并行性呢？多人可以更快地匹配袜子吗？

1. 最简单的并行化策略是让多个工人从输入篮子中取出袜子，然后将袜子放在堆上。这只会扩大这么多——想象一下 100 个人在 10 个桩上战斗。同步成本（表现为手部碰撞和人为交流）破坏了效率和速度（参见通用可扩展性定律！这容易出现死锁吗？不可以，因为每个工人一次只需要访问一堆。只有一把“锁”，就不会有死锁。Livelocks可能是可能的，这取决于人类如何协调对桩的访问。他们可能只是使用随机回退，就像网卡一样，在物理层面上这样做，以确定哪个卡可以专门访问网络线。如果它适用于 NIC，那么它也应该适用于人类。
2. 如果每个工人都有自己的一组桩，它几乎可以无限扩展。然后，工人可以从输入篮子中取出大块的袜子（很少发生争用，因为他们很少这样做），并且在分配袜子时根本不需要同步（因为它们有线程局部堆）。最后，所有工人都需要将他们的桩组联合起来。我相信如果工人形成一个聚合树，则可以在 O（log（工人计数 * 每个工人的桩数））中完成。

元素独特性问题呢？正如文章所述，元素独特性问题可以在 中求解。这与袜子问题是一样的（同样，如果你只需要一个分布步骤（我提出多个步骤只是因为人类不擅长计算 - 如果你分布在 上，一个步骤就足够了，即所有属性的完美哈希））。O(N)O(N)md5(color, length, pattern, ...)

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

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

非算法答案，但当我这样做时“高效”：

• 第 1 步）丢弃所有现有的袜子

• 第 2 步）去沃尔玛购买 10 - n 包 白色和黑色的 M 包。日常不需要其他颜色 生命。

然而，有时我不得不再次这样做（丢失的袜子，损坏的袜子等），我讨厌经常丢弃完美的袜子（我希望他们继续出售相同的袜子参考！），所以我最近采取了不同的方法。

算法答案：

想想看，如果你只为第二叠袜子抽了一只袜子，就像你所做的那样，你在幼稚的搜索中找到匹配袜子的几率是相当低的。

• 因此，随机挑选其中的五个，并记住它们的形状或长度。

为什么是五个？通常，人类在工作记忆中记住五到七个不同的元素是好的 - 有点像人类相当于一个 RPN 堆栈 - 五个是安全的默认值。

• 从 2n-5 的堆栈中拿起一个。

• 现在在你画的五个中寻找一个匹配（视觉模式匹配 - 人类擅长用一个小堆栈），如果你没有找到一个，那就把它添加到你的五个中。

• 继续从堆栈中随机挑选袜子，并与您的 5+1 袜子进行比较以进行匹配。随着筹码的增长，它会降低您的性能，但会增加您的几率。速度快得多。

随意写下公式，以计算您必须抽取多少样本才能获得 50% 的比赛几率。IIRC：这是一个超几何定律。

我每天早上都这样做，很少需要超过三次抽奖——但我有类似的一双（大约 10 双，给或拿走丢失的）异形白袜子。现在你可以估计我的股票堆的大小：-）nm

顺便说一句，我发现每次需要一双袜子时对所有袜子进行分类的交易成本总和远低于一次并绑定袜子。准时制效果更好，因为这样你就不必束缚袜子了，而且边际回报也会递减（也就是说，你一直在寻找两三只袜子，当在洗衣房的某个地方时，你需要完成你的袜子匹配，你就会浪费时间）。

由于人脑的架构与现代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. 对每堆袜子进行快速分类，并使用袜子的长度进行比较。作为一个人，你可以相当快地决定使用哪种袜子来分区，以避免最坏的情况。（您可以同时看到多只袜子，请利用它来发挥您的优势！
3. 当堆积物达到阈值时停止分类，在这个阈值上，您可以立即找到斑点对和无法配对的袜子

如果你有 1000 只袜子，有 8 种颜色和平均分布，你可以在 c*n 时间内将每 125 只袜子做成 4 堆。阈值为 5 只袜子，您可以在 6 次运行中对每堆袜子进行分类。（算上 2 秒，把袜子扔到右边的一堆上，不到 4 小时。

如果您只有 60 只袜子、3 种颜色和 2 种袜子（您/您妻子的），您可以在 1 次运行中对每堆 10 只袜子进行分类（再次阈值 = 5）。（计算 2 秒，需要 2 分钟）。

最初的桶分类将加快您的过程，因为它会及时将您的 n 只袜子分成 k 个桶，因此您只需要做工作。（不考虑阈值）。所以总而言之，你所做的工作，其中 c 是把袜子扔在一堆东西上的时候。c*nc*n*log(k)n*c*(1 + log(k))

与任何方法相比，这种方法将是有利的，大致与 .c*x*n + O(1)log(k) < x - 1

---

在计算机科学中，这可能会有所帮助： 我们有一个 n 个事物的集合，它们的顺序（长度）和一个等价关系（额外的信息，例如袜子的颜色）。等价关系允许我们对原始集合进行分区，并且在每个等价类中，我们的顺序仍然保持不变。一个事物到它的等价类的映射可以在 O（1） 中完成，所以只需要 O（n） 就可以将每个项目分配给一个类。现在我们已经使用了额外的信息，可以以任何方式对每个类进行排序。优点是数据集已经明显变小了。

如果我们有多个等价关系，该方法也可以嵌套 - >制作颜色堆，而不是在纹理上的每个堆分区内，而不是在长度上排序。任何创建具有 2 个以上大小大小相等的元素的分区的等价关系都将带来比排序更快的速度改进（前提是我们可以直接将袜子分配给它的堆），并且排序可以在较小的数据集上非常快速地发生。

这是基于比较的模型中的 Omega（n log n） 下限。（唯一有效的操作是比较两只袜子。

假设您知道您的 2n 袜子是这样排列的：

第₁ 页 第₂ 页_{第 3} 页 ...p_n p f（1） p_f（2） ...磷_（n）

其中 f 是集合 {1,2,...,n} 的未知排列。知道这一点不会使问题变得更难。有 n！可能的输出（上半场和下半场之间的匹配），这意味着您需要 log（n！） = Omega（n log n） 比较。这可以通过排序获得。

由于您对元素独特性问题的联系感兴趣：证明元素独特性的 Omega（n log n） 绑定更难，因为输出是二进制的 yes/no。在这里，输出必须是匹配的，并且可能的输出数量足以获得一个体面的边界。但是，有一个变体与元素独特性有关。假设您有 2n 只袜子，想知道它们是否可以唯一配对。您可以通过发送 （a 1， a 2， ...， a n） 到 （a 1， a₁， a 2， a₂， ...， a n， _{a n}） 来从 ED 获得减少。（括号内，通过拓扑学证明ED的硬度非常有趣。

我认为，如果您只允许相等性测试，那么应该有一个 Omega（n²） 绑定到原始问题。我的直觉是：考虑一个图，在测试后添加一条边，并争辩说，如果图不密集，则输出不是唯一确定的。

如果你能把一双袜子抽象为键本身，而将另一对袜子抽象为值，我们就可以使用哈希来发挥杠杆作用。

1. 在你身后的地板上做两个假想的部分，一个给你，另一个给你的配偶。

2. 从一堆袜子里拿一个。

3. 现在按照以下规则将袜子一个接一个地放在地板上。

   • 将袜子识别为您或她的袜子，并查看地板上的相关部分。

   • 如果你能在地板上发现这对，把它捡起来打结，或者把它们夹起来，或者在你找到一对后做任何事情，把它放在篮子里（把它从地板上拿下来）。

   • 将其放在相关部分。

4. 重复 3 次，直到所有袜子都从堆中结束。

---

解释：

哈希和抽象

抽象是一个非常强大的概念，已被用于改善用户体验 （UX）。与计算机进行现实交互的抽象示例包括：

• 用于在 GUI（图形用户界面）中导航以访问地址的文件夹图标，而不是键入实际地址以导航到某个位置。
• GUI 滑块用于控制各种级别的音量、文档滚动位置等。

哈希或其他非就地解决方案不是一种选择，因为我无法复制我的袜子（尽管如果可以的话会很好）。

我相信提问者正在考虑应用散列，以便在放置它们之前知道任何一双袜子的插槽。

这就是为什么我建议将放在地板上的一只袜子抽象化为哈希键本身（因此无需复制袜子）。

如何定义我们的哈希键？

如果有不止一双相似的袜子，我们钥匙的以下定义也适用。也就是说，假设有两双黑人男士袜子 PairA 和 PairB，每只袜子都命名为 PairA-L、PairA-R、PairB-L、PairB-R。所以 PairA-L 可以与 PairB-R 配对，但 PairA-L 和 PairB-L 不能配对。

假设任何袜子都可以通过以下方式统一识别，

Attribute[Gender] + Attribute[Colour] + Attribute[Material] + Attribute[Type1] + Attribute[Type2] + Attribute[Left_or_Right]

这是我们的第一个哈希函数。让我们为此使用一个简短的符号。h1（x） 不是我们的位置键。h1(G_C_M_T1_T2_LR)

另一个消除 Left_or_Right 属性的哈希函数是 。第二个函数 h2（x） 是我们的位置键！（对于您身后地板上的空间）。h2(G_C_M_T1_T2)

• 要找到插槽，请使用 h2（G_C_M_T1_T2）。
• 找到插槽后，使用 h1（x） 检查它们的哈希值。如果它们不匹配，则有一对。否则，将袜子扔进同一个插槽中。

注意：由于我们在找到一对后就会删除一对，因此可以安全地假设最多只有一个具有唯一 h2（x） 或 h1（x） 值的插槽。

如果我们每只袜子都有一对匹配的袜子，那么使用 h2（x） 来查找位置，如果没有一对，则需要检查，因为可以安全地假设它们是一对。

为什么把袜子放在地板上很重要

让我们考虑一个场景，袜子堆成一堆（最坏的情况）。这意味着我们别无选择，只能进行线性搜索以找到一对。

将它们铺在地板上可以提高可见度，从而提高发现匹配袜子（匹配哈希键）的机会。 在第 3 步中，当一只袜子放在地板上时，我们的大脑已经下意识地记录了这个位置。 - 因此，如果这个位置在我们的内存中可用，我们可以直接找到匹配的对。 - 如果位置没有被记住，请不要担心，那么我们可以随时恢复为线性搜索。

为什么将这对从地板上移开很重要？

• 人类的短期记忆在需要记住的项目较少时效果最好。从而增加了我们诉诸哈希来发现该货币对的可能性。
• 它还将减少在使用线性搜索对时要搜索的项目数。

分析

1. 情况 1：最坏的情况是 Derpina 无法记住或直接使用散列技术发现地板上的袜子。Derp 对地板上的物品进行线性搜索。这并不比在堆中迭代以找到该货币对更糟糕。
   • 比较上限：O（n^2）。
   • 比较下限：（n/2）。（当 Derpina 捡到的每只袜子都是前一双袜子时）。
2. 案例 2：Derp 记得他放在地板上的每只袜子的位置，每只袜子正好有一双。
   • 比较上限：O（n/2）。
   • 比较下限：O（n/2）。

我说的是比较操作，从一堆袜子中挑选袜子必然是 n 次操作。因此，实际的下限是 n 次迭代和 n/2 次比较。

加快速度

为了获得满分，以便 Derp 获得 O（n/2） 比较，我会推荐 Derpina，

• 花更多的时间在袜子上熟悉它。是的，这也意味着要花更多的时间在Derp的袜子上。
• 玩记忆游戏，比如在网格中发现配对，可以提高短期记忆性能，这可能是非常有益的。

这是否等同于元素独特性问题？

我建议的方法是用于解决元素独特性问题的方法之一，您可以将它们放在哈希表中并进行比较。

鉴于只有一对精确对的特殊情况，它已经变得非常等同于元素不同问题。因为我们甚至可以对袜子进行分类并检查相邻的袜子是否有对（EDP 的另一种解决方案）。

但是，如果给定的袜子可能存在多双袜子，那么它就会偏离 EDP。

这就是我实际的做法，对于 p 双袜子（n = 2p 单只袜子）：

• 从一堆袜子中随机抓起一只袜子。
• 对于第一只袜子，或者如果之前选择的所有袜子都已配对，只需将袜子放入您面前未配对袜子“阵列”的第一个“插槽”中即可。
• 如果您有一个或多个选定的未配对袜子，请根据阵列中所有未配对的袜子检查您当前的袜子。
  • 在构建阵列时，可以将袜子分为一般类别或类型（白色/黑色、脚踝/船员、运动/连衣裙），并“向下钻取”以仅进行比较。
  • 如果找到可接受的匹配项，请将两只袜子放在一起并将它们从阵列中取出。
  • 如果没有，请将当前袜子放入阵列中的第一个空位插槽中。
• 对每只袜子重复。

这个方案的最坏情况是，每双袜子都足够不同，必须完全匹配，并且你选择的前 n/2 只袜子都是不同的。这是您的 O（n²） 场景，而且极不可能。如果独特类型的袜子 t 的数量小于 p = n/2 的对数，并且每种类型的袜子都足够相似（通常与磨损相关），以至于该类型的任何袜子都可以与任何其他袜子配对，那么正如我上面推断的那样，您必须比较的最大袜子数量是 t， 之后，您拉的下一只袜子将与其中一只未配对的袜子相匹配。这种情况在普通袜子抽屉中比最坏情况更有可能发生，并将最坏情况的复杂度降低到 O（n*t），其中通常 t << n。

考虑一个大小为“N”的哈希表。

如果我们假设正态分布，那么将至少一只袜子映射到一个桶的估计“插入”数为 NlogN（即，所有桶都已满）

我把它作为另一个谜题的一部分，但我很乐意被证明是错的。这是我关于同一主题的博客文章

让“N”对应于您拥有的袜子的独特颜色/图案数量的近似上限。

一旦你发生碰撞（又名：比赛），只需脱掉那双袜子。 对下一批 NlogN 袜子重复相同的实验。 它的美妙之处在于，由于人类思维的工作方式，您可以进行 NlogN 并行比较（碰撞分辨率）。:-)

List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();

foreach (Sock newSock in UnsearchedSocks)
{
  Sock MatchedSock = null;
  foreach(Sock UnmatchedSock in UnmatchedSocks)
  {
    if (UnmatchedSock.isPairOf(newSock))
    {
      MatchedSock = UnmatchedSock;
      break;
    }
  }
  if (MatchedSock != null)
  {
    UnmatchedSocks.remove(MatchedSock);
    PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock));
  }
  else
  {
    UnmatchedSocks.Add(NewSock);
  }
}

从您的问题中可以清楚地看出，您在洗衣:)方面没有太多实际经验。您需要一种适用于少量不可配对袜子的算法。

到目前为止，答案并没有很好地利用我们的人类模式识别能力。Set 游戏提供了如何做好这项工作的线索：将所有袜子放在一个二维空间中，这样您既可以很好地识别它们，又可以轻松地用手够到它们。这会将您限制在大约 120 * 80 厘米左右的区域。从那里选择您识别的对并删除它们。将多余的袜子放在空闲空间中并重复。如果你为那些穿着容易识别的袜子的人洗衣服（我想到小孩），你可以先选择这些袜子来做基数排序。只有当单袜数量较少时，此算法才有效

袜子，无论是真实的袜子还是一些类似的数据结构，都会成对提供。

最简单的答案是，在允许将袜子分开之前，应该已经初始化了该对的单个数据结构，其中包含指向左右袜子的指针，从而可以直接或通过它们的对引用袜子。袜子也可以扩展为包含指向其伴侣的指针。

这可以通过抽象层删除任何计算配对问题来解决它。

将同样的想法应用于配对袜子的实际问题，显而易见的答案是：不要让你的袜子不配对。袜子是成对的，成对放在抽屉里（也许是把它们放在一起），成对穿。但是可以取消配对的点是在洗衣机中，因此所需要的只是一个物理机制，可以让袜子保持在一起并有效地洗涤。

有两种物理可能性：

对于一个“配对”对象，它有一个指向每只袜子的指针，我们可以有一个布袋，用来将袜子放在一起。这似乎是巨大的开销。

但是，为了让每只袜子都保持对另一只袜子的引用，有一个巧妙的解决方案：一个弹出器（如果你是美国人，则为“按扣”），例如：

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

然后，你所要做的就是在脱下袜子后立即将袜子扣在一起，并将它们放入洗衣篮中，这样你就消除了需要将袜子配对的问题，并对“配对”概念进行了物理抽象。

这个问题其实很有哲理。从本质上讲，这是关于人们解决问题的能力（我们大脑的“湿软件”）是否等同于算法可以完成的工作。

袜子分类的一个明显算法是：

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

现在这个问题中的计算机科学是关于步骤的

1. “如果 s 与 N 中的袜子 t 配对”。我们能以多快的速度“记住”到目前为止所看到的？
2. “从 N 中删除 t”和“将 s 添加到 N”。跟踪我们目前所看到的情况有多昂贵？

人类将使用各种策略来实现这些目标。人类的记忆是联想的，类似于哈希表，其中存储值的特征集与相应的值本身配对。例如，“红色汽车”的概念映射到一个人能够记住的所有红色汽车。记忆力完美的人拥有完美的映射。大多数人在这方面是不完美的（以及大多数其他人）。关联映射的容量有限。映射可能会在各种情况下消失（一杯啤酒太多），被错误地记录（“我虽然她的名字是贝蒂，而不是内蒂”），或者即使我们观察到事实已经改变，也永远不会被覆盖（“爸爸的车”让人想起“橙色火鸟”，而我们实际上知道他已经把它换成了红色的科迈罗）。

就袜子而言，完美的回忆意味着看着袜子总是会产生其兄弟姐妹的记忆，包括足够的信息（它在熨衣板上的位置）以在恒定的时间内定位。一个有照相记忆的人可以在恒定的时间内完成 1 和 2，而不会失败。stt

记忆力不完美的人可能会根据他能够跟踪的特征使用一些常识等价类：尺寸（爸爸、妈妈、婴儿）、颜色（绿色、红色等）、图案（菱形、素色等）、风格（脚、膝盖高等）。因此，熨衣板将分为类别部分。这通常允许通过内存在恒定时间内定位类别，但随后需要通过类别“桶”进行线性搜索。

完全没有记忆或想象力的人（对不起）只会把袜子放在一堆，然后对整堆袜子进行线性搜索。

一个整洁的怪胎可能会像有人建议的那样使用数字标签来表示对。这为全面排序打开了大门，它允许人类使用与CPU完全相同的算法：二进制搜索，树，哈希等。

因此，“最佳”算法取决于运行它的湿软件/硬件/软件的质量，以及我们通过对对施加总订单来“作弊”的意愿。当然，“最好的”元算法是聘请世界上最好的袜子分拣机：一个人或机器可以获取并快速存储大量 N 个袜子属性集，并将其存储在 1-1 关联存储器中，并具有恒定时间查找、插入和删除。像这样的人和机器都可以采购。如果你有一只袜子，你可以在 O（N） 时间内将所有袜子配对 N 对，这是最佳的。总订单标签允许您使用标准哈希在人机或硬件计算机上获得相同的结果。

我提出了另一种解决方案，它不会承诺更少的操作，也不会减少时间消耗，但应该尝试看看它是否是一种足够好的启发式方法，可以在大量袜子配对中提供更少的时间消耗。

前提 条件：不能保证有相同的袜子。如果它们具有相同的颜色，并不意味着它们具有相同的大小或图案。袜子是随机洗牌的。袜子的数量可能很奇怪（有些不见了，我们不知道有多少）。准备记住变量“index”并将其设置为 0。

结果将有一个或两个桩：1.“匹配”和 2.“失踪”

启发式：

1. 找到最有特色的袜子。
2. 找到匹配项。
3. 如果没有匹配项，请将其放在“缺失”堆上。
4. 从 1 开始重复。直到没有更多最独特的袜子。
5. 如果袜子少于 6 只，请转到 11 只。
6. 盲目地将所有袜子与邻居配对（不要打包）
7. 找到所有匹配的对，打包并将打包的对移动到“匹配”的堆中; 如果没有新的匹配项 - 将“index”递增 1
8. 如果“index”大于 2（这可能取决于 sock 的值 数量，因为袜子数量越多，机会就越少 盲目配对）转到 11
9. 洗牌其余的
10. 转到 1
11. 忘记“索引”
12. 挑选袜子
13. 找到它的对
14. 如果袜子没有一双，请将其移至“丢失”的一堆
15. 如果找到匹配，请配对，打包配对并将其移动到“匹配”堆中
16. 如果还有更多，那么一只袜子就去 12 只
17. 如果只剩下一个，请转到 14
18. 满意的笑容:)

此外，还可以增加对损坏的袜子的检查，就好像去除这些袜子一样。它可以插入 2 到 3 之间，以及 13 到 14 之间。

我期待听到任何经验或更正。

做一些预处理怎么样？我会在每只袜子上缝上一个标记或 ID 号，使每双袜子都有相同的标记/ID 号。每次购买新袜子时，都可能完成此过程。然后，您可以进行基数排序以获得 O（n） 总成本。为每个标记/ID 号找到一个位置，然后一个接一个地挑选所有袜子并将它们放在正确的位置。

为了说明从一堆袜子中配对的效率如何，我们必须首先定义机器，因为配对不是通过图灵还是随机访问机器完成的，而随机访问机器通常用作算法分析的基础。

机器

机器是现实世界中称为人类的元素的抽象。它能够通过一双眼睛从环境中读取。我们的机器模型能够通过使用 2 个手臂来操纵环境。逻辑和算术运算是用我们的大脑计算的（希望;-））。

我们还必须考虑可以使用这些仪器执行的原子操作的内在运行时间。由于物理限制，由手臂或眼睛执行的操作具有非恒定的时间复杂度。这是因为我们不能用胳膊移动一大堆袜子，也不能用眼睛看到一大堆袜子上的最上面的袜子。

然而，机械物理学也给了我们一些好处。我们不限于用胳膊最多移动一只袜子。我们可以一次移动其中的几个。

因此，根据前面的分析，应按降序使用以下操作：

• 逻辑和算术运算
• 环境读数
• 环境改造

我们还可以利用人们只有非常有限的袜子这一事实。因此，环境改造可以涉及堆中的所有袜子。

算法

所以这是我的建议：

1. 将堆中的所有袜子铺在地板上。
2. 通过查看地板上的袜子找到一双。
3. 从 2 开始重复，直到无法配对。
4. 从 1 开始重复，直到地板上没有袜子。

操作 4 是必要的，因为当将袜子铺在地板上时，有些袜子可能会隐藏其他袜子。以下是对算法的分析：

分析

该算法以很高的概率终止。这是因为在步骤 2 中找不到袜子。

对于配对袜子的以下运行时分析，我们假设在步骤 1 之后至少有一半的袜子没有被隐藏。因此，在一般情况下，我们可以找到成对。这意味着循环是步骤 4 的执行次数。步骤 2 是执行次数。因此，我们可以得出结论：n2nn/2O(log n)O(n^2)

• 该算法涉及环境修改（第 1 步加上从地板上捡起每双袜子）O(ln n + n)O(ln n)
• 该算法涉及步骤 2 中的环境读取O(n^2)
• 该算法涉及逻辑和算术运算，用于在步骤 2 中将一只袜子与另一只袜子进行比较O(n^2)

因此，我们的总运行时复杂度为 O（r*n^2 + w*（ln n + n）），其中 和 分别是合理数量的袜子的环境读取和环境写入操作的因素。省略了逻辑和算术运算的成本，因为我们假设需要恒定数量的逻辑和算术运算来决定 2 只袜子是否属于同一对袜子。这可能并非在所有情况下都可行。rw

这是在问错误的问题。正确的问题是，我为什么要花时间整理袜子？当您将空闲时间视为您选择的 X 个货币单位时，每年要花多少钱？

通常情况下，这不仅仅是任何空闲时间，而是早上的空闲时间，你可以在床上度过，或者喝咖啡，或者早点离开，不被堵在交通中。

退后一步，想办法解决问题通常是件好事。

而且有办法！

找一只你喜欢的袜子。考虑所有相关功能：不同照明条件下的颜色、整体质量和耐用性、不同气候条件下的舒适度以及气味吸收。同样重要的是，它们在储存时不应失去弹性，因此天然织物是好的，并且它们应该以塑料包装形式提供。

如果左脚袜和右脚袜没有区别就更好了，但这并不重要。如果袜子是左右对称的，那么找到一双袜子是 O（1） 操作，对袜子进行分类是近似 O（M） 操作，其中 M 是你家里乱扔袜子的地方的数量，理想情况下是一些小的常数。

如果你选择了一双左右袜子不同的花哨的袜子，对左右脚桶进行全桶分类，取 O（N+M），其中 N 是袜子的数量，M 与上面相同。其他人可以给出找到第一对的平均迭代次数的公式，但通过盲搜索找到一对的最坏情况是 N/2+1，对于合理的 N 来说，这在天文数字上不太可能。当使用 Mk1 Eyeball 扫描一堆未分类的袜子时，可以使用先进的图像识别算法和启发式方法来加快速度。

因此，实现 O（1） 袜子配对效率的算法（假设袜子是对称的）是：

1. 你需要估计你的余生需要多少双袜子，或者直到你退休并搬到温暖的气候，不再需要穿袜子。如果你还年轻，你也可以估计我们家里要多久才能拥有袜子分拣机器人，整个问题就变得无关紧要了。

2. 您需要了解如何批量订购所选袜子，以及成本以及它们是否交付。

3. 订购袜子！

4. 扔掉你的旧袜子。

另一种第 3 步将涉及比较多年来一次购买相同数量的可能更便宜的袜子的成本，并添加分类袜子的成本，但请相信我的话：批量购买更便宜！此外，储藏中的袜子会以股价上涨的速度增加价值，这比您在许多投资中获得的要多。话又说回来，还有存储成本，但袜子在壁橱的顶层架子上真的不会占用太多空间。

问题解决了。所以，只要买一双新袜子，扔掉/捐赠你的旧袜子，在知道你在余生中每天都在节省金钱和时间后，就过上幸福的生活。

实际方法：

尽快从未分类的袜子堆中取出一只袜子，并堆放在您面前。绒毛的布置应该在一定程度上节省空间，所有袜子都指向同一个方向;桩的数量受到您可以轻松到达的距离的限制。选择放袜子的堆应该 - 尽可能快 - 将袜子放在一堆明显像袜子的袜子上;偶尔的I型（把袜子放在不属于它的袜子堆上）或II型（当有一堆类似的袜子时，把袜子放在自己的堆里）错误是可以容忍的——最重要的考虑因素是速度。

一旦所有的袜子都堆成一堆，迅速穿过多袜子堆，形成一对并取出它们（这些袜子正走向抽屉）。如果袜子堆中有不匹配的袜子，请将它们重新堆放到最佳状态（在尽可能快的约束范围内）。处理完所有多袜桩后，匹配由于 II 类错误而未配对的剩余可配对袜子。哎呀，你完了——我有很多袜子，直到大部分袜子都脏了才洗。另一个实用的注意事项：我将一双袜子的顶部向下翻转到另一只袜子上，利用它们的弹性特性，这样它们在被运送到抽屉和抽屉时都会保持在一起。

我采取了一些简单的步骤，将我的工作量减少到一个需要 O（1） 时间的过程中。

通过将我的输入减少到两种袜子中的一种（用于娱乐的白袜子，用于工作的黑袜子），我只需要确定我手头有两只袜子中的哪一种。（从技术上讲，由于它们从未一起洗涤，因此我将该过程缩短到 O（0） 时间。

需要一些前期努力来找到理想的袜子，并购买足够的数量以消除对现有袜子的需求。由于我在需要黑袜之前就这样做了，所以我的努力很小，但里程可能会有所不同。

这种前期工作在非常流行和有效的代码中已经多次出现。例子包括将 pi #DEFINE 到几位小数（还有其他例子，但这是现在想到的）。

创建一个哈希表，该表将用于不匹配的袜子，使用模式作为哈希。逐个迭代袜子。如果袜子在哈希表中具有模式匹配，请将袜子从表中取出并制作一对。如果袜子没有匹配，请将其放入表格中。

在我攻读博士学位（计算机科学）期间，我经常想到这一点。我想出了多种解决方案，这取决于区分袜子的能力，从而尽快找到正确的袜子。

假设观察袜子并记住其独特图案的成本可以忽略不计（ε）。那么最好的解决方案就是把所有的袜子都扔在桌子上。这涉及以下步骤：

1. 把所有的袜子都扔到桌子上 （1） 并创建一个哈希图 {pattern： position} （ε）
2. 虽然有剩余的袜子 （n/2）：
   1. 随便捡到一只袜子 （1）
   2. 查找相应袜子的位置 （ε）
   3. 取回袜子 （1） 和商店对

这确实是最快的可能性，并且以 n + 1 = O（n） 复杂度执行。但它假设你完全记住了所有的模式......在实践中，情况并非如此，我个人的经验是，您有时在第一次尝试时找不到匹配的对：

1. 把所有的袜子都扔在桌子上 （1）
2. 虽然有剩余的袜子 （n/2）：
   1. 随便捡到一只袜子 （1）
   2. 未配对时 （1/P）：
      1. 查找具有相似图案的袜子
      2. 拿起袜子并比较两者 （1）
      3. 如果可以，则存储对

现在，这取决于我们找到匹配对的能力。如果您有深色/灰色袜子或白色运动袜，通常具有非常相似的图案，则尤其如此！让我们承认，你有 P 的概率找到相应的袜子。平均而言，您需要尝试 1/P 才能找到相应的袜子以形成一双袜子。总体复杂度为 1 + （n/2） * （1 + 1/P） = O（n）。

两者在袜子数量上都是线性的，并且是非常相似的解决方案。让我们稍微修改一下问题，承认套装中有多双相似的袜子，并且很容易在一次移动中存放多双袜子 （1+ε）。对于 K 种不同的模式，您可以实现：

1. 对于每只袜子 （n）：
   1. 随便捡到一只袜子 （1）
   2. 把它放在其模式的集群上
2. 对于每个集群 （K）：
   1. 取一簇并存放袜子 （1+ε）

总体复杂度变为 n+K = O（n）。它仍然是线性的，但选择正确的算法现在可能很大程度上取决于 P 和 K 的值！但有人可能会再次反对说，您可能很难找到（或创建）每个袜子的集群。

此外，您还可以通过在网站上查看什么是最佳算法并提出自己的解决方案来浪费时间:)

对 n 双袜子进行排序的问题是 O（n）。在你把它们扔进洗衣篮之前，你把左边的穿到右边的。取出它们后，您剪断线并将每对放入抽屉 - 对 n 对 2 次操作，因此 O（n）。

现在的问题是，你是否自己洗衣服，你的妻子做她的衣服。这可能是一个完全不同的问题领域的问题。:)

当我对袜子进行分类时，我会进行近似基数排序，将袜子放在相同颜色/图案类型的其他袜子附近。除非我能在我即将放下袜子的位置/附近看到完全匹配的情况，否则我会在那个点提取这双袜子。

几乎所有其他算法（包括 usr 得分最高的答案）都会对成对进行排序，然后删除。我发现，作为一个人，最好尽量减少一次考虑的袜子数量。

我通过以下方式做到这一点：

1. 挑选一只与众不同的袜子（无论在一堆袜子中首先引起我的注意）。
2. 根据与该位置的相似性，从该概念位置开始基数排序，方法是从堆中拉出袜子。
3. 将新袜子放在当前袜子堆附近，根据袜子的不同程度确定距离。如果您发现自己因为袜子相同而将袜子放在另一只袜子上，请在那里形成一对，然后将它们取下。这意味着将来的比较需要更少的努力来找到正确的位置。

这利用了人类在O（1）时间内进行模糊匹配的能力，这在某种程度上相当于在计算设备上建立哈希图。

通过首先拉出独特的袜子，您可以留出空间来“放大”那些不太独特的特征。

在去除了荧光色、带条纹的袜子和三双长袜子后，您最终可能会得到大部分白色袜子，大致按磨损程度分类。

在某些时候，袜子之间的差异足够小，以至于其他人不会注意到差异，并且不需要任何进一步的匹配工作。

我现在已经完成了袜子的配对，我发现最好的方法是：

• 选择其中一只袜子并将其收起（为那双袜子创建一个“桶”）
• 如果下一个是前一个存储桶的对，则将其放入现有存储桶，否则创建一个新存储桶。

在最坏的情况下，这意味着您将有 n/2 个不同的存储桶，并且您将有 n-2 个关于哪个存储桶包含当前袜子的对。显然，如果您只有几对，此算法效果很好;我用 12 双做到了。

它不是那么科学，但效果很好：）

拿起第一只袜子，放在桌子上。现在再挑一只袜子;如果它与第一个拾取的匹配，则将其放在第一个拾取的顶部。如果没有，请将其放在桌子上，距离第一个不远。挑选第三只袜子;如果它与前两个中的任何一个匹配，请将其放在它们之上，或者将其放置在与第三个相距不远的地方。重复直到你拿起所有的袜子。

我希望我能为这个问题贡献一些新的东西。我注意到，所有的答案都忽略了这样一个事实，即在两点上，你可以在不降低整体洗衣性能的情况下进行预处理。

此外，即使对于大家庭，我们也不需要假设大量的袜子。袜子从抽屉里拿出来穿，然后把它们扔在一个地方（可能是垃圾箱），然后洗干净。虽然我不会称上述垃圾箱为后进先出堆栈，但我想说可以安全地假设

1. 人们把两只袜子大致扔在袜子的同一区域 站
2. 箱在任何时候都不是随机的，因此
3. 从此素材箱顶部获取的任何子集通常都包含两者 一双袜子。

由于我所知道的所有洗衣机的尺寸都是有限的（不管你要洗多少只袜子），而且实际的随机化发生在洗衣机中，无论我们有多少袜子，我们总是有小的子集，几乎没有单例。

我们的两个预处理阶段是“把袜子放在晾衣绳上”和“把袜子从晾衣绳上拿下来”，我们必须这样做，才能得到不仅干净而且干燥的袜子。与洗衣机一样，晾衣绳是有限的，我假设我们把袜子放在视线范围内的整个线部分。

以下是 put_socks_on_line（） 的算法：

while (socks left in basket) {
 take_sock();
 if (cluster of similar socks is present) { 
   Add sock to cluster (if possible, next to the matching pair)
 } else {
  Hang it somewhere on the line, this is now a new cluster of similar-looking socks.      
  Leave enough space around this sock to add other socks later on 
 }
}

不要浪费时间四处移动袜子或寻找最佳匹配，这一切都应该在 O（n） 中完成，我们也需要将它们放在未分类的生产线上。 袜子还没有配对，我们只有几个相似性集群。我们在这里有一组有限的袜子是很有帮助的，因为这有助于我们创建“好”的集群（例如，如果袜子组中只有黑色袜子，则按颜色集群将不是要走的路）

以下是 take_socks_from_line（） 的算法：

while(socks left on line) {
 take_next_sock();
 if (matching pair visible on line or in basket) {
   Take it as well, pair 'em and put 'em away
 } else {
   put the sock in the basket
 }

我应该指出，为了提高剩余步骤的速度，明智的做法不是随机挑选下一只袜子，而是从每个集群中按顺序挑选一只又一只袜子。 这两个预处理步骤都不需要花费更多的时间，只是将袜子放在生产线上或篮子里，无论如何我们都必须这样做，因此这应该会大大提高洗衣性能。

在此之后，就可以很容易地进行哈希分区算法了。通常，大约 75% 的袜子已经配对，给我留下了非常小的袜子子集，而且这个子集已经（在某种程度上）聚类了（在预处理步骤之后，我不会在我的篮子中引入太多熵）。另一件事是，剩余的簇往往足够小，可以一次处理，因此可以从篮子中取出整个簇。

以下是 sort_remaining_clusters（） 的算法：

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

在那之后，只剩下几只袜子了。在这里，我将以前未配对的袜子引入系统，并在没有任何特殊算法的情况下处理剩余的袜子 - 剩余的袜子非常少，并且可以在视觉上非常快速地处理。

对于所有剩余的袜子，我假设它们的对应物仍然未洗过，并将它们放在下一迭代中。如果你注意到随着时间的推移，不成对的袜子会增长（“袜子漏水”），你应该检查你的垃圾箱 - 它可能会被随机化（你有猫睡在那里吗？

我知道这些算法需要很多假设：一个充当某种后进先出堆栈的垃圾箱，一台有限的普通洗衣机，以及一根有限的普通晾衣绳——但这仍然适用于非常多的袜子。

关于并行性： 只要你把两只袜子都扔进同一个垃圾箱，你就可以很容易地并行完成所有这些步骤。

我提出的解决方案假设所有袜子在细节上都是相同的，除了颜色。如果袜子之间有更多细节需要延迟，这些细节可用于定义不同类型的袜子，而不是我示例中的颜色。

鉴于我们有一堆袜子，袜子可以有三种颜色：蓝色、红色或绿色。

然后，我们可以为每种颜色创建一个并行工作器;它有自己的列表来填充相应的颜色。

At time i:

Blue  read  Pile[i]    : If Blue  then Blue.Count++  ; B=TRUE  ; sync

Red   read  Pile[i+1]  : If Red   then Red.Count++   ; R=TRUE  ; sync

Green read  Pile [i+2] : If Green then Green.Count++ ; G=TRUE  ; sync

使用同步过程：

Sync i:

i++

If R is TRUE:
    i++
    If G is TRUE:
        i++

这需要初始化：

Init:

If Pile[0] != Blue:
    If      Pile[0] = Red   : Red.Count++
    Else if Pile[0] = Green : Green.Count++

If Pile[1] != Red:
    If Pile[0] = Green : Green.Count++

哪里

Best Case: B, R, G, B, R, G, .., B, R, G

Worst Case: B, B, B, .., B

Time(Worst-Case) = C * n ~ O(n)

Time(Best-Case) = C * (n/k) ~ O(n/k)

n: number of sock pairs
k: number of colors
C: sync overhead

如果“移动”操作相当昂贵，而“比较”操作很便宜，并且无论如何都需要将整个集合移动到搜索速度比原始存储快得多的缓冲区中......只需将分类集成到强制性移动中即可。

我发现将分拣过程整合到悬挂晾干中是一件轻而易举的事。无论如何，我都需要拿起每只袜子，然后把它挂起来（移动），把它挂在绳子上的特定位置几乎不需要花钱。现在，为了不强制搜索整个缓冲区（字符串），我选择按颜色/阴影放置袜子。左边更暗，右边更亮，正面更丰富多彩等。现在，在我挂每只袜子之前，我会查看它的“正确附近”是否已经有匹配的袜子——这将“扫描”限制为其他 2-3 只袜子——如果是，我会将另一只袜子挂在它旁边。然后我把它们卷成两对，同时从绳子上取下，当干燥时。

现在，这似乎与顶级答案建议的“按颜色形成桩”没有什么不同，但首先，通过不选择离散的桩而是选择范围，我对“紫色”是“红色”还是“蓝色”桩进行分类没有问题;它只是介于两者之间。然后通过集成两个操作（悬挂晾干和分拣），悬挂时分拣的开销约为单独分拣的 10%。

我的解决方案并不完全符合您的要求，因为它正式需要“额外”空间。但是，考虑到我的条件，它在我的实际应用中非常有效。因此，我认为这应该很有趣。O(n)

与其他任务结合

我的特殊情况是我不使用烘干机，只是将我的布挂在普通的干布机上。挂布需要操作（顺便说一句，我总是在这里考虑垃圾箱包装问题），而问题本质上需要线性的“额外”空间。当我从桶里拿出一只新袜子时，如果袜子已经挂好了，我会试着把它挂在袜子旁边。如果是一双新袜子，我会在它旁边留出一些空间。O(n)

甲骨文机器更好;-）

显然，它需要一些额外的工作来检查是否有匹配的袜子已经挂在某处，并且它会为计算机提供系数约为的解决方案。但在这种情况下，“人为因素”实际上是一个优势——如果袜子已经挂起来，我通常可以非常快速（几乎）识别出匹配的袜子（可能涉及一些难以察觉的大脑缓存）——将其视为一种有限的“神谕”，就像在 Oracle Machine 中一样;在某些情况下，我们人类比数字机器具有这些优势;-）O(n^2)1/2O(1)

快有了！O(n)

因此，将配对袜子的问题与挂布的问题联系起来，我免费获得了“额外的空间”，并且有一个及时的解决方案，只需要比简单的挂布多一点工作，即使在非常糟糕的星期一早上，也可以立即获得完整的袜子...... ;-）O(n)O(n)

你试图解决错误的问题。

解决方案 1：每次把脏袜子放在洗衣篮里时，都要打一个小结。这样，您就不必在洗涤后进行任何分类。可以把它想象成在 Mongo 数据库中注册索引。未来需要做一些工作，以便将来节省一些 CPU。

解决方案 2：如果是冬天，你不必穿配套的袜子。我们是程序员。没有人需要知道，只要它有效。

解决方案 3：传播工作。您希望异步执行如此复杂的 CPU 进程，而不会阻塞 UI。拿起那堆袜子，塞进袋子里。只在您需要时才寻找一对。这样一来，所需的工作量就不那么明显了。

希望这有帮助！

迈向一种从一堆袜子中配对的高效算法

前提 条件

1. 堆中必须至少有一只袜子
2. 桌子必须足够大，以容纳 N/2 袜子（最坏情况），其中 N 是总数 袜子。

算法

尝试：

1. 挑选第一只袜子
2. 把它放在桌子上
3. 选择下一只袜子，看看它（可能会扔掉“堆里不再有袜子”的例外情况）
4. 现在扫描桌子上的袜子（如果桌子上没有袜子，则抛出异常）
5. 有匹配吗？ a） yes => 从桌子上取下匹配的袜子 b） no => 把袜子放在桌子上（可能会抛出“桌子不够大”的异常）

除了：

• 桌子不够大：
  小心地将所有未配对的袜子混合在一起，然后恢复操作
  // 此操作将导致新的一堆和一张空的桌子

• 桌子上没有袜子：
  扔掉（最后一只无法配对的袜子）

• 袜子堆里没有袜子：
  离开洗衣房

最后：

• 如果堆里还有袜子：
  转到 3

已知问题

如果周围没有表，算法将进入无限循环，或者 桌子上没有足够的空间来容纳至少一只袜子。

可能的改进

根据要分拣的袜子数量，吞吐量可能为 通过对桌子上的袜子进行分类来增加，前提是有足够的袜子 空间。

为了使它起作用，需要一个具有唯一属性的属性 每双袜子的价值。这样的属性可以很容易地 从袜子的视觉特性合成而成。

按上述属性对桌子上的袜子进行排序。我们称之为该属性 '颜色'。将袜子排成一排，并将颜色较深的袜子放在 右边（即 .push_back（）））和左边浅色袜子（即 .push_front（））

对于大堆袜子，尤其是以前看不见的袜子，属性合成 可能需要大量时间，因此吞吐量会明显降低。 但是，这些属性可以保留在内存中并重复使用。

需要一些研究来评估这种可能性的效率 起色。出现以下问题：

• 上面要配对的最佳袜子数量是多少 起色？
• 对于给定数量的袜子，之前需要多少次迭代 吞吐量增加？
  a） 对于最后一次迭代
  b） 对于整个迭代的所有迭代

符合MCVE指南的PoC：

#include <iostream>
#include <vector>
#include <string>
#include <time.h>

using namespace std;

struct pileOfsocks {
    pileOfsocks(int pairCount = 42) :
        elemCount(pairCount<<1) {
        srand(time(NULL));
        socks.resize(elemCount);

        vector<int> used_colors;
        vector<int> used_indices;

        auto getOne = [](vector<int>& v, int c) {
            int r;
            do {
                r = rand() % c;
            } while (find(v.begin(), v.end(), r) != v.end());
            v.push_back(r);
            return r;
        };

        for (auto i = 0; i < pairCount; i++) {
            auto sock_color = getOne(used_colors, INT_MAX);
            socks[getOne(used_indices, elemCount)] = sock_color;
            socks[getOne(used_indices, elemCount)] = sock_color;
        }
    }

    void show(const string& prompt) {
        cout << prompt << ":" << endl;
        for (auto i = 0; i < socks.size(); i++){
            cout << socks[i] << " ";
        }
        cout << endl;
    }

    void pair() {
        for (auto i = 0; i < socks.size(); i++) {
            std::vector<int>::iterator it = find(unpaired_socks.begin(), unpaired_socks.end(), socks[i]);
            if (it != unpaired_socks.end()) {
                unpaired_socks.erase(it);
                paired_socks.push_back(socks[i]);
                paired_socks.push_back(socks[i]);
            }
            else
                unpaired_socks.push_back(socks[i]);
        }

        socks = paired_socks;
        paired_socks.clear();
    }

private:
    int elemCount;
    vector<int> socks;
    vector<int> unpaired_socks;
    vector<int> paired_socks;
};

int main() {
    pileOfsocks socks;

    socks.show("unpaired socks");
    socks.pair();
    socks.show("paired socks");

    system("pause");
    return 0;
}

两种思路，查找任何匹配项所需的速度，与查找所有匹配项所需的速度与存储相比。

对于第二种情况，我想指出一个 GPU 并行版本，它会查询袜子中的所有匹配项。

如果您有多个要匹配的属性，则可以使用分组元组和更漂亮的 zip 迭代器以及 thrust 的转换函数，为了简单起见，这里是基于 GPU 的简单查询：

//test.cu
#include <thrust/device_vector.h>
#include <thrust/sequence.h>
#include <thrust/copy.h>
#include <thrust/count.h>
#include <thrust/remove.h>
#include <thrust/random.h>
#include <iostream>
#include <iterator>
#include <string>

// Define some types for pseudo code readability
typedef thrust::device_vector<int> GpuList;
typedef GpuList::iterator          GpuListIterator;

template <typename T>
struct ColoredSockQuery : public thrust::unary_function<T,bool>
{
    ColoredSockQuery( int colorToSearch )
    { SockColor = colorToSearch; }

    int SockColor;

    __host__ __device__
    bool operator()(T x)
    {
        return x == SockColor;
    }
};


struct GenerateRandomSockColor
{
    float lowBounds, highBounds;

    __host__ __device__
    GenerateRandomSockColor(int _a= 0, int _b= 1) : lowBounds(_a), highBounds(_b) {};

    __host__ __device__
    int operator()(const unsigned int n) const
    {
        thrust::default_random_engine rng;
        thrust::uniform_real_distribution<float> dist(lowBounds, highBounds);
        rng.discard(n);
        return dist(rng);
    }
};

template <typename GpuListIterator>
void PrintSocks(const std::string& name, GpuListIterator first, GpuListIterator last)
{
    typedef typename std::iterator_traits<GpuListIterator>::value_type T;

    std::cout << name << ": ";
    thrust::copy(first, last, std::ostream_iterator<T>(std::cout, " "));
    std::cout << "\n";
}

int main()
{
    int numberOfSocks = 10000000;
    GpuList socks(numberOfSocks);
    thrust::transform(thrust::make_counting_iterator(0),
                      thrust::make_counting_iterator(numberOfSocks),
                      socks.begin(),
                      GenerateRandomSockColor(0, 200));

    clock_t start = clock();

    GpuList sortedSocks(socks.size());
    GpuListIterator lastSortedSock = thrust::copy_if(socks.begin(),
                                                     socks.end(),
                                                     sortedSocks.begin(),
                                                     ColoredSockQuery<int>(2));
    clock_t stop = clock();

    PrintSocks("Sorted Socks: ", sortedSocks.begin(), lastSortedSock);

    double elapsed = (double)(stop - start) * 1000.0 / CLOCKS_PER_SEC;
    std::cout << "Time elapsed in ms: " << elapsed << "\n";

    return 0;
}

    //nvcc -std=c++11 -o test test.cu

1000 万只袜子的运行时间：9 ms

正如许多作者所指出的，基数排序是一种有效的袜子分类方法。尚未提出的是一种完美的散列方法。使用每双袜子的购买时间就是这样的哈希值。只需在购买袜子时按顺序编号，就可以在翻阅袜子时将它们放在自己编号的抽屉中。

最多 24 双袜子的示例。请注意，较大的袜子隔层消除了将袜子卷在一起的需要，即所谓的速度/存储权衡。

Defant & Kravitz （1） 给出了一种算法，通过按顺序将袜子放在脚上和脚上来对袜子进行分类。

他们的算法适用于任意数量的英尺。

本文给出了（定理1.1）袜子顺序的特征，这些顺序可以使用一只脚进行排序。根据他们的定理 1.3，每个 4 种颜色的袜子订单最多可以用两英尺进行分类，而存在 5 种颜色的袜子订单，而不可能用两只脚进行分类。

1. Colin Defant 和 Noah Kravitz，袜子的足部分类 （2022）