昨天,我在洗衣服时把袜子配对,结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子,然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家,我在想我能做什么?排序(根据大小/颜色/…)当然是为了实现O(NlogN)解决方案。
哈希或其他不到位的解决方案是不可选择的,因为我无法复制我的袜子(如果可以的话,这可能很好)。
因此,问题基本上是:
给定一堆n双袜子,其中包含2n个元素(假设每只袜子正好有一对匹配的袜子),用对数的额外空间高效地将它们配对的最佳方式是什么?(如果需要的话,我相信我可以记住这些信息。)
我将感谢回答以下方面的问题:
大量袜子的一般理论解。袜子的实际数量没有那么多,我不相信我的配偶和我有超过30双。(而且很容易区分我的袜子和她的袜子;这也可以用吗?)它是否等同于元素清晰度问题?
非算法答案,但当我这样做时“高效”:
步骤1)丢弃所有现有袜子第2步)去沃尔玛买10-n包的白色和m包黑色。日常无需其他颜色生活
然而,有时,我不得不再次这样做(丢失的袜子、损坏的袜子等),我讨厌太频繁地丢弃完美的袜子(我希望他们继续出售相同的袜子参考!),所以我最近采取了不同的方法。
算法答案:
考虑一下,如果你只为第二叠袜子画一只袜子,就像你正在做的那样,你在天真的搜索中找到匹配袜子的几率很低。
所以,随机挑选其中五个,记住它们的形状或长度。
为什么是五?通常情况下,人类在工作记忆中记住五到七个不同的元素是很好的——有点像RPN堆栈的人类等价物——五个是安全的默认值。
从2n-5的堆栈中选择一个。现在,在你画的五个图案中寻找一个匹配(视觉模式匹配-人类擅长用一个小堆栈),如果你没有找到一个,那么把它添加到你的五个。继续从袜子堆中随机挑选袜子,并与你的5+1袜子进行比较。随着堆栈的增长,它会降低性能,但会提高赔率。快得多。
请随意写下公式,以计算50%的匹配几率需要抽取多少样本。IIRC这是一个超几何定律。
我每天早上都会这样做,很少需要三次以上的平局——但我有n双类似的m形白袜子(大约10双,不分输赢)。现在你可以估计我的股票堆的大小:-)
顺便说一句,我发现,每次我需要一双袜子时,整理所有袜子的交易成本之和远远少于一次整理和装订袜子。准时制的效果更好,因为这样你就不必绑袜子了,而且边际回报也在减少(也就是说,当你在洗衣店的某个地方时,你一直在寻找那两到三只袜子,而你需要完成袜子的搭配,而你却在这上面浪费了时间)。
当我对袜子进行排序时,我会进行近似基数排序,将袜子放在同一颜色/图案类型的其他袜子附近。除非在我即将放下袜子的地方/附近,我能看到一对完全匹配的袜子,否则我会在那一刻取出这双袜子。
几乎所有其他算法(包括usr评分最高的答案)排序,然后删除配对。我发现,作为一个人,一次考虑的袜子数量最好尽量减少。
我通过以下方式做到这一点:
挑选一只与众不同的袜子(在袜子堆里最先映入我眼帘的东西)。从概念位置开始基数排序,根据与该位置的相似性从堆中拉出袜子。将新袜子放在当前袜子堆的附近,距离取决于它的不同程度。如果你发现自己将袜子放在另一只袜子的上面,因为它是相同的,请在那里形成一对,然后将它们取下。这意味着未来的比较需要更少的努力来找到正确的位置。
这利用了人类在O(1)时间内进行模糊匹配的能力,这在某种程度上相当于在计算设备上建立哈希图。
通过先穿上与众不同的袜子,你可以留出空间来“放大”那些不那么与众不同的特征。
在去除了浅色、条纹袜子和三双长袜之后,你可能最终会得到大致按磨损程度分类的白色袜子。
在某种程度上,袜子之间的差异很小,以至于其他人不会注意到差异,因此不需要进一步的匹配。
由于人脑的结构与现代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);
}
至少这是我在现实生活中使用的,我发现它非常有效。缺点是它需要一个平坦的表面,但通常很丰富。