为了说明从一堆袜子中配对有多有效，我们必须首先定义机器，因为配对不是通过图灵或随机存取机器完成的，而随机存取机器通常用作算法分析的基础。

机器

机器是被称为人类的现实世界元素的抽象。它能够通过一双眼睛从环境中阅读。我们的机器模型能够通过使用两个手臂来操纵环境。逻辑和算术运算是用我们的大脑计算的（希望是；-）。

我们还必须考虑可以使用这些仪器执行的原子操作的内在运行时间。由于物理限制，由手臂或眼睛执行的操作具有非恒定的时间复杂性。这是因为我们不能用手臂移动一大堆无穷无尽的袜子，也不能用眼睛看到一大堆袜子上的袜子。

然而，机械物理学也给了我们一些好处。我们不限于用手臂移动最多一只袜子。我们可以一次移动两个。

因此，根据之前的分析，应按降序使用以下操作：

逻辑和算术运算环境读数环境改造

我们还可以利用这样一个事实，即人们只有非常有限的袜子。因此，环境改造可能涉及到所有袜子。

算法

我的建议是：

把袜子堆里的袜子都铺在地板上。通过看地板上的袜子找到一双。从2开始重复，直到无法配对。从1开始重复，直到地板上没有袜子。

操作4是必要的，因为当将袜子铺在地板上时，一些袜子可能会隐藏其他袜子。算法分析如下：

分析

该算法以高概率终止。这是由于在第二步中找不到袜子。

对于以下对n双袜子配对的运行时分析，我们假设在步骤1之后，至少有一半的2n双袜子没有隐藏。所以在平均情况下，我们可以找到n/2对。这意味着步骤4的循环执行了O（logn）次。步骤2执行O（n^2）次。因此，我们可以得出结论：

该算法涉及O（lnn+n）环境修改（步骤1 O（lnn）加上从地板上挑选每双袜子）该算法涉及步骤2中的O（n^2）个环境读数该算法包括O（n^2）个逻辑和算术运算，用于在步骤2中比较袜子和另一袜子

因此，我们的总运行时复杂度为O（r*n^2+w*（lnn+n）），其中r和w分别是合理数量袜子的环境读取和环境写入操作的因素。省略了逻辑运算和算术运算的成本，因为我们假设需要恒定数量的逻辑运算和算数运算来决定2只袜子是否属于同一对。这可能在每种情况下都不可行。

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);
  }
}

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

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

一种有效的袜子配对算法

前提条件

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

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

对于第二种情况，我想指出一个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（移动袜子）和搜索（搜索袜子的行）的速度，所花费的时间要少得多。