我刚刚完成袜子配对，我发现最好的方法是：

选择一只袜子并将其收起来（为这双袜子创建一个“水桶”）如果下一个是上一个的一对，则将其放到现有的存储桶中，否则创建一个新的存储桶。

在最坏的情况下，这意味着您将有n/2个不同的存储桶，并且您将有n-2个关于哪个存储桶包含当前袜子的确定。显然，如果你只有几对，这个算法会很好地工作；我用了12双鞋。

它不是那么科学，但它工作得很好：）

真实世界方法：

尽快将袜子从未分类的袜子堆中取出，一次一个，然后放在前面。桩应布置得有一定的空间效率，所有袜子指向相同的方向；桩的数量受你容易到达的距离的限制。选择一堆袜子时，应尽快将袜子放在一堆看起来很像的袜子上；偶尔出现的I型（把袜子放在不属于它的袜子堆上）或II型（当有一堆类似的袜子时，把袜子放进自己的袜子堆里）错误是可以容忍的——最重要的考虑是速度。

一旦所有袜子都成了一堆，快速穿过多个袜子堆，创建成对的袜子，然后将它们取下（这些袜子朝抽屉方向）。如果袜子堆中有不匹配的袜子，请将它们重新堆到最好的位置（在尽可能快的限制范围内）。当处理完所有的多袜子堆后，将由于II类错误而未配对的剩余可配对袜子进行配对。哎呦，你完了——我有很多袜子，直到大部分都脏了才洗。另一个实际注意事项是：我将一双袜子的顶部翻转到另一双袜子上，利用它们的弹性财产，以便它们在被运送到抽屉和抽屉中时保持在一起。

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

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

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

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

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

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

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

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

机器

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

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

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

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

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

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

算法

我的建议是：

把袜子堆里的袜子都铺在地板上。通过看地板上的袜子找到一双。从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只袜子是否属于同一对。这可能在每种情况下都不可行。

你试图解决错误的问题。

解决方案1：每次你把脏袜子放进洗衣篮时，把它们打个小结。这样你就不用在洗完衣服后做任何分类了。把它想象成在Mongo数据库中注册索引。未来需要做一些工作来节省CPU。

解决方案2：如果是冬天，你不必穿配套的袜子。我们是程序员。没有人需要知道，只要它有效。

解决方案3：分散工作。您希望异步执行如此复杂的CPU进程，而不阻塞UI。把那堆袜子塞进袋子里。只有在你需要的时候才找一双。这样，你的工作量就不那么明显了。

希望这有帮助！