昨天,我在洗衣服时把袜子配对,结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子,然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家,我在想我能做什么?排序(根据大小/颜色/…)当然是为了实现O(NlogN)解决方案。
哈希或其他不到位的解决方案是不可选择的,因为我无法复制我的袜子(如果可以的话,这可能很好)。
因此,问题基本上是:
给定一堆n双袜子,其中包含2n个元素(假设每只袜子正好有一对匹配的袜子),用对数的额外空间高效地将它们配对的最佳方式是什么?(如果需要的话,我相信我可以记住这些信息。)
我将感谢回答以下方面的问题:
大量袜子的一般理论解。袜子的实际数量没有那么多,我不相信我的配偶和我有超过30双。(而且很容易区分我的袜子和她的袜子;这也可以用吗?)它是否等同于元素清晰度问题?
当我对袜子进行排序时,我会进行近似基数排序,将袜子放在同一颜色/图案类型的其他袜子附近。除非在我即将放下袜子的地方/附近,我能看到一对完全匹配的袜子,否则我会在那一刻取出这双袜子。
几乎所有其他算法(包括usr评分最高的答案)排序,然后删除配对。我发现,作为一个人,一次考虑的袜子数量最好尽量减少。
我通过以下方式做到这一点:
挑选一只与众不同的袜子(在袜子堆里最先映入我眼帘的东西)。从概念位置开始基数排序,根据与该位置的相似性从堆中拉出袜子。将新袜子放在当前袜子堆的附近,距离取决于它的不同程度。如果你发现自己将袜子放在另一只袜子的上面,因为它是相同的,请在那里形成一对,然后将它们取下。这意味着未来的比较需要更少的努力来找到正确的位置。
这利用了人类在O(1)时间内进行模糊匹配的能力,这在某种程度上相当于在计算设备上建立哈希图。
通过先穿上与众不同的袜子,你可以留出空间来“放大”那些不那么与众不同的特征。
在去除了浅色、条纹袜子和三双长袜之后,你可能最终会得到大致按磨损程度分类的白色袜子。
在某种程度上,袜子之间的差异很小,以至于其他人不会注意到差异,因此不需要进一步的匹配。
为了说明从一堆袜子中配对有多有效,我们必须首先定义机器,因为配对不是通过图灵或随机存取机器完成的,而随机存取机器通常用作算法分析的基础。
机器
机器是被称为人类的现实世界元素的抽象。它能够通过一双眼睛从环境中阅读。我们的机器模型能够通过使用两个手臂来操纵环境。逻辑和算术运算是用我们的大脑计算的(希望是;-)。
我们还必须考虑可以使用这些仪器执行的原子操作的内在运行时间。由于物理限制,由手臂或眼睛执行的操作具有非恒定的时间复杂性。这是因为我们不能用手臂移动一大堆无穷无尽的袜子,也不能用眼睛看到一大堆袜子上的袜子。
然而,机械物理学也给了我们一些好处。我们不限于用手臂移动最多一只袜子。我们可以一次移动两个。
因此,根据之前的分析,应按降序使用以下操作:
逻辑和算术运算环境读数环境改造
我们还可以利用这样一个事实,即人们只有非常有限的袜子。因此,环境改造可能涉及到所有袜子。
算法
我的建议是:
把袜子堆里的袜子都铺在地板上。通过看地板上的袜子找到一双。从2开始重复,直到无法配对。从1开始重复,直到地板上没有袜子。
操作4是必要的,因为当将袜子铺在地板上时,一些袜子可能会隐藏其他袜子。算法分析如下:
分析
该算法以高概率终止。这是由于在第二步中找不到袜子。
对于以下对n双袜子配对的运行时分析,我们假设在步骤1之后,至少有一半的2n双袜子没有隐藏。所以在平均情况下,我们可以找到n/2对。这意味着步骤4的循环执行了O(logn)次。步骤2执行O(n^2)次。因此,我们可以得出结论:
该算法涉及O(lnn+n)环境修改(步骤1 O(lnn)加上从地板上挑选每双袜子)该算法涉及步骤2中的O(n^2)个环境读数该算法包括O(n^2)个逻辑和算术运算,用于在步骤2中比较袜子和另一袜子
因此,我们的总运行时复杂度为O(r*n^2+w*(lnn+n)),其中r和w分别是合理数量袜子的环境读取和环境写入操作的因素。省略了逻辑运算和算术运算的成本,因为我们假设需要恒定数量的逻辑运算和算数运算来决定2只袜子是否属于同一对。这可能在每种情况下都不可行。
成本:移动袜子->高,查找/搜索袜子排成一排->小
我们想做的是减少移动次数,并用搜索次数进行补偿。此外,我们还可以利用智人的多威胁环境,在解密缓存中保存更多的东西。
X=您的,Y=您的配偶
从所有袜子的A堆开始:
选择两个袜子,将相应的X袜子放在X线上,将Y袜子放在Y线上的下一个可用位置。
直到A为空。
对于每行X和Y
选择行中的第一只袜子,沿着行搜索,直到找到相应的袜子。放入相应的袜子成品线。可选当您搜索线条时,当前正在查看的袜子与之前的袜子相同,请对这些袜子执行步骤2。
可选地,在第一步中,您从该行中拾取两个袜子,而不是两个,因为缓存内存足够大,我们可以快速识别其中一个袜子是否与您正在观察的行上的当前袜子匹配。如果你有幸拥有三只手臂,那么考虑到受试者的记忆足够大,你可以同时解析三只袜子。
直到X和Y都为空。
Done
然而,由于这与选择排序具有相似的复杂性,由于I/O(移动袜子)和搜索(搜索袜子的行)的速度,所花费的时间要少得多。
这个问题实际上很有哲理。本质上,这是关于人们解决问题的能力(我们大脑的“湿件”)是否等同于算法所能完成的任务。
袜子分类的一个明显算法是:
Let N be the set of socks that are still unpaired, initially empty
for each sock s taken from the dryer
if s matches a sock t in N
remove t from N, bundle s and t together, and throw them in the basket
else
add s to N
现在这个问题的计算机科学都是关于步骤的
“如果s与N中的袜子t配对”。我们能多快“记住”到目前为止所看到的东西?“从N中删除t”和“将s添加到N”。跟踪我们目前所看到的情况有多贵?
人类将使用各种策略来实现这些目标。人类的记忆是关联的,类似于哈希表,其中存储值的特征集与相应的值本身配对。例如,“红色汽车”的概念映射到一个人能够记住的所有红色汽车。有完美记忆的人有完美的映射。大多数人(以及其他大多数人)在这方面都不完美。关联映射的容量有限。映射可能会在各种情况下(一杯啤酒太多)消失,被错误记录(“我认为她的名字是贝蒂,而不是内蒂”),或者即使我们观察到真相已经改变,也永远不会被覆盖(“爸爸的车”让人想起“橙色火鸟”,而我们实际上知道他用它换了红色的科迈罗)。
就袜子而言,完美回忆意味着看一只袜子总会产生它的同胞t的记忆,包括足够的信息(它在熨衣板上的位置),以便在恒定的时间内找到t。一个有照片记忆的人会在恒定的时间内完成1和2的任务。
记忆力不太好的人可能会根据自己能力范围内的特征使用一些常识等价类:尺寸(爸爸、妈妈、宝宝)、颜色(绿色、红色等)、图案(菱形、素色等)、风格(脚、膝盖高等)。这通常允许通过内存在恒定时间内定位类别,但随后需要通过类别“桶”进行线性搜索。
一个完全没有记忆或想象力的人(抱歉)只会把袜子放在一堆里,然后对整堆袜子进行线性搜索。
一个整洁的怪人可能会像某人建议的那样使用数字标签。这打开了完全排序的大门,允许人类使用与CPU完全相同的算法:二进制搜索、树、散列等。
因此,“最佳”算法取决于运行该算法的湿软件/硬件/软件的质量,以及我们是否愿意通过对其施加总订单来“欺骗”。当然,一个“最好”的元算法是雇佣世界上最好的袜子分类器:一个人或机器可以通过不断的时间查找、插入和删除,在1-1关联存储器中获取并快速存储大量的袜子属性集N。这样的人和机器都可以采购。如果你有一双袜子,你可以在O(N)时间内将所有袜子配对N双,这是最佳的。总订单标签允许您使用标准哈希来获得与人工或硬件计算机相同的结果。