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

对于第二种情况，我想指出一个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;
}