如何有效地从一堆袜子中配对？
昨天我把干净的洗衣店里的袜子做成了配对，并且发现我做这件事的方式效率不高。 我正在做一个天真的搜索 - 挑选一只袜子并“迭代”一堆以找到它的一对。 这要求平均迭代n / 2 * n / 4 = n2 / 8袜子。
作为一名计算机科学家，我在想我能做什么？ 当然想到排序（根据大小/颜色/ ...）来实现O（NlogN）解决方案。
哈希或其他非原地解决方案不是一种选择，因为我无法复制我的袜子（尽管如果可以的话它可能会很好）。
所以，问题基本上是：
给定一堆n对袜子，包含2n元素（假设每个袜子只有一个配对），将它们有效配对到对数额外空间的最佳方法是什么？ （如果需要，我相信我可以记住这些信息量。）
我将非常感谢解决以下问题的答案：
已经提出了分拣解决方案，但排序有点太过分了 ：我们不需要订单; 我们只需要平等团体 。
所以哈希将是足够的（和更快）。
这种递归散列分区实际上是由SQL Server完成的，因为它需要对大数据集进行散列连接或散列汇总。 它将其构建输入流分发到许多独立的分区中。 该方案线性扩展为任意数量的数据和多个CPU。
如果您可以找到一个分配密钥（散列密钥），那么您不需要递归分区，即提供足够的存储桶以使每个存储桶足够小以便能够非常快地处理。 不幸的是，我不认为袜子有这样的财产。
如果每个袜子都有一个称为“PairID”的整数，则可以根据PairID % 10 （最后一位数）轻松地将它们分配到10个桶中。
我能想到的最好的现实世界划分是创建一个长方形的堆 ：一个是颜色，另一个是模式。 为什么是矩形？ 因为我们需要O（1）随机访问桩。 （3D长方体也可以，但这不太实际。）
更新：
并行性呢？ 多个人可以更快地匹配袜子吗？
元素清晰度问题呢？ 正如文章所述，元素清晰度问题可以在O(N)解决。 这对于袜子问题也是一样的（也是O(N) ，如果你只需要一个分布步骤（我只提出多个步骤，因为人类在计算上不好 - 如果你在md5(color, length, pattern, ...)分布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 ：组合的数量不变（所有权，颜色，大小，纹理等）。
使用基数排序。 这只是线性时间，因为不需要比较。
情况3 ：组合的数量未预先知道（一般情况）。
我们必须做比较来检查两只袜子是否配对。 选择O(n log n)基于比较的排序算法之一。
然而，在现实生活中，当袜子的数量相对较小（不变）时，这些理论上最优的算法将不能很好地工作。 它可能比顺序搜索花费更多时间，理论上这需要二次时间。
链接地址: http://www.djcxy.com/p/195.html