昨天,我在洗衣服时把袜子配对,结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子,然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。

作为一名计算机科学家,我在想我能做什么?排序(根据大小/颜色/…)当然是为了实现O(NlogN)解决方案。

哈希或其他不到位的解决方案是不可选择的,因为我无法复制我的袜子(如果可以的话,这可能很好)。

因此,问题基本上是:

给定一堆n双袜子,其中包含2n个元素(假设每只袜子正好有一对匹配的袜子),用对数的额外空间高效地将它们配对的最佳方式是什么?(如果需要的话,我相信我可以记住这些信息。)

我将感谢回答以下方面的问题:

大量袜子的一般理论解。袜子的实际数量没有那么多,我不相信我的配偶和我有超过30双。(而且很容易区分我的袜子和她的袜子;这也可以用吗?)它是否等同于元素清晰度问题?


当前回答

排序解决方案已经提出,但排序有点太多了:我们不需要排序;我们只需要平等团体。

所以散列就足够了(而且更快)。

对于每种颜色的袜子,形成一堆。重复输入篮中的所有袜子,并将它们分配到颜色堆上。在每个桩上循环,并通过其他度量(例如模式)将其分配到第二组桩中递归地应用此方案,直到您将所有袜子分发到非常小的堆上,您可以立即进行可视化处理

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

如果您可以找到一个分发密钥(哈希密钥),该密钥提供足够的存储桶,使得每个存储桶足够小,可以快速处理,那么您就不需要递归分区。不幸的是,我认为袜子没有这种特性。

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

我能想到的现实世界中最好的分区是创建一个堆积的矩形:一个维度是颜色,另一个是图案。为什么是长方形?因为我们需要O(1)随机访问桩。(3D长方体也可以,但这不太实用。)


更新:

并行性呢?多人能更快地匹配袜子吗?

最简单的并行化策略是让多个工人从输入篮中取出袜子,然后将袜子放到堆上。这只会增加这么多——想象100人在10个桩上战斗。同步成本(表现为手部碰撞和人类通信)破坏了效率和加速(参见通用可扩展性定律!)。这是否容易陷入僵局?不,因为每个工人一次只需要访问一堆。只有一个“锁”,就不会出现死锁。活锁可能是可能的,这取决于人类如何协调对桩的访问。他们可能只是使用随机退避,就像网卡在物理级别上那样,以确定什么卡可以独占地访问网络线路。如果它适用于NIC,那么它也应该适用于人类。如果每个工人都有自己的一组桩,它几乎可以无限扩展。然后,工人可以从输入篮中取出大块袜子(很少有人争抢,因为他们很少这样做),而且他们在分发袜子时根本不需要同步(因为他们有线程局部堆)。最后,所有工人都需要联合他们的桩组。我相信,如果工人形成一个聚合树,这可以在O(log(工人计数*每个工人的桩数))中完成。

元素的清晰度问题呢?正如文章所述,元素区别问题可以用O(N)来解决。袜子问题也是如此(如果你只需要一个分发步骤(我提出了多个步骤,只是因为人类不擅长计算-如果你在md5上分发(颜色、长度、图案…),即所有属性的完美哈希),那么一个步骤就够了)。

显然,一个速度不能比O(N)快,所以我们已经达到了最佳下限。

虽然输出不完全相同(在一种情况下,只是布尔值。在另一种情况中,是袜子对),但渐近复杂性是相同的。

其他回答

排序解决方案已经提出,但排序有点太多了:我们不需要排序;我们只需要平等团体。

所以散列就足够了(而且更快)。

对于每种颜色的袜子,形成一堆。重复输入篮中的所有袜子,并将它们分配到颜色堆上。在每个桩上循环,并通过其他度量(例如模式)将其分配到第二组桩中递归地应用此方案,直到您将所有袜子分发到非常小的堆上,您可以立即进行可视化处理

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

如果您可以找到一个分发密钥(哈希密钥),该密钥提供足够的存储桶,使得每个存储桶足够小,可以快速处理,那么您就不需要递归分区。不幸的是,我认为袜子没有这种特性。

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

我能想到的现实世界中最好的分区是创建一个堆积的矩形:一个维度是颜色,另一个是图案。为什么是长方形?因为我们需要O(1)随机访问桩。(3D长方体也可以,但这不太实用。)


更新:

并行性呢?多人能更快地匹配袜子吗?

最简单的并行化策略是让多个工人从输入篮中取出袜子,然后将袜子放到堆上。这只会增加这么多——想象100人在10个桩上战斗。同步成本(表现为手部碰撞和人类通信)破坏了效率和加速(参见通用可扩展性定律!)。这是否容易陷入僵局?不,因为每个工人一次只需要访问一堆。只有一个“锁”,就不会出现死锁。活锁可能是可能的,这取决于人类如何协调对桩的访问。他们可能只是使用随机退避,就像网卡在物理级别上那样,以确定什么卡可以独占地访问网络线路。如果它适用于NIC,那么它也应该适用于人类。如果每个工人都有自己的一组桩,它几乎可以无限扩展。然后,工人可以从输入篮中取出大块袜子(很少有人争抢,因为他们很少这样做),而且他们在分发袜子时根本不需要同步(因为他们有线程局部堆)。最后,所有工人都需要联合他们的桩组。我相信,如果工人形成一个聚合树,这可以在O(log(工人计数*每个工人的桩数))中完成。

元素的清晰度问题呢?正如文章所述,元素区别问题可以用O(N)来解决。袜子问题也是如此(如果你只需要一个分发步骤(我提出了多个步骤,只是因为人类不擅长计算-如果你在md5上分发(颜色、长度、图案…),即所有属性的完美哈希),那么一个步骤就够了)。

显然,一个速度不能比O(N)快,所以我们已经达到了最佳下限。

虽然输出不完全相同(在一种情况下,只是布尔值。在另一种情况中,是袜子对),但渐近复杂性是相同的。

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

此外,即使是大家庭,我们也不需要假设有大量袜子。袜子从抽屉中取出并穿上,然后在洗衣服之前,将它们扔到一个地方(可能是一个垃圾箱)。虽然我不会将所说的垃圾箱称为后进先出堆栈,但我认为可以安全地假设

人们把两只袜子大致扔在箱子箱子在任何时候都不会随机化,因此从该容器顶部获取的任何子集通常都包含一双袜子。

由于我所知道的所有洗衣机的尺寸都是有限的(不管你要洗多少袜子),而且洗衣机中会发生实际的随机性,所以无论我们有多少袜子,我们总是有几乎不含单品的小子集。

我们的两个预处理阶段是“把袜子放在晾衣绳上”和“把袜子从晾衣绳里拿出来”,我们必须这样做,这样才能得到既干净又干燥的袜子。和洗衣机一样,晾衣绳是有限的,我假设我们可以看到袜子的整个部分。

以下是put_socks_on_ine()的算法:

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_maining_clusters()的算法:

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

之后,只剩下几只袜子了。在这里,我将之前未配对的袜子引入到系统中,并在不使用任何特殊算法的情况下处理剩余的袜子——剩余的袜子非常少,可以非常快速地进行视觉处理。

对于所有剩余的袜子,我假设它们的同伴仍然没有洗,并将它们放在一边,以备下次迭代。如果你记录了一段时间内未配对袜子的增长(“袜子泄漏”),你应该检查你的垃圾箱——它可能会随机出现(你有猫睡在里面吗?)

我知道这些算法需要很多假设:一个充当某种LIFO堆栈的垃圾箱,一台有限的普通洗衣机,以及一条有限的普通晾衣绳——但这仍然适用于大量袜子。

关于并行性:只要你把两个袜子放在同一个箱子里,你就可以很容易地并行化所有这些步骤。

正如许多作者所指出的,基数排序是一种有效的袜子排序方法。尚未提出的是一种完美的哈希方法。用每双袜子买来的时间来计算真是太麻烦了。在你购买袜子时,只需按顺序给袜子编号,就可以让你在整理袜子时把它们放在自己编号的抽屉里。

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

由于人脑的结构与现代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);
}

至少这是我在现实生活中使用的,我发现它非常有效。缺点是它需要一个平坦的表面,但通常很丰富。

当我对袜子进行排序时,我会进行近似基数排序,将袜子放在同一颜色/图案类型的其他袜子附近。除非在我即将放下袜子的地方/附近,我能看到一对完全匹配的袜子,否则我会在那一刻取出这双袜子。

几乎所有其他算法(包括usr评分最高的答案)排序,然后删除配对。我发现,作为一个人,一次考虑的袜子数量最好尽量减少。

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

挑选一只与众不同的袜子(在袜子堆里最先映入我眼帘的东西)。从概念位置开始基数排序,根据与该位置的相似性从堆中拉出袜子。将新袜子放在当前袜子堆的附近,距离取决于它的不同程度。如果你发现自己将袜子放在另一只袜子的上面,因为它是相同的,请在那里形成一对,然后将它们取下。这意味着未来的比较需要更少的努力来找到正确的位置。

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

通过先穿上与众不同的袜子,你可以留出空间来“放大”那些不那么与众不同的特征。

在去除了浅色、条纹袜子和三双长袜之后,你可能最终会得到大致按磨损程度分类的白色袜子。

在某种程度上,袜子之间的差异很小,以至于其他人不会注意到差异,因此不需要进一步的匹配。