帖子

目前显示的是 九月, 2016的博文

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.

upd…

Torch的tensor

Torch中的tensor是一个n维数组,它是torch最基础最重要的组件。
下面这段代码演示如何通过下标来访问tensor。这段代码首先,初始化一个长度为10的1维数组,将其内容填充成0,1,2...9,然后遍历这个tensor,将其内容打印出来。
#include "TH/TH.h" #define Real Double #define real double int main() { THTensor* tensor1 = THTensor_(newWithSize1d)(10); for (int64_t i = 0; i != 10; ++i) { THTensor_(set1d)(tensor1, i, (real)i); } for (int i = 0; i != 10; ++i) { printf("%g ", THTensor_(get1d)(tensor1, i)); } printf("\n"); THTensor_(free)(tensor1); return 0; } 输出应该是:
0 1 2 3 4 5 6 7 8 9
使用下标来访问tensor有两种方式,上面这种是通过set/get函数,比较慢。更快的方式是这样。
#include "TH/TH.h" #define Real Double #define real double int main() { THTensor* tensor1 = THTensor_(newWithSize1d)(10); int i = 0; TH_TENSOR_APPLY(real, tensor1, *tensor1_data = (real)i; ++i;); for (int i = 0; i != 10; ++i) { printf("%g ", THTensor_(get1d)(tensor1, i)); } printf("\n"); THTensor_(free)(tensor1); return 0; } TH_TENSOR_APPLY是一个宏,在TH/THTensorApply.h中声…

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

我想给我的电脑前贴个条子:“少写代码,多读别人写的代码”
想要成为一个优秀的程序员真的很不容易。
不是说天天读英语听英语,英语水平就会好。只有在刻意学习的时候,才会有收获。
同样的,不是说天天专心写代码,coding能力就会渐涨。除非刻意的想要提高自己,否则,不出几年就会达到自身的瓶颈。
我才多大啊,比我老练的程序员多了去了,如大海里的沙子。
要天天牢记自己是个渣滓,督促自己少写代码,只写必要的。因为写了就得有人维护,就算自己不嫌累,也不要给别人添麻烦添负担。