昨天,我在洗衣服时把袜子配对,结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子,然后“反复”寻找那一双袜子。这需要平均在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毫秒

其他回答

当我对袜子进行排序时,我会进行近似基数排序,将袜子放在同一颜色/图案类型的其他袜子附近。除非在我即将放下袜子的地方/附近,我能看到一对完全匹配的袜子,否则我会在那一刻取出这双袜子。

几乎所有其他算法(包括usr评分最高的答案)排序,然后删除配对。我发现,作为一个人,一次考虑的袜子数量最好尽量减少。

我通过以下方式做到这一点:

挑选一只与众不同的袜子(在袜子堆里最先映入我眼帘的东西)。从概念位置开始基数排序,根据与该位置的相似性从堆中拉出袜子。将新袜子放在当前袜子堆的附近,距离取决于它的不同程度。如果你发现自己将袜子放在另一只袜子的上面,因为它是相同的,请在那里形成一对,然后将它们取下。这意味着未来的比较需要更少的努力来找到正确的位置。

这利用了人类在O(1)时间内进行模糊匹配的能力,这在某种程度上相当于在计算设备上建立哈希图。

通过先穿上与众不同的袜子,你可以留出空间来“放大”那些不那么与众不同的特征。

在去除了浅色、条纹袜子和三双长袜之后,你可能最终会得到大致按磨损程度分类的白色袜子。

在某种程度上,袜子之间的差异很小,以至于其他人不会注意到差异,因此不需要进一步的匹配。

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

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

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

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

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

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

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


更新:

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

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

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

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

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

非算法答案,但当我这样做时“高效”:

步骤1)丢弃所有现有袜子第2步)去沃尔玛买10-n包的白色和m包黑色。日常无需其他颜色生活

然而,有时,我不得不再次这样做(丢失的袜子、损坏的袜子等),我讨厌太频繁地丢弃完美的袜子(我希望他们继续出售相同的袜子参考!),所以我最近采取了不同的方法。

算法答案:

考虑一下,如果你只为第二叠袜子画一只袜子,就像你正在做的那样,你在天真的搜索中找到匹配袜子的几率很低。

所以,随机挑选其中五个,记住它们的形状或长度。

为什么是五?通常情况下,人类在工作记忆中记住五到七个不同的元素是很好的——有点像RPN堆栈的人类等价物——五个是安全的默认值。

从2n-5的堆栈中选择一个。现在,在你画的五个图案中寻找一个匹配(视觉模式匹配-人类擅长用一个小堆栈),如果你没有找到一个,那么把它添加到你的五个。继续从袜子堆中随机挑选袜子,并与你的5+1袜子进行比较。随着堆栈的增长,它会降低性能,但会提高赔率。快得多。

请随意写下公式,以计算50%的匹配几率需要抽取多少样本。IIRC这是一个超几何定律。

我每天早上都会这样做,很少需要三次以上的平局——但我有n双类似的m形白袜子(大约10双,不分输赢)。现在你可以估计我的股票堆的大小:-)

顺便说一句,我发现,每次我需要一双袜子时,整理所有袜子的交易成本之和远远少于一次整理和装订袜子。准时制的效果更好,因为这样你就不必绑袜子了,而且边际回报也在减少(也就是说,当你在洗衣店的某个地方时,你一直在寻找那两到三只袜子,而你需要完成袜子的搭配,而你却在这上面浪费了时间)。

List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();

foreach (Sock newSock in UnsearchedSocks)
{
  Sock MatchedSock = null;
  foreach(Sock UnmatchedSock in UnmatchedSocks)
  {
    if (UnmatchedSock.isPairOf(newSock))
    {
      MatchedSock = UnmatchedSock;
      break;
    }
  }
  if (MatchedSock != null)
  {
    UnmatchedSocks.remove(MatchedSock);
    PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock));
  }
  else
  {
    UnmatchedSocks.Add(NewSock);
  }
}

一种有效的袜子配对算法

前提条件

堆里必须至少有一只袜子桌子必须足够大,以容纳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;
}