昨天,我在洗衣服时把袜子配对,结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子,然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。

作为一名计算机科学家,我在想我能做什么?排序(根据大小/颜色/…)当然是为了实现O(NlogN)解决方案。

哈希或其他不到位的解决方案是不可选择的,因为我无法复制我的袜子(如果可以的话,这可能很好)。

因此,问题基本上是:

给定一堆n双袜子,其中包含2n个元素(假设每只袜子正好有一对匹配的袜子),用对数的额外空间高效地将它们配对的最佳方式是什么?(如果需要的话,我相信我可以记住这些信息。)

我将感谢回答以下方面的问题:

大量袜子的一般理论解。袜子的实际数量没有那么多,我不相信我的配偶和我有超过30双。(而且很容易区分我的袜子和她的袜子;这也可以用吗?)它是否等同于元素清晰度问题?


当前回答

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

其他回答

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

对于第二种情况,我想指出一个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(或者更多,如果有几只袜子按排序标准是相同的,但不是来自同一双)。

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

理论上的限制是O(n),因为你需要触摸每一只袜子(除非有些袜子已经配对)。

你可以用基数排序实现O(n)。你只需要为桶选择一些属性。

首先你可以选择(她的,我的)-把它们分成两堆,然后使用颜色(可以有任何颜色的顺序,例如按颜色名称的字母顺序)-按颜色将它们分成一堆(记住对同一堆中的所有袜子保持步骤1中的初始顺序),然后袜子的长度,然后是纹理,....

如果您可以选择有限数量的属性,但有足够多的属性可以唯一地标识每对属性,则应该使用O(k*n),如果我们可以考虑k是有限的,则使用O(n)。

我提出了另一个解决方案,它不会承诺更少的操作,也不会减少时间消耗,但应该尝试看看它是否能成为一个足够好的启发式方法,在大量袜子配对中提供更少的时间消耗。

前提条件:不能保证有相同的袜子。如果它们的颜色相同,并不意味着它们的大小或图案相同。袜子随机洗牌。袜子的数量可能是奇数(有些不见了,我们不知道有多少)。准备记住一个变量“index”并将其设置为0。

结果将有一个或两个桩:1。“匹配”和2。“缺少”

启发式:

找到最与众不同的袜子。找到匹配项。如果没有匹配项,请将其放在“缺失”堆上。从1开始重复。直到没有最与众不同的袜子。如果袜子少于6只,请转到11只。盲目地将所有袜子与邻居配对(不要打包)找到所有匹配的对,将其打包并将打包的对移动到“匹配”的堆中;如果没有新的匹配项-将“索引”增加1如果“index”大于2(这可能取决于袜子的值因为袜子数量越多盲目配对)进入11打乱其余的转到1忘记“索引”挑选一只袜子查找其配对如果没有袜子,就把它移到“失踪”的那一堆如果找到匹配项,将其配对,将其打包并移动到“匹配”堆中如果还有不止一只袜子,那就去12只如果只剩下一个,请转到14满意的微笑:)

此外,还可以添加检查袜子是否损坏,就像移除袜子一样。它可以插入2到3之间,13到14之间。

我期待听到任何经验或更正。

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