How to removes duplicate values from an array: A counterintuitive story of Big O

Everyone knows O(N) is faster than O(NlogN). However, sometimes, it isn't.
Please look at this example:

template <typename T>
size_t count_unique_elements_by_map(T* begin, T* end) {
  std::unordered_set<T> s(end - begin);
  s.insert(begin, end);
  return s.size();
}

template <typename T>
size_t count_unique_elements_by_sort(T* begin, T* end) {
  if (begin >= end) return 0;
  std::sort(begin, end);
  auto newEnd = std::unique(begin,end);
  return newEnd - begin;
}

Method 2 is faster than method 1 if duplicates are rare.

问题的背景是这样:我有一些ID,我想把这些ID对应的value查出来。这些value保存在一个分布式系统中(如memcached)。为了减少服务器的查询压力,我把这些ID先去重,然后计算每个ID在哪个服务器上,把ID按服务器分组,然后发送查询。最初我用了一个hash map做这件事情,然后我发现去重的操作所耗费的CPU远远超过其它代码(比如网络IO)。

然后我发现sort比hash更快,在我的场景下,快10倍以上。但是故事并未到此结束,当我收到服务器的reply之后,我还是得把这些ID以及value插入到一个hash map中。否则我就只能用binary search读取它们。所以,我还是得构建这个hash map,逃不掉的。

再后来我发现,如果把STL的hash map换成我自己写的一个基于open address方式的hash map,那么速度也能提升1倍左右。

Please tell me if you have any better solutions. Thanks.

update: 我刚想到,如果input id也是有序的,那么不用构建hash map。在有序数组中查找有序数组,算法复杂度还是O(N)。但是实际效果如何,有待验证。

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥