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

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

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

因此,问题基本上是:

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

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

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


当前回答

袜子,无论是真的还是类似的数据结构,都将成对提供。

最简单的答案是,在允许袜子对分开之前,应该初始化袜子对的单个数据结构,该结构包含指向左右袜子的指针,从而可以直接或通过袜子对引用袜子。袜子也可以扩展为包含指向其伙伴的指针。

这通过使用抽象层来消除任何计算配对问题。

将同样的想法应用于袜子配对的实际问题,显而易见的答案是:不要让你的袜子不配对。袜子是一双提供的,一双放在抽屉里(也许是把它们捆在一起),一双穿。但可能脱漆的地方是在洗衣机里,所以所需要的只是一个物理机制,让袜子保持在一起并有效地清洗。

有两种物理可能性:

对于一个“pair”对象,它保持指向每只袜子的指针,我们可以使用一个布袋来将袜子放在一起。这似乎是巨大的开销。

但是,为了让每一只袜子都能互相参照,有一个很好的解决方案:一个popper(如果你是美国人,可以使用“按扣”),比如:

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

然后,你所做的就是在脱下袜子并将其放进洗衣篮后立即将袜子扣在一起,再次消除了需要用“配对”概念的物理抽象来对袜子进行配对的问题。

其他回答

我所做的就是拿起第一只袜子,把它放下(比如,放在洗衣碗的边缘)。然后我拿起另一只袜子,检查它是否与第一只袜子相同。如果是,我会把它们都去掉。如果不是,我把它放在第一只袜子旁边。然后我拿起第三只袜子,将其与前两只袜子进行比较(如果它们还在的话)。等

这种方法可以很容易地在阵列中实现,假设“移除”袜子是一个选项。实际上,你甚至不需要“脱掉”袜子。如果您不需要对袜子进行排序(见下文),那么您只需移动它们,就可以得到一个数组,该数组中所有袜子都成对排列。

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

当然,分类可以提高效率,尤其是在现实生活中,你可以很容易地将袜子“插入”在另外两个袜子之间。在计算中,树也可以做到这一点,但这是额外的空间。当然,我们又回到了NlogN(或者更多,如果有几只袜子按排序标准是相同的,但不是来自同一双)。

除此之外,我想不出什么,但这种方法在现实生活中似乎非常有效

每当你拿起袜子时,把它放在一个地方。然后你拿起的下一只袜子,如果它与第一只袜子不匹配,就把它放在第一只袜子旁边。如果是,那就有一对。这样,有多少种组合其实并不重要,而且你挑选的每一只袜子只有两种可能——要么它已经在你的袜子数组中匹配,要么它没有匹配,这意味着你将它添加到数组中的一个位置。

这也意味着你几乎肯定不会把所有袜子都放在阵列中,因为袜子会在搭配时被取下。

袜子,无论是真的还是类似的数据结构,都将成对提供。

最简单的答案是,在允许袜子对分开之前,应该初始化袜子对的单个数据结构,该结构包含指向左右袜子的指针,从而可以直接或通过袜子对引用袜子。袜子也可以扩展为包含指向其伙伴的指针。

这通过使用抽象层来消除任何计算配对问题。

将同样的想法应用于袜子配对的实际问题,显而易见的答案是:不要让你的袜子不配对。袜子是一双提供的,一双放在抽屉里(也许是把它们捆在一起),一双穿。但可能脱漆的地方是在洗衣机里,所以所需要的只是一个物理机制,让袜子保持在一起并有效地清洗。

有两种物理可能性:

对于一个“pair”对象,它保持指向每只袜子的指针,我们可以使用一个布袋来将袜子放在一起。这似乎是巨大的开销。

但是,为了让每一只袜子都能互相参照,有一个很好的解决方案:一个popper(如果你是美国人,可以使用“按扣”),比如:

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

然后,你所做的就是在脱下袜子并将其放进洗衣篮后立即将袜子扣在一起,再次消除了需要用“配对”概念的物理抽象来对袜子进行配对的问题。

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

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

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

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

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

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

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


更新:

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

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

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

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

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

一种有效的袜子配对算法

前提条件

堆里必须至少有一只袜子桌子必须足够大,以容纳N/2袜子(最坏情况),其中N是总数袜子。

算法

Try:

挑选第一只袜子把它放在桌子上选择下一只袜子,然后看看它(可能会把“不再有袜子”扔到袜子堆里)现在扫描桌子上的袜子(如果桌子上没有袜子,则抛出异常)有匹配的吗?a) 是=>从桌子上取下匹配的袜子b) no=>将袜子放在桌子上(可能会抛出“桌子不够大”异常)

除了:

桌子不够大:小心地将所有未配对的袜子混合在一起,然后继续操作//此操作将导致一个新的堆和一个空表桌子上没有袜子:扔(最后一只不受欢迎的袜子)堆里没有袜子:出口洗衣房

最后:

如果袜子堆里还有袜子:转到3

已知问题

如果或周围没有表,算法将进入无限循环桌子上没有足够的地方容纳至少一只袜子。

可能的改进

根据要分拣的袜子数量,吞吐量可能是通过整理桌子上的袜子来增加空间

为了使其工作,需要一个具有唯一每双袜子的价值。这样的属性很容易根据袜子的视觉财产合成。

按所述属性对桌上的袜子进行排序。让我们调用该属性“颜色”。将袜子排成一排,并将深色袜子放在右侧(即push_back()),左侧(即。.push_front())

对于大量的袜子,尤其是以前看不见的袜子,属性合成可能需要很长时间,因此吞吐量将明显下降。但是,这些属性可以保存在内存中并重用。

需要进行一些研究来评估这种可能性的效率改善出现以下问题:

上述袜子的最佳搭配数量是多少改善对于给定数量的袜子,之前需要多少次迭代吞吐量增加?a) 用于最后一次迭代b) 对于所有迭代

符合MCVE指南的PoC:

#include <iostream>
#include <vector>
#include <string>
#include <time.h>

using namespace std;

struct pileOfsocks {
    pileOfsocks(int pairCount = 42) :
        elemCount(pairCount<<1) {
        srand(time(NULL));
        socks.resize(elemCount);

        vector<int> used_colors;
        vector<int> used_indices;

        auto getOne = [](vector<int>& v, int c) {
            int r;
            do {
                r = rand() % c;
            } while (find(v.begin(), v.end(), r) != v.end());
            v.push_back(r);
            return r;
        };

        for (auto i = 0; i < pairCount; i++) {
            auto sock_color = getOne(used_colors, INT_MAX);
            socks[getOne(used_indices, elemCount)] = sock_color;
            socks[getOne(used_indices, elemCount)] = sock_color;
        }
    }

    void show(const string& prompt) {
        cout << prompt << ":" << endl;
        for (auto i = 0; i < socks.size(); i++){
            cout << socks[i] << " ";
        }
        cout << endl;
    }

    void pair() {
        for (auto i = 0; i < socks.size(); i++) {
            std::vector<int>::iterator it = find(unpaired_socks.begin(), unpaired_socks.end(), socks[i]);
            if (it != unpaired_socks.end()) {
                unpaired_socks.erase(it);
                paired_socks.push_back(socks[i]);
                paired_socks.push_back(socks[i]);
            }
            else
                unpaired_socks.push_back(socks[i]);
        }

        socks = paired_socks;
        paired_socks.clear();
    }

private:
    int elemCount;
    vector<int> socks;
    vector<int> unpaired_socks;
    vector<int> paired_socks;
};

int main() {
    pileOfsocks socks;

    socks.show("unpaired socks");
    socks.pair();
    socks.show("paired socks");

    system("pause");
    return 0;
}