如何有效地配对袜子?

昨天我从干净的洗衣店里给袜子配对了,发现我做这件事的方式不是很有效。我一直在天真地搜寻 - 挑选一只袜子,然后 “反复” 寻找那双袜子。这需要遍历平均 N / 2 * N / 4 = N8 分之 2袜子。

作为计算机科学家,我在想我能做什么?当然会想到进行排序(根据大小 / 颜色 / ...)以实现 O(NlogN)解决方案。

不能选择散列或其他非现场解决方案,因为我无法复制袜子(尽管如果可以的话,可能会很好)。

因此,问题基本上是:

给定一堆n对袜子,其中包含2n元素(假设每只袜子具有一对完全匹配的袜子),最好的方法是将它们有效配对并具有对数的额外空间? (我相信我可以记住该信息的数量,如果需要的话。)

我希望能从以下几个方面回答这个问题:

  • 大量袜子的一般理论解决方案。
  • 袜子的实际数量不是很大,我不相信我的配偶和我有超过 30 对。 (而且很容易区分我的袜子和她的袜子;也可以使用吗?)
  • 它等同于元素区分性问题吗?

答案

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

因此散列就足够了(并且更快)。

  1. 对于每种颜色的袜子, 形成一堆 。遍历输入筐中的所有袜子并将它们分配到颜色堆上
  2. 遍历每个桩,并按其他度量 (例如图案)将其分配到第二组桩中
  3. 递归应用此方案,直到将所有袜子分配到很小的绒头上,然后即可立即进行视觉处理

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

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

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

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


更新:

那么并行性呢?可以让多个人更快地匹配袜子吗?

  1. 最简单的并行化策略是让多名工人从输入筐中取出并将袜子放在堆上。这只会扩展得如此之多 - 想象有 100 个人在战斗 10 堆。 同步成本 (表现为手动冲突和人际交流) 破坏了效率和速度 (请参阅《 通用可扩展性法则》 !)。这容易陷入僵局吗?否,因为每个工人一次只需要访问一堆。只有一个 “锁” 就不会出现死锁。取决于人类如何协调对堆的访问,可能会出现活锁 。他们可能只使用随机退避,就像网卡在物理级别上那样来确定哪些网卡可以独占访问网络线路。如果它适用于NIC ,它也应适用于人类。
  2. 如果每个工人都有自己的桩,它几乎可以无限扩展。然后,工人可以从进料篮中取出大块的袜子(很少有竞争,因为他们很少这样做),并且在分配袜子时根本不需要同步(因为他们有局部线程堆)。最后,所有工人都需要结合他们的桩具。我相信,如果工人形成一个聚合树 ,可以用 O(log(工人数 * 每个工人的堆数))来完成。

元素区分性问题呢?如文章所述,元素区别性问题可以在O(N)解决。对于袜子问题(如果只需要一个分配步骤,也是O(N) (我提议多个步骤仅是因为人类在计算上很差 - 如果您在md5(color, length, pattern, ...)分配一个md5(color, length, pattern, ...) ,即所有属性的完美哈希 ))。

显然,不能比O(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 :所有袜子都是一样的(顺便说一句,这是我在现实生活中所做的)。

选择其中任意两个配对。恒定的时间。

情况 2 :组合数量不变(所有权,颜色,大小,纹理等)。

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

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

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

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

非算法答案,但在执行时却 “有效”:

  • 步骤 1)丢弃所有现有的袜子

  • 步骤 2)前往沃尔玛(Walmart) ,以 10 包 - 白色 n 包和 m 黑色包的价格购买它们。日常生活中无需其他颜色。

但是有时候,我必须再次这样做(袜子丢失,袜子损坏等),而且我不想过多地丢弃完美的袜子(我希望他们继续出售相同的袜子参考!),所以我最近服用了一种不同的方法。

算法答案:

考虑一下,如果您像第二只袜子一样只抽出一只袜子,那么,在幼稚的搜索中找到匹配的袜子的几率很低。

  • 因此,随机挑选其中五个,并记住其形状或长度。

为什么是五个?通常,人类会记住在工作存储器中的五个到七个不同的元素(有点像RPN堆栈的人类等效元素),五个是安全的默认值。

  • 从 2n-5 的堆栈中取出一个。

  • 现在,在您绘制的五个对象中寻找一个匹配项(视觉模式匹配 - 人类擅长于一小堆),如果找不到,则将其添加到您的五个中。

  • 保持从堆栈中随机挑选袜子,并与您的 5 + 1 袜子进行比较。随着堆栈的增加,它会降低性能,但会增加赔率。快多了。

随意写下公式,以计算一场比赛有 50%的几率时必须抽取多少个样本。 IIRC 这是一个超几何定律。

我每天早上都这样做,很少需要超过 3 次抽奖 - 但我有n对类似的袜子(大约 10 对,输掉或丢掉了m字形的白色袜子)。现在您可以估计我的股票数量了:-)

顺便说一句 ,我发现每次我需要一双袜子对所有袜子进行分类的交易成本总和要比一次绑定袜子要少得多。即时作业会更好,因为这样您就不必束缚袜子了,边际收益也会递减(也就是说,当您在洗衣房中的某个地方并且需要时,您一直在寻找两三只袜子)完成与袜子的匹配,您会因此而浪费时间)。

我要做的是拿起第一只袜子放下(例如,放在洗衣盆的边缘)。然后,我拿起另一只袜子,检查它是否与第一只袜子相同。如果是,我将它们都删除。如果不是,我把它放到第一只袜子的旁边。然后,我拿起第三只袜子,并将其与前两只袜子进行比较(如果它们仍在那儿)。等等。

假设 “移除” 袜子是一种选择,则可以很容易地在阵列中实施此方法。实际上,您甚至不需要 “去除” 袜子。如果不需要对袜子进行排序(请参见下文),则只需将它们四处移动即可得到一个数组,该数组将所有袜子成对排列。

假设袜子的唯一操作是比较相等性,该算法基本上仍是 n 2算法,尽管我不知道平均情况(从未学会过计算)。

排序当然可以提高效率,特别是在现实生活中,您可以轻松地在另外两只袜子之间 “插入” 袜子。在计算中,一棵树可以实现相同的目的,但这是额外的空间。而且,当然,我们又回到了 NlogN(或者,如果有几只袜子的排序标准相同,但不是同一对袜子,则更多)。

除此之外,我什么也没想到,但是这种方法在现实生活中确实非常有效。 :)

这是在问一个错误的问题。正确的问题是,为什么我要花时间整理袜子?当您以所选的 X 个货币单位来评估您的空闲时间时,每年花费多少钱?

而且,这不仅是任何空闲时间,更是早上的空闲时间,您可能会在床上度过,或者喝着咖啡,或者早点离开,而不会被交通阻塞。

退后一步,想办法解决问题通常是很好的。

有办法!

找到你喜欢的袜子。考虑所有相关特征:不同照明条件下的颜色,整体质量和耐用性,不同气候条件下的舒适度以及气味吸收。同样重要的是,它们在存储时不应失去弹性,因此天然织物是不错的选择,并且应该采用塑料包装。

左脚袜子和右脚袜子之间最好没有差异,但这不是关键。如果袜子是左右对称的,则找到一对是 O(1)运算,对袜子进行排序是近似 O(M)运算,其中 M 是房子里放满袜子的地方数,最好是一些小常数。

如果您选择了左右袜子不同的花式对,则对左右脚桶进行完整的桶排序将取 O(N + M),其中 N 是袜子的数量,M 与上面的相同。其他人可以给出寻找第一个对的平均迭代的公式,但是用盲搜索找到对的最坏情况是 N / 2 + 1,这对于合理的 N 来说在天文学上是不可能的情况。这可以通过使用高级图像来加快Mk1 Eyeball扫描一堆未分类的袜子时,识别算法和启发式算法。

因此,用于实现 O(1)袜子配对效率(假设对称袜子)的算法为:

  1. 您需要估算一生中需要多少双袜子,或者直到您退休并转入温暖的气候,而无需再穿袜子。如果您还年轻,您还可以估计我们家中都将有多少个袜子分拣机器人需要花费多长时间,并且整个问题变得无关紧要。

  2. 您需要了解如何批量订购选定的袜子,价格多少以及它们如何交付。

  3. 订购袜子!

  4. 摆脱旧袜子。

备选步骤 3 将涉及比较这些年来一次购买几双相同数量或价格较便宜的袜子的成本,以及对袜子进行分拣的成本,但请注意:批量购买更便宜!另外,存储袜子的价值会随着股票价格的上涨而增加,这比许多投资所能带来的收益还要多。再有,这也有存储成本,但是袜子确实在壁橱的顶部架子上占用不了太多空间。

问题解决了。因此,只要知道自己在余生中每天都在节省金钱和时间,就可以买新袜子,扔掉 / 捐出旧袜子并过上幸福的生活。

理论极限是 O(n),因为您需要触摸每只袜子(除非有些袜子已经以某种方式配对)。

您可以使用基数排序实现 O(n)。您只需要为存储桶选择一些属性即可。

  1. 首先,您可以选择(她的,我的)- 将它们分成两堆,
  2. 然后使用颜色(颜色可以有任何顺序,例如按颜色名称的字母顺序)- 按颜色将它们分成绒头(记住,对于同一绒头中的所有袜子,请保持步骤 1 的初始顺序),
  3. 然后是袜子的长度
  4. 然后质地,....

如果可以选择数量有限的属性,但是有足够的属性可以唯一地标识每对,则应该用 O(k * n)表示,如果我们可以认为 k 是有限的,则应为 O(n)。

作为实际的解决方案:

  1. 快速堆起容易区分的袜子。 (按颜色说)
  2. 快速分类每堆,并使用袜子的长度进行比较。作为一个人,您可以做出一个相当快速的决定,以使用哪种袜子来进行分区以避免最坏的情况。 (您可以同时看到多只袜子,利用它来发挥自己的优势!)
  3. 当它们达到阈值时停止对堆进行分类,在该阈值下您可以轻松找到斑点对和不可配对的袜子

如果您有 1000 只袜子,有 8 种颜色并且平均分配,则您可以在 c * n 时间内将每 125 只袜子分成 4 堆。使用 5 根袜子的阈值,您可以在 6 次跑步中对每堆进行分类。 (用 2 秒钟的时间将袜子扔到正确的桩上,将花费您不到 4 小时的时间。)

如果您只有 60 只袜子,3 种颜色和 2 种袜子(您自己 / 您的妻子的袜子),则可以在 10 次运行中对每堆 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)就可以将每个项目分配给一个类。现在,我们已经使用了额外的信息,可以以任何方式对每个类进行排序。优点是数据集已经大大缩小了。

如果我们有多个等价关系 -> 创建颜色桩,则该方法也可以嵌套,而不是在纹理上的每个桩分区内,在长度上进行排序。任何等价关系创建的分区都具有两个以上大小相等的元素,将带来比排序更快的速度(前提是我们可以直接将袜子分配给它的堆),并且排序可以在较小的数据集上快速发生。

您正在尝试解决错误的问题。

解决方案 1:每次将脏袜子放入洗衣篮中时,请打一个小结。这样,您在清洗后就无需进行任何分类。可以将其视为在 Mongo 数据库中注册索引。未来需要做一些工作以节省一些 CPU。

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

解决方案 3:传播工作。您想异步执行这样一个复杂的 CPU 进程,而不阻塞 UI。把那堆袜子塞进袋子里。仅在需要时寻找一对。这样,所需的工作量就不那么明显了。

希望这可以帮助!

这个问题实际上是深层次的哲学。从本质上讲,这是人们解决问题的能力(我们大脑的 “湿软件”)是否等同于可以通过算法完成的功能。

袜子排序的一个明显算法是:

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

现在,这个问题中的计算机科学全都涉及步骤

  1. “如果 s 与 N 中的袜子 t 配对”。我们多快可以 “记住” 我们到目前为止所看到的?
  2. “从 N 删除 t” 和 “将 s 加到 N”。跟踪到目前为止我们所看到的东西有多昂贵?

人类将使用各种策略来实现这些目标。 人的记忆关联的 ,类似于哈希表,其中存储的值的特征集与相应的值本身配对。例如,“红色汽车” 的概念映射到一个人能够记住的所有红色汽车。具有完美记忆的人具有完美的映射。大多数人在这方面(以及其他大多数人)并不完美。关联地图的容量有限。映射可以哔哔了在各种情况下存在(一个啤酒太多),被记录在错误(“我虽然她的名字是贝蒂,不内蒂”),或者从来没有被覆盖,即使我们观察到的事实已经改变(“爸爸的当我们实际上知道他用红色的 Camaro 换来的时候,“汽车” 就唤起了 “橙色的火鸟”。

对于袜子,完美的召回意味着看着袜子s总是会产生其同级t的记忆,包括足够的信息(在熨衣板上的信息)可以在恒定的时间内定位t 。具有照片记忆的人可以在恒定时间内无故障地完成 1 和 2 的工作。

记忆欠佳的人可能会根据自己能力范围内的特征使用一些常识对等类:大小(爸爸,妈妈,婴儿),颜色(偏绿,偏红等),图案(菱形,浅色等) ,样式(鞋类,膝盖高等)。因此,熨衣板将分为几个部分。通常,这可以通过内存在固定时间内定位类别,但是随后需要通过类别 “存储桶” 进行线性搜索。

完全没有记忆力或想象力的人(对不起)只会将袜子放在一堆中,并对整个堆进行线性搜索。

有人建议,整齐的怪胎可能会使用数字标签来配对。这为总排序打开了方便之门,使人们可以使用与 CPU 可能完全相同的算法:二进制搜索,树,哈希等。

因此,“最佳” 算法取决于运行它的湿件 / 硬件 / 软件的质量,以及我们对成对施加总订单的 “作弊” 意愿。当然,“最佳” 算法是雇用世界上最好的袜子分类器:一个人或机器,可以通过不断的时间查找,插入,获取,快速存储大量 N 个袜子属性集到 1-1 关联内存中,并删除。这样的人和机器都可以采购。如果您有一只袜子,则可以在 O(N)时间内将所有袜子配对 N 对,这是最佳选择。总订单标签使您可以使用标准哈希来与人机或硬件计算机获得相同的结果。