昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
考虑大小为“N”的哈希表。
如果我们假设正态分布，那么至少有一个袜子映射到一个存储桶的估计“插入”数量为NlogN（即，所有存储桶都已满）
我将此作为另一个谜题的一部分，但我很乐意被证明是错误的。这是我的博客文章
让“N”对应于袜子独特颜色/图案数量的近似上限。
一旦发生碰撞（也就是火柴），只需脱掉那双袜子。对下一批NlogN袜子重复相同的实验。它的美妙之处在于，由于人类思维的方式，你可以进行NlogN并行比较（冲突解决）
其他回答
我所做的就是拿起第一只袜子，把它放下（比如，放在洗衣碗的边缘）。然后我拿起另一只袜子，检查它是否与第一只袜子相同。如果是，我会把它们都去掉。如果不是，我把它放在第一只袜子旁边。然后我拿起第三只袜子，将其与前两只袜子进行比较（如果它们还在的话）。等
这种方法可以很容易地在阵列中实现，假设“移除”袜子是一个选项。实际上，你甚至不需要“脱掉”袜子。如果您不需要对袜子进行排序（见下文），那么您只需移动它们，就可以得到一个数组，该数组中所有袜子都成对排列。
假设袜子的唯一操作是比较相等，这个算法基本上仍然是n2算法，尽管我不知道平均情况（从未学会计算）。
当然，分类可以提高效率，尤其是在现实生活中，你可以很容易地将袜子“插入”在另外两个袜子之间。在计算中，树也可以做到这一点，但这是额外的空间。当然，我们又回到了NlogN（或者更多，如果有几只袜子按排序标准是相同的，但不是来自同一双）。
除此之外，我想不出什么，但这种方法在现实生活中似乎非常有效
理论上的限制是O（n），因为你需要触摸每一只袜子（除非有些袜子已经配对）。
你可以用基数排序实现O（n）。你只需要为桶选择一些属性。
首先你可以选择（她的，我的）-把它们分成两堆，然后使用颜色（可以有任何颜色的顺序，例如按颜色名称的字母顺序）-按颜色将它们分成一堆（记住对同一堆中的所有袜子保持步骤1中的初始顺序），然后袜子的长度，然后是纹理，....
如果您可以选择有限数量的属性，但有足够多的属性可以唯一地标识每对属性，则应该使用O（k*n），如果我们可以考虑k是有限的，则使用O（n）。
考虑大小为“N”的哈希表。
如果我们假设正态分布，那么至少有一个袜子映射到一个存储桶的估计“插入”数量为NlogN（即，所有存储桶都已满）
我将此作为另一个谜题的一部分，但我很乐意被证明是错误的。这是我的博客文章
让“N”对应于袜子独特颜色/图案数量的近似上限。
一旦发生碰撞（也就是火柴），只需脱掉那双袜子。对下一批NlogN袜子重复相同的实验。它的美妙之处在于，由于人类思维的方式，你可以进行NlogN并行比较（冲突解决）
这是基于比较的模型中的Omega（n log n）下限。（唯一有效的操作是比较两只袜子。）
假设你知道你的2n只袜子是这样排列的：
p1 p2 p3。。。pn pf（1）pf（2）。。。功率因数（n）
其中f是集合{1,2，…，n}的未知排列。知道这一点不会使问题变得更难。有n个！可能的输出（上半部分和下半部分之间的匹配），这意味着您需要log（n！）=Omega（n log n）比较。这可通过分类获得。
由于您对元素区别性问题的连接感兴趣：证明元素区别性的Omega（n log n）界限比较困难，因为输出是二进制的yes/no。这里，输出必须是匹配的，并且可能输出的数量足以获得一个合适的界限。然而，有一个变量与元素的区别有关。假设你有2n只袜子，想知道它们是否可以唯一配对。您可以通过将（a1，a2，…，an）发送到（a1，a1，a2、a2，…、an，an）来获得ED的缩减。（附带地，通过拓扑结构，ED的硬度证明非常有趣。）
我认为，如果只允许等式测试，那么原始问题应该有一个Omega（n2）边界。我的直觉是：考虑一个测试后添加边的图形，并认为如果图形不密集，则输出不是唯一确定的。
两种思路，查找任何匹配项所需的速度，与查找所有匹配项所需要的速度相比，与存储相比。
对于第二种情况，我想指出一个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毫秒
