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

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

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

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

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

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

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

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

整理n双袜子的问题是O（n）。在你把它们扔进洗衣篮之前，你先把左边的衣服穿到右边的衣服上。取出时，你剪下线，把每一对线放进抽屉里——对n对线进行2次操作，所以O（n）。

现在，下一个问题很简单，你是自己洗衣服，还是妻子洗衣服。这可能是一个完全不同领域的问题。：）

考虑大小为“N”的哈希表。

如果我们假设正态分布，那么至少有一个袜子映射到一个存储桶的估计“插入”数量为NlogN（即，所有存储桶都已满）

我将此作为另一个谜题的一部分，但我很乐意被证明是错误的。这是我的博客文章

让“N”对应于袜子独特颜色/图案数量的近似上限。

一旦发生碰撞（也就是火柴），只需脱掉那双袜子。对下一批NlogN袜子重复相同的实验。它的美妙之处在于，由于人类思维的方式，你可以进行NlogN并行比较（冲突解决）

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

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

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

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

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

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

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

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