协慌网

昨天我把干净的洗衣店的袜子配对，弄清楚我做的方式效率不高。我正在做一个天真的搜索 - 挑选一个袜子并 “迭代” 堆，以找到它的对。这需要迭代在 n / 2 * N / 4 = N ^2/8上平均的袜子。

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

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

所以，问题基本上是：

鉴于一堆n双袜子，包含2n元素（假设每个袜子只有一对匹配），有效配对多达对数额外空间的最佳方法是什么？ （我相信如果需要，我会记住那些信息。）

我将感谢一个解决以下方面的答案：

• 大量袜子的一般理论解决方案。
• 袜子的实际数量并不是那么大，我不相信我的配偶和我有超过 30 双。 （并且很容易区分我的袜子和她的袜子; 这也可以使用吗？）
• 它是否等同于元素清晰度问题 ？

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

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

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

当需要在大型数据集上散列连接或散列聚合时，这种递归散列分区实际上是由SQL Server完成的。它将构建输入流分配到许多独立的分区中。该方案线性地扩展到任意数量的数据和多个 CPU。

如果您可以找到提供足够桶的分发键（散列键），并且每个桶足够小以便快速处理，则不需要递归分区。不幸的是，我不认为袜子有这样的属性。

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

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

更新：

并行性怎么样？多个人可以更快地匹配袜子吗？

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

元素清晰度问题怎么样？正如文章所述，元素清晰度问题可以用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)比较的排序算法。

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

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

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

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

当需要在大型数据集上散列连接或散列聚合时，这种递归散列分区实际上是由SQL Server完成的。它将构建输入流分配到许多独立的分区中。该方案线性地扩展到任意数量的数据和多个 CPU。

如果您可以找到提供足够桶的分发键（散列键），并且每个桶足够小以便快速处理，则不需要递归分区。不幸的是，我不认为袜子有这样的属性。

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

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

更新：

并行性怎么样？多个人可以更快地匹配袜子吗？

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

元素清晰度问题怎么样？正如文章所述，元素清晰度问题可以用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)比较的排序算法。

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