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

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

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

因此,问题基本上是:

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

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

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


当前回答

做一些预处理怎么样?我会在每只袜子上缝上一个标记或身份证号码,这样每双袜子都有相同的标记/身份证号码。这个过程可能在你每次买一双新袜子时都会完成。然后,您可以进行基数排序以获得O(n)总成本。为每个标记/身份证号码找一个位置,只需逐一挑选所有袜子并将它们放在正确的位置。

其他回答

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

如果我们假设正态分布,那么至少有一个袜子映射到一个存储桶的估计“插入”数量为NlogN(即,所有存储桶都已满)

我将此作为另一个谜题的一部分,但我很乐意被证明是错误的。这是我的博客文章

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

一旦发生碰撞(也就是火柴),只需脱掉那双袜子。对下一批NlogN袜子重复相同的实验。它的美妙之处在于,由于人类思维的方式,你可以进行NlogN并行比较(冲突解决)

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

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

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

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

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

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

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


更新:

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

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

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

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

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

我已经采取了简单的步骤,将我的努力减少到一个需要O(1)时间的过程中。

通过将我的输入减少到两种袜子中的一种(休闲用的白色袜子,工作用的黑色袜子),我只需要确定手中有哪种袜子。(从技术上讲,由于它们从未一起清洗过,我已将过程缩短到O(0)时间。)

为了找到合适的袜子,需要提前付出一些努力,并购买足够数量的袜子,以消除对现有袜子的需求。因为我在需要黑色袜子之前就已经做了这件事,所以我的努力很小,但里程可能会有所不同。

这种前期工作在非常流行和有效的代码中已经多次出现。示例包括#DEFINE'将圆周率定义为几个小数(其他示例也存在,但这是我现在想到的)。

真实世界方法:

尽快将袜子从未分类的袜子堆中取出,一次一个,然后放在前面。桩应布置得有一定的空间效率,所有袜子指向相同的方向;桩的数量受你容易到达的距离的限制。选择一堆袜子时,应尽快将袜子放在一堆看起来很像的袜子上;偶尔出现的I型(把袜子放在不属于它的袜子堆上)或II型(当有一堆类似的袜子时,把袜子放进自己的袜子堆里)错误是可以容忍的——最重要的考虑是速度。

一旦所有袜子都成了一堆,快速穿过多个袜子堆,创建成对的袜子,然后将它们取下(这些袜子朝抽屉方向)。如果袜子堆中有不匹配的袜子,请将它们重新堆到最好的位置(在尽可能快的限制范围内)。当处理完所有的多袜子堆后,将由于II类错误而未配对的剩余可配对袜子进行配对。哎呦,你完了——我有很多袜子,直到大部分都脏了才洗。另一个实际注意事项是:我将一双袜子的顶部翻转到另一双袜子上,利用它们的弹性财产,以便它们在被运送到抽屉和抽屉中时保持在一起。

案例1:所有袜子都是一样的(顺便说一句,这是我在现实生活中所做的)。

选择其中的任意两个组成一对。恒定时间。

案例2:有固定数量的组合(所有权、颜色、大小、纹理等)。

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

情况3:组合的数量事先未知(一般情况)。

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

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