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

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

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

因此,问题基本上是:

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

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

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


当前回答

两种思路,查找任何匹配项所需的速度,与查找所有匹配项所需要的速度相比,与存储相比。

对于第二种情况,我想指出一个GPU并行版本,它查询所有匹配的袜子。

如果您有多个要匹配的财产,则可以使用分组元组和更高级的zip迭代器以及推力的转换函数,尽管这里是一个基于GPU的简单查询:

//test.cu
#include <thrust/device_vector.h>
#include <thrust/sequence.h>
#include <thrust/copy.h>
#include <thrust/count.h>
#include <thrust/remove.h>
#include <thrust/random.h>
#include <iostream>
#include <iterator>
#include <string>

// Define some types for pseudo code readability
typedef thrust::device_vector<int> GpuList;
typedef GpuList::iterator          GpuListIterator;

template <typename T>
struct ColoredSockQuery : public thrust::unary_function<T,bool>
{
    ColoredSockQuery( int colorToSearch )
    { SockColor = colorToSearch; }

    int SockColor;

    __host__ __device__
    bool operator()(T x)
    {
        return x == SockColor;
    }
};


struct GenerateRandomSockColor
{
    float lowBounds, highBounds;

    __host__ __device__
    GenerateRandomSockColor(int _a= 0, int _b= 1) : lowBounds(_a), highBounds(_b) {};

    __host__ __device__
    int operator()(const unsigned int n) const
    {
        thrust::default_random_engine rng;
        thrust::uniform_real_distribution<float> dist(lowBounds, highBounds);
        rng.discard(n);
        return dist(rng);
    }
};

template <typename GpuListIterator>
void PrintSocks(const std::string& name, GpuListIterator first, GpuListIterator last)
{
    typedef typename std::iterator_traits<GpuListIterator>::value_type T;

    std::cout << name << ": ";
    thrust::copy(first, last, std::ostream_iterator<T>(std::cout, " "));
    std::cout << "\n";
}

int main()
{
    int numberOfSocks = 10000000;
    GpuList socks(numberOfSocks);
    thrust::transform(thrust::make_counting_iterator(0),
                      thrust::make_counting_iterator(numberOfSocks),
                      socks.begin(),
                      GenerateRandomSockColor(0, 200));

    clock_t start = clock();

    GpuList sortedSocks(socks.size());
    GpuListIterator lastSortedSock = thrust::copy_if(socks.begin(),
                                                     socks.end(),
                                                     sortedSocks.begin(),
                                                     ColoredSockQuery<int>(2));
    clock_t stop = clock();

    PrintSocks("Sorted Socks: ", sortedSocks.begin(), lastSortedSock);

    double elapsed = (double)(stop - start) * 1000.0 / CLOCKS_PER_SEC;
    std::cout << "Time elapsed in ms: " << elapsed << "\n";

    return 0;
}

    //nvcc -std=c++11 -o test test.cu

1000万只袜子的运行时间:9毫秒

其他回答

成本:移动袜子->高,查找/搜索袜子排成一排->小

我们想做的是减少移动次数,并用搜索次数进行补偿。此外,我们还可以利用智人的多威胁环境,在解密缓存中保存更多的东西。

X=您的,Y=您的配偶

从所有袜子的A堆开始:

选择两个袜子,将相应的X袜子放在X线上,将Y袜子放在Y线上的下一个可用位置。

直到A为空。

对于每行X和Y

选择行中的第一只袜子,沿着行搜索,直到找到相应的袜子。放入相应的袜子成品线。可选当您搜索线条时,当前正在查看的袜子与之前的袜子相同,请对这些袜子执行步骤2。

可选地,在第一步中,您从该行中拾取两个袜子,而不是两个,因为缓存内存足够大,我们可以快速识别其中一个袜子是否与您正在观察的行上的当前袜子匹配。如果你有幸拥有三只手臂,那么考虑到受试者的记忆足够大,你可以同时解析三只袜子。

直到X和Y都为空。

Done

然而,由于这与选择排序具有相似的复杂性,由于I/O(移动袜子)和搜索(搜索袜子的行)的速度,所花费的时间要少得多。

创建一个哈希表,该表将用于不匹配的袜子,使用模式作为哈希。一只一只地重复袜子。如果袜子在哈希表中有图案匹配,请将袜子从表中取出并配对。如果袜子没有火柴,就把它放到桌子上。

从你的问题来看,你显然没有太多洗衣方面的实际经验:)。你需要一种算法,能很好地处理少量不可配对的袜子。

到目前为止,答案还没有充分利用我们的人类模式识别能力。集合游戏提供了如何做好这一点的线索:将所有袜子放在一个二维空间中,这样你就可以很好地识别它们,并用手轻松地够到它们。这将您的面积限制在120*80厘米左右。从那里选择您识别的配对并将其删除。将多余的袜子放在空闲空间,然后重复。如果你为穿着容易辨认的袜子的人洗衣服(脑海中浮现的是小孩子),你可以先选择袜子来进行基数排序。该算法仅在单袜子数量较少时有效

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

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

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

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

拿起第一只袜子放在桌子上。现在再挑一只袜子;如果它与第一个拾取的匹配,请将其放在第一个拾取上。如果没有,把它放在桌子上,离第一个小距离。挑选第三只袜子;如果它与前两个匹配,请将它放在它们的上面,或者将它放置在距离第三个的一小段距离处。重复上述步骤,直到你捡起所有袜子。