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

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

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

因此,问题基本上是:

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

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

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


当前回答

如果你可以将一双袜子抽象为密钥本身,将另一双袜子作为值,那么我们可以使用哈希来发挥作用。

在你身后的地板上做两个假想的部分,一个给你,另一个给配偶。从袜子堆里取一只。现在,按照以下规则将袜子一只一只地放在地板上。确定袜子是你的还是她的,并查看地板上的相关部分。如果你能在地板上找到这双鞋,就把它捡起来,把它们系起来,或者把它们夹起来,或者在找到一双鞋后做任何你想做的事情,然后把它放在篮子里(把它从地板上取下来)。将其放在相关章节中。重复3次,直到所有袜子都从袜子堆上取下。

说明:

哈希和抽象

抽象是一个非常强大的概念,已用于改善用户体验(UX)。现实生活中与计算机交互的抽象示例包括:

用于在GUI(图形用户界面)中导航以访问地址的文件夹图标,而不是键入实际地址以导航到某个位置。GUI滑块用于控制不同级别的音量、文档滚动位置等。。

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

我相信提问者正在考虑使用哈希,这样在放置袜子之前,应该知道袜子的位置。

这就是为什么我建议将放在地板上的一只袜子抽象为哈希键本身(因此不需要复制袜子)。

如何定义哈希键?

如果有不止一双类似的袜子,下面的密钥定义也适用。也就是说,假设有两双黑色男士袜子PairA和PairB,每双袜子都被命名为PairA-L、PairA-R、PairB-L和PairB-R。因此,PairA-L可以与PairB-R配对,但PairA-L和PairB-L不能配对。

假设任何袜子都可以通过以下方式唯一标识,

属性[性别]+属性[颜色]+属性(材质)+属性[类型1]+属性[类别2]+属性[左_右]

这是我们的第一个哈希函数。让我们对这个h1(G_C_M_T1_T2_LR)使用一个简短的符号。h1(x)不是我们的位置键。

消除Left_or_Right属性的另一个哈希函数是h2(G_C_M_T1_T2)。第二个函数h2(x)是我们的位置键!(你身后地板上的空间)。

要定位插槽,请使用h2(G_C_M_T1_T2)。一旦找到了槽,就使用h1(x)来检查它们的哈希值。如果它们不匹配,你就有一对。否则,把袜子扔到同一个槽里。

注意:由于我们在找到一个插槽时删除了一个插槽,因此可以安全地假设最多只有一个插槽具有唯一的h2(x)或h1(x)值。

如果我们每只袜子正好有一对匹配的袜子,那么使用h2(x)来查找位置,如果没有袜子,则需要进行检查,因为可以安全地假设它们是一对。

为什么把袜子放在地板上很重要

让我们考虑一个场景,袜子堆在一起(最坏的情况)。这意味着我们别无选择,只能进行线性搜索来找到一对。

将它们铺在地板上可以提高可见度,从而提高发现匹配袜子(匹配哈希键)的机会。当第三步把袜子放在地板上时,我们的大脑已经下意识地记录了位置。-因此,如果这个位置在我们的内存中可用,我们可以直接找到匹配的配对。-如果没有记住位置,不要担心,然后我们可以一直返回到线性搜索。

为什么从地板上取下这对鞋很重要?

短期人类记忆在需要记忆的项目较少时效果最好。因此,增加了我们使用哈希来识别这对的概率。当使用线性搜索对时,它还将减少要搜索的项目的数量。

分析

情况1:最坏的情况是,Derpina无法记住或直接使用哈希技术在地板上发现袜子。Derp对地板上的物品进行线性搜索。这并不比遍历堆以找到对更糟。比较上限:O(n^2)。比较下限:(n/2)。(当Derpina每捡一只袜子都是上一只的时候)。案例2:德普记得他放在地板上的每一只袜子的位置,每只袜子正好有一双。比较上限:O(n/2)。比较下限:O(n/2)。

我说的是比较操作,从袜子堆里挑选袜子必然是n次操作。因此,实际的下限是n次迭代,n/2次比较。

加快进度

为了获得完美的分数,使Derp获得O(n/2)比较,我建议Derpina,

花更多时间穿袜子来熟悉它。是的,这意味着也要花更多时间穿着德普的袜子。玩记忆游戏,如在网格中找出对,可以提高短期记忆性能,这是非常有益的。

这是否等同于元素清晰度问题?

我建议的方法是用于解决元素区分问题的方法之一,将它们放在哈希表中并进行比较。

考虑到您的特殊情况,即只有一个精确的对,它已经变得非常等价于元素区别问题。因为我们甚至可以对袜子进行分类,并检查相邻袜子是否成对(EDP的另一种解决方案)。

然而,如果给定袜子可能存在不止一双,那么它就偏离了EDP。

其他回答

对于p双袜子(n=2p只袜子),我实际上是这样做的:

从袜子堆里随便拿一只袜子。对于第一只袜子,或者如果之前选择的所有袜子都已配对,只需将袜子放入前面未配对袜子“阵列”的第一个“槽”中。如果有一个或多个选定的未配对袜子,请对照阵列中的所有未配对袜子检查当前袜子。在构建阵列时,可以将袜子分为普通类别或类型(白色/黑色、脚踝/圆领、运动型/连衣裙),并“向下搜索”以仅比较同类。如果你找到了一个可以接受的匹配,把两只袜子放在一起,然后把它们从阵列中去掉。如果没有,请将当前袜子放入阵列中第一个打开的插槽中。对每只袜子重复上述步骤。

这种方案的最坏情况是,每双袜子都不同,必须完全匹配,而且你挑选的第一双n/2袜子都不同。这是你的O(n2)场景,极不可能。如果袜子的独特类型的数量t小于袜子对的数量p=n/2,并且每种类型的袜子都足够相似(通常在穿着相关的术语中),使得该类型的任何袜子都可以与任何其他袜子配对,那么正如我上面所推断的,你必须与之进行比较的袜子的最大数量是t,之后你拉动的下一只袜子将与未配对的袜子之一相匹配。这种情况在普通袜子抽屉中比在最坏情况下更可能发生,并将最坏情况的复杂性降低到O(n*t),其中通常t<<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:每次你把脏袜子放进洗衣篮时,把它们打个小结。这样你就不用在洗完衣服后做任何分类了。把它想象成在Mongo数据库中注册索引。未来需要做一些工作来节省CPU。

解决方案2:如果是冬天,你不必穿配套的袜子。我们是程序员。没有人需要知道,只要它有效。

解决方案3:分散工作。您希望异步执行如此复杂的CPU进程,而不阻塞UI。把那堆袜子塞进袋子里。只有在你需要的时候才找一双。这样,你的工作量就不那么明显了。

希望这有帮助!

作为实际解决方案:

快速制作一堆易于区分的袜子。(用颜色表示)快速整理每一堆,并使用袜子的长度进行比较。作为一个人,你可以很快地决定用哪只袜子进行分区,以避免最坏的情况。(你可以看到多只袜子平行排列,这对你有利!)当垃圾堆达到一个阈值时,停止分类,在该阈值下,您可以立即找到不合适的袜子和短袜

如果你有1000只袜子,有8种颜色,平均分布,你可以在c*n时间内每125只袜子做4堆。以5只袜子为阈值,你可以在6次跑步中对每一堆袜子进行分类。(数2秒把袜子扔到正确的堆上,只需要不到4小时。)

如果你只有60只袜子、3种颜色和2种袜子(你/你妻子的),你可以在1次跑步中对每一堆10只袜子进行分类(同样阈值=5)。(数2秒,需要2分钟)。

最初的桶排序将加快您的进程,因为它在c*n时间内将n个袜子分成k个桶,因此您只需执行c*n*log(k)工作。(不考虑阈值)。所以,你所做的所有关于n*c*(1+log(k))的工作,其中c是把袜子扔在一堆上的时间。

与任何c*x*n+O(1)方法相比,只要log(k)<x-1,该方法将是有利的。


在计算机科学中,这可能很有用:我们有一个n个事物的集合,它们的顺序(长度)和等价关系(额外的信息,例如袜子的颜色)。等价关系允许我们对原始集合进行分区,并且在每个等价类中我们的顺序仍然保持不变。一个事物到它的等价类的映射可以在O(1)中完成,因此只需要O(n)就可以将每个项分配给一个类。现在我们已经使用了额外的信息,可以以任何方式对每个类进行排序。其优点是数据集已经明显更小。

该方法也可以嵌套,如果我们有多个等价关系->使颜色堆积,而不是在纹理上的每个堆积分区内,而不是按长度排序。任何等价关系如果创建一个分区,其中包含2个以上的元素,且大小大致相等,那么与排序相比,排序的速度都会有所提高(前提是我们可以直接将袜子分配给它的堆),并且排序可以在较小的数据集上快速进行。

Defant&Kravitz(1)给出了一种算法,通过将袜子依次放在脚上和脚下来对袜子进行排序。

他们的算法适用于任意数量的英尺。

本文给出了(定理1.1)可使用单脚排序的袜子订单的特征。从他们的定理1.3可以看出,每一个4种颜色的袜子订单最多可以用两只脚进行排序,而有5种颜色的袜订单不可能用两只脚排序。

Colin Defant和Noah Kravitz,袜子足部分类(2022)