Aug
16
为了扩展Python，我们可以[用C/C++编写模块](http://docs.python.org/2/extending/ )，但是这要求对Python的底层有足够的了解，包括Python对象模型、常用模块、引用计数等，门槛较高，且不方便利用现有的C库。而 [ctypes](http://docs.python.org/2/library/ctypes.html ) 则另辟蹊径，通过封装`dlopen/dlsym`之类的函数，并提供对C中数据结构的包装/解包，让Python能够加载动态库、导出其中的函数直接加以利用。
快速上手
-------
最简单的，我们可以从 libc 开始：
由于ctypes库能够直接处理 None, integers, longs, byte strings 和 unicode strings 类型的转换，因此在这里不需要任何额外的操作就能完成任务。（注意，最后一行的25是printf的返回值，标识输出了25个字符）
自己动手
-------
[这里](http://wolfprojects.altervista.org/articles/dll-in-c-for-python/)有一个最简单的例子——实现一个 `int sum(int a, int b)`：
编译之得到 foo.so:
$ gcc -fPIC -shared -o foo.so foo.c
然后在Python里头：
真是超级简单。
丰衣足食
-------
下面来个稍微复杂点的例子：反转一个字符串。尽管ctypes可以直接处理string的转换，但是你不能直接修改string里的内容，所以这里需要变通一下。可能的解决方案有两个：
1. 在foo.c里面malloc一点空间然后返回。这样可以不修改原string，但是却要考虑释放该空间的问题，不太好处理。
2. 让Python分配好空间，将原字符串拷贝进去，再让foo里面的函数来修改它。ctypes为这种方案提供了`create_string_buffer`这个函数，正适合。
那就让我们用方案2来实现它：
然后在Python里头：
这样就OK啦。
补充说明
-------
以上的操作都是在Linux下完成的，在Windows下基本上一致，除了windows不能直接load libc.so.6，而是应该找 msvcrt :
>>> libc = ctypes.cdll.msvcrt
或者直接导入文件
>>> libc = ctypes.CDLL("msvcr90.dll")
小结
-------
前面演示了ctypes库的简单使用，已经能够完成许多任务了；但是它可以完成更多的任务，包括操作更复杂的例如结构体、数组等C数据结构，具体的这里不细说了，可以参考详细的[官方文档](http://docs.python.org/2/library/ctypes.html)。
好了，就到这里。
快速上手
-------
最简单的，我们可以从 libc 开始：
felix021@ubserver:~/code$ python
Python 2.7.3 (default, Jul 5 2013, 08:39:51)
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import ctypes
>>> libc = ctypes.CDLL("libc.so.6")
>>> libc.printf("hello, %s! %d + %d = %d\n", "world", 1, 2, 3)
hello, world! 1 + 2 = 3
25
Python 2.7.3 (default, Jul 5 2013, 08:39:51)
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import ctypes
>>> libc = ctypes.CDLL("libc.so.6")
>>> libc.printf("hello, %s! %d + %d = %d\n", "world", 1, 2, 3)
hello, world! 1 + 2 = 3
25
由于ctypes库能够直接处理 None, integers, longs, byte strings 和 unicode strings 类型的转换，因此在这里不需要任何额外的操作就能完成任务。（注意，最后一行的25是printf的返回值，标识输出了25个字符）
自己动手
-------
[这里](http://wolfprojects.altervista.org/articles/dll-in-c-for-python/)有一个最简单的例子——实现一个 `int sum(int a, int b)`：
//file foo.c
#ifdef __WIN32
#define DLLEXPORT __declspec(dllexport)
#else
#define DLLEXPORT
#endif
DLLEXPORT int sum(int a, int b)
{
return a + b;
}
#ifdef __WIN32
#define DLLEXPORT __declspec(dllexport)
#else
#define DLLEXPORT
#endif
DLLEXPORT int sum(int a, int b)
{
return a + b;
}
编译之得到 foo.so:
$ gcc -fPIC -shared -o foo.so foo.c
然后在Python里头：
>>> foo = ctypes.CDLL("./foo.so")
>>> foo.sum(5, 3)
8
>>> foo.sum(5, 3)
8
真是超级简单。
丰衣足食
-------
下面来个稍微复杂点的例子：反转一个字符串。尽管ctypes可以直接处理string的转换，但是你不能直接修改string里的内容，所以这里需要变通一下。可能的解决方案有两个：
1. 在foo.c里面malloc一点空间然后返回。这样可以不修改原string，但是却要考虑释放该空间的问题，不太好处理。
2. 让Python分配好空间，将原字符串拷贝进去，再让foo里面的函数来修改它。ctypes为这种方案提供了`create_string_buffer`这个函数，正适合。
那就让我们用方案2来实现它：
//file foo.c
DLLEXPORT int reverse(char *str)
{
int i, j, t;
for (i = 0, j = strlen(str) - 1; i < j; i++, j--)
t = str[i], str[i] = str[j], str[j] = t;
return 0;
}
DLLEXPORT int reverse(char *str)
{
int i, j, t;
for (i = 0, j = strlen(str) - 1; i < j; i++, j--)
t = str[i], str[i] = str[j], str[j] = t;
return 0;
}
然后在Python里头：
>>> s = ctypes.create_string_buffer("hello world!")
>>> foo.reverse(s)
0
>>> print s.value
!dlrow olleh
>>> foo.reverse(s)
0
>>> print s.value
!dlrow olleh
这样就OK啦。
补充说明
-------
以上的操作都是在Linux下完成的，在Windows下基本上一致，除了windows不能直接load libc.so.6，而是应该找 msvcrt :
>>> libc = ctypes.cdll.msvcrt
或者直接导入文件
>>> libc = ctypes.CDLL("msvcr90.dll")
小结
-------
前面演示了ctypes库的简单使用，已经能够完成许多任务了；但是它可以完成更多的任务，包括操作更复杂的例如结构体、数组等C数据结构，具体的这里不细说了，可以参考详细的[官方文档](http://docs.python.org/2/library/ctypes.html)。
好了，就到这里。
Jul
30
简单地说，MPI 就是个并行计算框架，模型也很直接——就是多进程。和hadoop不同，它不提供计算任务的map和reduce，只提供了一套通信接口，需要程序员来完成这些任务；它也不提供冗余容错等机制，完全依赖于其下层的可靠性。但是因为把控制权几乎完全交给了程序员，所以有很大的灵活性，可以最大限度地榨取硬件性能。超级计算机上的运算任务，基本上都是使用MPI来开发的。
～ 下载编译安装：
现在貌似一般都用MPICH，开源的MPI库，可以从这里获取： http://www.mpich.org/ ，现在的最新版本是3.0.4，编译安装过程可以参考安装包里的README的说明，基本步骤如下（万恶的configure）：
$ wget http://www.mpich.org/static/downloads/3.0.4/mpich-3.0.4.tar.gz
$ tar zxf mpich-3.0.4.tar.gz
$ cd mpich-3.0.4
$ mkdir ~/mpich
$ ./configure --prefix=$HOME/mpich --disable-f77 --disable-fc 2>&1 | tee c.txt #我禁用了fortran的支持
$ make -j4 2>&1 | tee m.txt
$ make install 2>&1 | tee i.txt
$ echo 'export PATH=$PATH:~/mpich/bin' >> ~/.bashrc
下面给出三个例子，参考教程：http://wenku.baidu.com/view/ee8bf3390912a216147929f3.html （注：22页有BUG，它把 MPI_Comm_XXX 错写成了 MPI_Common_xxx //包括全大写版本，共四处），给出了MPI框架中最常用、最基础的6个API的例子。更复杂的API可以参考mpich的手册。这些例子只是简单地演示了MPI框架的使用；实际上在使用MPI开发并行计算的软件时，还需要考虑到很多方面的问题，这里就不展开说了（其实真相是我也不会-.-，有兴趣的话可以请教 @momodi 和 @dumbear 两位）。
1. 最简单的：Hello world
代码如下： hello.c
编译：
$ mpicc -o hello hello.c
运行：
$ mpiexec -n 4 ./hello
Hello world!
Hello world!
Hello world!
Hello world!
可以看到这里启动了4个进程。注意 -n 和 4 之间一定要有空格，否则会报错。
2. 进程间通信
MPI最基本的通信接口是 MPI_Send/MPI_Recv:
编译运行：
$ mpicc comm.c
$ mpiexec -n 4 ./a.out
I'm 0 of 4
from 1: hello from 1
from 2: hello from 2
I'm 1 of 4
I'm 2 of 4
from 3: hello from 3
I'm 3 of 4
3. 来个复杂点的：数数前1亿个自然数里有几个 雷劈数
代码后附，答案是97（真少），不过这不是重点，重点是MPI对硬件的利用率是怎样 :D
测试机器是 16核 AMD Opteron 6128HE @2GHz，32G内存
单进程（无MPI版本）：56.9s
4进程：15.3s
8进程：7.85s
12进程：5.35s
考虑到16核跑满可能会受到其他进程的影响（性能不稳定，4.2～4.9s），这个数据就不列进来比较了。
可以看出来，在这个例子里，因为通信、同步只有在计算完之后才有那么一点点，所以在SMP架构下，耗费的时间基本上是跟进程数成反比的，说明MPI框架对硬件性能的利用率还是相当高的。
具体代码如下：
～ 下载编译安装：
现在貌似一般都用MPICH，开源的MPI库，可以从这里获取： http://www.mpich.org/ ，现在的最新版本是3.0.4，编译安装过程可以参考安装包里的README的说明，基本步骤如下（万恶的configure）：
引用
$ wget http://www.mpich.org/static/downloads/3.0.4/mpich-3.0.4.tar.gz
$ tar zxf mpich-3.0.4.tar.gz
$ cd mpich-3.0.4
$ mkdir ~/mpich
$ ./configure --prefix=$HOME/mpich --disable-f77 --disable-fc 2>&1 | tee c.txt #我禁用了fortran的支持
$ make -j4 2>&1 | tee m.txt
$ make install 2>&1 | tee i.txt
$ echo 'export PATH=$PATH:~/mpich/bin' >> ~/.bashrc
下面给出三个例子，参考教程：http://wenku.baidu.com/view/ee8bf3390912a216147929f3.html （注：22页有BUG，它把 MPI_Comm_XXX 错写成了 MPI_Common_xxx //包括全大写版本，共四处），给出了MPI框架中最常用、最基础的6个API的例子。更复杂的API可以参考mpich的手册。这些例子只是简单地演示了MPI框架的使用；实际上在使用MPI开发并行计算的软件时，还需要考虑到很多方面的问题，这里就不展开说了（其实真相是我也不会-.-，有兴趣的话可以请教 @momodi 和 @dumbear 两位）。
1. 最简单的：Hello world
代码如下： hello.c
#include <stdio.h>
#include <mpi.h>
int main(int argc, char *argv[])
{
MPI_Init(&argc, &argv); //初始化MPI环境
printf("Hello world!\n");
MPI_Finalize(); //结束MPI环境
return 0;
}
#include <mpi.h>
int main(int argc, char *argv[])
{
MPI_Init(&argc, &argv); //初始化MPI环境
printf("Hello world!\n");
MPI_Finalize(); //结束MPI环境
return 0;
}
编译：
$ mpicc -o hello hello.c
运行：
$ mpiexec -n 4 ./hello
Hello world!
Hello world!
Hello world!
Hello world!
可以看到这里启动了4个进程。注意 -n 和 4 之间一定要有空格，否则会报错。
2. 进程间通信
MPI最基本的通信接口是 MPI_Send/MPI_Recv:
#include <stdio.h>
#include <mpi.h>
int main(int argc, char *argv[])
{
int myid, numprocs, source, msg_tag = 0;
char msg[100];
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &numprocs); //共启动几个进程
MPI_Comm_rank(MPI_COMM_WORLD, &myid); //当前进程的编号（0～n-1）
printf("I'm %d of %d\n", myid, numprocs);
if (myid != 0)
{
int len = sprintf(msg, "hello from %d", myid);
MPI_Send(msg, len, MPI_CHAR, 0, msg_tag, MPI_COMM_WORLD); //向id=0的进程发送信息
}
else
{
for (source = 1; source < numprocs; source++)
{
//从id=source的进程接受消息
MPI_Recv(msg, 100, MPI_CHAR, source, msg_tag, MPI_COMM_WORLD, &status);
printf("from %d: %s\n", source, msg);
}
}
MPI_Finalize();
return 0;
}
#include <mpi.h>
int main(int argc, char *argv[])
{
int myid, numprocs, source, msg_tag = 0;
char msg[100];
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &numprocs); //共启动几个进程
MPI_Comm_rank(MPI_COMM_WORLD, &myid); //当前进程的编号（0～n-1）
printf("I'm %d of %d\n", myid, numprocs);
if (myid != 0)
{
int len = sprintf(msg, "hello from %d", myid);
MPI_Send(msg, len, MPI_CHAR, 0, msg_tag, MPI_COMM_WORLD); //向id=0的进程发送信息
}
else
{
for (source = 1; source < numprocs; source++)
{
//从id=source的进程接受消息
MPI_Recv(msg, 100, MPI_CHAR, source, msg_tag, MPI_COMM_WORLD, &status);
printf("from %d: %s\n", source, msg);
}
}
MPI_Finalize();
return 0;
}
编译运行：
$ mpicc comm.c
$ mpiexec -n 4 ./a.out
I'm 0 of 4
from 1: hello from 1
from 2: hello from 2
I'm 1 of 4
I'm 2 of 4
from 3: hello from 3
I'm 3 of 4
3. 来个复杂点的：数数前1亿个自然数里有几个 雷劈数
代码后附，答案是97（真少），不过这不是重点，重点是MPI对硬件的利用率是怎样 :D
测试机器是 16核 AMD Opteron 6128HE @2GHz，32G内存
单进程（无MPI版本）：56.9s
4进程：15.3s
8进程：7.85s
12进程：5.35s
考虑到16核跑满可能会受到其他进程的影响（性能不稳定，4.2～4.9s），这个数据就不列进来比较了。
可以看出来，在这个例子里，因为通信、同步只有在计算完之后才有那么一点点，所以在SMP架构下，耗费的时间基本上是跟进程数成反比的，说明MPI框架对硬件性能的利用率还是相当高的。
具体代码如下：
#include <stdio.h>
#include <mpi.h>
int is_lp(long long x)
{
long long t = x * x, i = 10;
while (i < t)
{
long long l = t / i, r = t % i;
if (l + r == x)
return 1;
i *= 10;
}
return 0;
}
int main(int argc, char *argv[])
{
int myid, numprocs, source;
const int N = 100000000;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myid);
MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
printf("I'm %d of %d\n", myid, numprocs);
int start = myid * (N / numprocs), stop = (myid + 1) * (N / numprocs);
if (myid == numprocs - 1)
stop = N;
printf("start from %d to %d\n", start, stop);
int ans = 0, i;
for (i = start; i < stop; i++)
if (is_lp(i))
ans += 1;
printf("%d finished calculation with %d numbers\n", myid, ans);
if (myid != 0)
{
MPI_Send(&ans, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
}
else
{
int tmp;
for (source = 1; source < numprocs; source++)
{
MPI_Recv(&tmp, 1, MPI_INT, source, 0, MPI_COMM_WORLD, &status);
printf("from %d: %d\n", source, tmp);
ans += tmp;
}
printf("final ans: %d\n", ans);
}
MPI_Finalize();
return 0;
}
#include <mpi.h>
int is_lp(long long x)
{
long long t = x * x, i = 10;
while (i < t)
{
long long l = t / i, r = t % i;
if (l + r == x)
return 1;
i *= 10;
}
return 0;
}
int main(int argc, char *argv[])
{
int myid, numprocs, source;
const int N = 100000000;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myid);
MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
printf("I'm %d of %d\n", myid, numprocs);
int start = myid * (N / numprocs), stop = (myid + 1) * (N / numprocs);
if (myid == numprocs - 1)
stop = N;
printf("start from %d to %d\n", start, stop);
int ans = 0, i;
for (i = start; i < stop; i++)
if (is_lp(i))
ans += 1;
printf("%d finished calculation with %d numbers\n", myid, ans);
if (myid != 0)
{
MPI_Send(&ans, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
}
else
{
int tmp;
for (source = 1; source < numprocs; source++)
{
MPI_Recv(&tmp, 1, MPI_INT, source, 0, MPI_COMM_WORLD, &status);
printf("from %d: %d\n", source, tmp);
ans += tmp;
}
printf("final ans: %d\n", ans);
}
MPI_Finalize();
return 0;
}
Jul
29
nth_element是一个用烂了的面试题，09年的时候我也曾经跑过一点数据（回头一看好像有点不太对，那时候CPU有那么慢吗？应该是当时没有把读取数据的时间给去掉吧），昨天看到 从一道笔试题谈算法优化（上） 和 从一道笔试题谈算法优化（下） 这个系列，里面提到了从简单到复杂的6种算法，根据作者的说法，经过各种优化以后solution6达到了相当的效率。受到作者启发，我也想到了一种算法，于是花了些时间，把常用的几种算法实现了进行对比（包括对比stl里的nth_element）。
回到 nth_element 的问题：从 n 个数里头，找出其中的 top k （top可以是找最大 也可以是找最小）。简单起见，后面都以找最小为例。
那篇文章里的后面的3种算法和我的算法都是基于它的solution3进行优化的，所以先介绍一下solution3：
1. 将 n 个数的前 k 个拷贝出来
2. 找出这 k 个数的最大值 m
3. 对于每一个剩下的 n - k 个数 i ：如果 i 小于 m ，将 m 替换为 i ，然后再找出新的 k 个数中的最大值 m
4. 返回过滤后得到的 k 个数
虽然第3步的判断条件成立时，这一步是 O(k) 的复杂度，但是在大部分情况下，这个判断条件都不成立，所以它需要执行的次数很少（这种效果越往后越明显，因为 m 的值越来越小，可以滤掉更多的数）。但是对于极端情况（或者接近极端的情况）——如果数组完全是降序排列的话，那么这个条件每次都会成立，会导致算法退化成 O(n * m) ，性能就不可接受了。
solution4~6的优化我觉得读起来有点晦涩，有兴趣的同学可以自己去看，这里不展开说了。它们都存在算法退化的情况。
我的算法可能理解起来要简单些，基本思路是偷懒：把缓冲区设置为 2 * k ，在扫数组的时候，如果这个数比当前保留的最大值还要小，就把它塞进缓冲区，直到缓冲区塞满了，再排序、取最大值、删多余的数。
1. 开辟一个 2 × k 的临时数组 r
2. 将 N[1..k] 拷贝到 r[1..k]，并记录 r 的末尾 e = k + 1
3. 找出 r[1..k] 中的最大值 m
4. 对于每一个剩下的 n - k 个数 i：
4.1 如果 i 小于 m，将 m 塞到 r 的末尾 r[e]；e = e + 1
4.1.1 如果 e == 2×k（r被塞满了），对 r 进行排序，得出前k个数中的最大值；抛弃后面的k个数，e = k + 1
5. 对 r[1..e] 进行排序
6. 返回 r[1..k]
这个算法的实际效果很好，在 n = 1亿、k = 1万 的情况下，对于随机的n个数，4.1条件成立的次数通常只有十几次，几乎可以忽略，因此大约只需要扫描整个数组时间的2～3倍即可。
但是这个算法同样存在退化的问题：如果全都是倒序排列的话，也变成O(n*m)了。幸而解决方案也很简单：对这个数组进行 n / 100 次的随机化（考虑到随机化耗时也比较大，100这个数字是试了几次以后发现的合适值，不一定最优，但是都差不多了）：
p.s. 很不幸的是随机化这个方法对于solution3来说虽然提升也很明显，但是远远不够。solution4～6也不太行。
这里给出随机情况下和完全倒序情况下的性能对比吧（ubuntu 12.04 x86_64，i5 2400@3.1G）：
补充说明一下，nth_element算法在面试的时候可能给出的 n 会更大，以至于在内存中存不下，这时候通常会认为用堆来实现最好——因为只要O(k)的空间就可以搞定，而且最差时间复杂度是O(logk * n)，但是要注意logk的常数实际上是很大的，所以你可以看到前面的数据里 堆算法 的效率并不是最好的。事实上这里给出的所有算法（不考虑随机化的话）也都只需要O(k)的空间；如果需要随机化的话也很简单，分段处理，只要保证每段能在内存中保存下来就行了。
最后上代码存档（为了方便测试用了些全局变量，看起来可能有点挫）：
回到 nth_element 的问题：从 n 个数里头，找出其中的 top k （top可以是找最大 也可以是找最小）。简单起见，后面都以找最小为例。
那篇文章里的后面的3种算法和我的算法都是基于它的solution3进行优化的，所以先介绍一下solution3：
1. 将 n 个数的前 k 个拷贝出来
2. 找出这 k 个数的最大值 m
3. 对于每一个剩下的 n - k 个数 i ：如果 i 小于 m ，将 m 替换为 i ，然后再找出新的 k 个数中的最大值 m
4. 返回过滤后得到的 k 个数
虽然第3步的判断条件成立时，这一步是 O(k) 的复杂度，但是在大部分情况下，这个判断条件都不成立，所以它需要执行的次数很少（这种效果越往后越明显，因为 m 的值越来越小，可以滤掉更多的数）。但是对于极端情况（或者接近极端的情况）——如果数组完全是降序排列的话，那么这个条件每次都会成立，会导致算法退化成 O(n * m) ，性能就不可接受了。
solution4~6的优化我觉得读起来有点晦涩，有兴趣的同学可以自己去看，这里不展开说了。它们都存在算法退化的情况。
我的算法可能理解起来要简单些，基本思路是偷懒：把缓冲区设置为 2 * k ，在扫数组的时候，如果这个数比当前保留的最大值还要小，就把它塞进缓冲区，直到缓冲区塞满了，再排序、取最大值、删多余的数。
1. 开辟一个 2 × k 的临时数组 r
2. 将 N[1..k] 拷贝到 r[1..k]，并记录 r 的末尾 e = k + 1
3. 找出 r[1..k] 中的最大值 m
4. 对于每一个剩下的 n - k 个数 i：
4.1 如果 i 小于 m，将 m 塞到 r 的末尾 r[e]；e = e + 1
4.1.1 如果 e == 2×k（r被塞满了），对 r 进行排序，得出前k个数中的最大值；抛弃后面的k个数，e = k + 1
5. 对 r[1..e] 进行排序
6. 返回 r[1..k]
这个算法的实际效果很好，在 n = 1亿、k = 1万 的情况下，对于随机的n个数，4.1条件成立的次数通常只有十几次，几乎可以忽略，因此大约只需要扫描整个数组时间的2～3倍即可。
但是这个算法同样存在退化的问题：如果全都是倒序排列的话，也变成O(n*m)了。幸而解决方案也很简单：对这个数组进行 n / 100 次的随机化（考虑到随机化耗时也比较大，100这个数字是试了几次以后发现的合适值，不一定最优，但是都差不多了）：
void rand_factor()
{
//randomization
const int factor = 100;
int r, t, i;
for (i = n / factor; i > 0; i--)
{
r = rand() % n;
t = a[0], a[0] = a[r], a[r] = t;
}
}
{
//randomization
const int factor = 100;
int r, t, i;
for (i = n / factor; i > 0; i--)
{
r = rand() % n;
t = a[0], a[0] = a[r], a[r] = t;
}
}
p.s. 很不幸的是随机化这个方法对于solution3来说虽然提升也很明显，但是远远不够。solution4～6也不太行。
这里给出随机情况下和完全倒序情况下的性能对比吧（ubuntu 12.04 x86_64，i5 2400@3.1G）：
引用
随机数据
========
随机化生成数据： 7.087s
遍历耗时： 0.053s
1/100随机化耗时： 0.064s
STL的nth_element： 0.841s
最大堆+随机化： 0.162s
Solution3+随机化： 3.121s
solution4+随机化： 2.825s
solution6+随机化： 0.249s
我的算法+随机化： 0.163s
倒序数据
========
无随机化生成数据： 0.150s
遍历耗时： 0.052s
1/100随机化耗时： 0.067s
STL的nth_element： 1.420s
最大堆+随机化： 0.301s
Solution3+随机化： 67.552s
solution4+随机化： 66.405s
solution6+随机化： 2.388s
我的算法+随机化： 0.170s
========
随机化生成数据： 7.087s
遍历耗时： 0.053s
1/100随机化耗时： 0.064s
STL的nth_element： 0.841s
最大堆+随机化： 0.162s
Solution3+随机化： 3.121s
solution4+随机化： 2.825s
solution6+随机化： 0.249s
我的算法+随机化： 0.163s
倒序数据
========
无随机化生成数据： 0.150s
遍历耗时： 0.052s
1/100随机化耗时： 0.067s
STL的nth_element： 1.420s
最大堆+随机化： 0.301s
Solution3+随机化： 67.552s
solution4+随机化： 66.405s
solution6+随机化： 2.388s
我的算法+随机化： 0.170s
补充说明一下，nth_element算法在面试的时候可能给出的 n 会更大，以至于在内存中存不下，这时候通常会认为用堆来实现最好——因为只要O(k)的空间就可以搞定，而且最差时间复杂度是O(logk * n)，但是要注意logk的常数实际上是很大的，所以你可以看到前面的数据里 堆算法 的效率并不是最好的。事实上这里给出的所有算法（不考虑随机化的话）也都只需要O(k)的空间；如果需要随机化的话也很简单，分段处理，只要保证每段能在内存中保存下来就行了。
最后上代码存档（为了方便测试用了些全局变量，看起来可能有点挫）：
Jul
11
在模板里引入其他模板应该是很常见的一种需求，但是webpy默认的template居然没有提供这种机制，挺神奇的。
官方的解决办法是把某个模板的输出给另一个模板，看起来和用起来都超级不爽；知乎网友给出的解决方案也很不爽：用render初始化时指定的layout，但是这个跟include差很多，不灵活。
实际上，由于render渲染模板后的输出本身是一个字符串，所以如果能在模板里头直接调用render渲染其他模板就最好了：而且这是可以实现的，只是略带tricky。
由于webpy给render的默认globals是空的，所以模板里只能用基本的python语法，默认连builtin的东西都用不了（比如zip、str），但是可以通过初始化render时指定globals的方式来引入：
所以我们只需要把render自己也加到这个globals里头去，就可以在模板里引用它了：
第三句看起来虽然tricky，但是由于python的对象传的是引用，所以可以达到预期的效果。
这样只要在模板里这样写就行了：
官方的解决办法是把某个模板的输出给另一个模板，看起来和用起来都超级不爽；知乎网友给出的解决方案也很不爽：用render初始化时指定的layout，但是这个跟include差很多，不灵活。
实际上，由于render渲染模板后的输出本身是一个字符串，所以如果能在模板里头直接调用render渲染其他模板就最好了：而且这是可以实现的，只是略带tricky。
由于webpy给render的默认globals是空的，所以模板里只能用基本的python语法，默认连builtin的东西都用不了（比如zip、str），但是可以通过初始化render时指定globals的方式来引入：
render = web.template.render('view/', cache=False, globals = __builtins__.__dict__)
所以我们只需要把render自己也加到这个globals里头去，就可以在模板里引用它了：
render_globals = {}
render = web.template.render('view/', cache=False, globals = render_globals)
render_globals['render'] = render
render = web.template.render('view/', cache=False, globals = render_globals)
render_globals['render'] = render
第三句看起来虽然tricky，但是由于python的对象传的是引用，所以可以达到预期的效果。
这样只要在模板里这样写就行了：
$:render.header('首页') #那个冒号别漏掉:)
Jul
3
先吐槽一下，顺便说下起因。
去年9月买的这个ML-G3000，青轴全无冲（回想起来有点2，青轴又不是拿来玩游戏的，买什么全无冲。。还贵了50块……），419入手的。它的键位基本上是标准的，但是R-Win变成了“禁用Win”功能键（直接在键盘电路逻辑里实现的，OS里检测不到keyCode的）、右键菜单（属性）键变成了功能键（配合Fx实现多媒体/音量控制什么的）。禁用Win对于游戏控来说是挺不错了，但是对于我这种几乎不怎么玩PC游戏的人来说就太废了点，而且还经常把这个当成Win键误按，例如我要Win+L锁屏，经常就变成了禁用Win，然后再换"左Win"+L，可是这时候Win已经被禁用了……各种抓狂。于是就用拔键器拔了一下，没想到键帽和轴结合太紧，直接把轴给拔坏了，里面弹簧蹦了出来。然后心里很不爽，就拿CapsLock开刀，果然又拔坏了……于是就成了这个样子：
去年9月买的这个ML-G3000，青轴全无冲（回想起来有点2，青轴又不是拿来玩游戏的，买什么全无冲。。还贵了50块……），419入手的。它的键位基本上是标准的，但是R-Win变成了“禁用Win”功能键（直接在键盘电路逻辑里实现的，OS里检测不到keyCode的）、右键菜单（属性）键变成了功能键（配合Fx实现多媒体/音量控制什么的）。禁用Win对于游戏控来说是挺不错了，但是对于我这种几乎不怎么玩PC游戏的人来说就太废了点，而且还经常把这个当成Win键误按，例如我要Win+L锁屏，经常就变成了禁用Win，然后再换"左Win"+L，可是这时候Win已经被禁用了……各种抓狂。于是就用拔键器拔了一下，没想到键帽和轴结合太紧，直接把轴给拔坏了，里面弹簧蹦了出来。然后心里很不爽，就拿CapsLock开刀，果然又拔坏了……于是就成了这个样子：
Jul
1
UPDATE@2013.08.04 搞到了一批折扣邀请码，有兴趣的同学（最好是带项目的团队、公司等）可以联系我。
最近弄了一台 ucloud.cn 的vps。准确地说应该是云主机，跟我在别处买的vps的确是有些不同的地方。
首先是注册，ucloud对密码的安全性要求太高了。其实很早之前就拿到邀请码试用过三天，但是由于对密码的要求过于复杂，刚开始几次，每次登陆之前都得重置密码，比较蛋疼；后来终于记住了，相当不容易。
然后是选配置。ucloud的最低配置是单核、2G内存、2mbps单线，显然不是面向个人vps玩家了，不过对于创业公司什么的倒是很合适。对比了一下国内另外两家云主机的同样配置，价格上也还是挺有优势的。选配置的时候有个“高性能磁盘”选项很有意思，目测是为了数据库之类对磁盘IOPS要求比较高的场合设置的，勾上了价格也没多大变化。
最终我选择的配置是双核、2G、20GB数据盘、4M双线，2700/yr。
开通主机以后就是选择系统。我图省事选了个ubuntu 12.04 64bit的。本来还做好准备像我的个人vps那样，vnc连上去在命令行下通过mount上去的iso安装，结果发现等了一会儿直接就可以开始用了，看起来应该是像openvz方案一样事先准备好了对应的template改改配置就能上。而且非常贴心的一点是，apt的默认源是ucloud自建的同步源，apt-get update和install的时候就很爽～其他的OS没试过，不过去mirror看了下，除了ubuntu，还有debian、fedora、centos等发行版的源，甚至还有个10gen（也就是mongodb他们家）的源。
进入后台管理看了下，一眼就能认出浓浓的bootstrap的味道，感觉挺无趣的，好歹用个Flat UI什么的换换小清新的口味嘛-。- 不过后台功能还是挺赞的，尤其是与 upyun、dnspod 的战略合作，可以绑定他们两家帐号，方便管理。至于upyun/dnspod的牛逼之处就不用多说了，这三家能合力打造这样的平台，前景我非常看好。
开通的时候我选择的是华东双线机房，所以给分配了2个ip，一个电信一个联通，因为域名是托管在dnspod，可以为不同请求线路返回合适的ip，很给力。ping了一下，延迟只有11ms，相当不错。ssh登上去看了下，ifconfig只看到了个内网ip，还觉得挺神奇的。后来在ucloud的主页看到，这是他们的“弹性IP”解决方案，ip不是直接绑定在vps的网卡上。设想，对于线上4台年付费的web机器进行负载均衡，某一台down了，可以马上把另一个按小时付费的备机开起来，把ip切过去，这样即减少了故障时间，又相当节省，貌似不错。
所谓“云主机”，我觉得跟传统vps/服务器的主要区别有2个：一个是可以按需选择合适的配置，并且此后还可以不断调整升级且代价很小；另一个就是底层存储是基于网络的，所在服务器挂掉也不用担心，换个地方再启动起来就好了。
去年12月在杭州参加SegmentFault举办的Hackathon的时候曾经试用过XX云的主机，他们家的特色是有自建的BGP骨干网，网络比较给力；但问题是，XX云主机的磁盘IO烂到一定境界，实在是……后来听说他们是直接用NFS作为底层存储，以及看到各种吐槽他们家IO的……
所以这次用ucloud的时候就特意关注了下磁盘性能，跑点数据列出来附在后面供参考，可以看出性能相当不错，已fio的数据为参考，顺序读取697M，顺序写入419M，随机读取 6245 IOPS，随机写入 309 IOPS。其中随机写入偏弱，可能是多备份网络延迟的原因吧，不知道选择“高性能磁盘”效果会怎样，但是就算是309 IOPS，也比服务器用的机械硬盘快多了，跟别说被甩开n条街的XX云了……很好奇他们家这个是怎么实现的，真希望ucloud的技术团队可以分享一下经验～
至于ucloud的其他方面，因为用的时间还比较短，体验不多，没什么可说的，就是总体感觉良好。ucloud提供的这项服务，对于创业团队什么的来说，的确可以算是最合适的选择了。
下附磁盘测试数据：
TEST#1 dd写入
TEST#2 hdparm -tT
TEST #3 fio random-read
TEST #4 fio random-write
$ cat random-write-test.fio
[random-write]
rw=randwrite
size=1G
directory=/home/felix021/test/
$ fio random-write-test.fio
random-write: (g=0): rw=randwrite, bs=4K-4K/4K-4K, ioengine=sync, iodepth=1
fio 1.59
Starting 1 process
random-write: Laying out IO file(s) (1 file(s) / 1024MB)
Jobs: 1 (f=1): [w] [92.5% done] [0K/1429K /s] [0 /348 iops] [eta 01m:09s]
random-write: (groupid=0, jobs=1): err= 0: pid=10733
write: io=1024.0MB, bw=1236.3KB/s, iops=309 , runt=848202msec
clat (usec): min=1 , max=1101.4K, avg=3231.07, stdev=10586.16
lat (usec): min=1 , max=1101.4K, avg=3231.53, stdev=10586.42
bw (KB/s) : min= 14, max=397248, per=95.34%, avg=1178.40, stdev=9976.63
cpu : usr=0.19%, sys=0.75%, ctx=49240, majf=0, minf=24
IO depths : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
submit : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
complete : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
issued r/w/d: total=0/262144/0, short=0/0/0
lat (usec): 2=0.01%, 4=0.06%, 10=54.82%, 20=25.75%, 50=2.45%
lat (usec): 100=1.28%, 250=0.84%, 500=0.36%, 750=0.08%, 1000=0.02%
lat (msec): 2=0.04%, 4=0.05%, 10=0.29%, 20=8.87%, 50=4.58%
lat (msec): 100=0.47%, 250=0.02%, 500=0.01%, 750=0.01%, 1000=0.01%
lat (msec): 2000=0.01%
Run status group 0 (all jobs):
WRITE: io=1024.0MB, aggrb=1236KB/s, minb=1265KB/s, maxb=1265KB/s, mint=848202msec, maxt=848202msec
Disk stats (read/write):
vdb: ios=1/145156, merge=0/13152, ticks=12/3297360, in_queue=3297220, util=99.78%
TEST #5 fio sequence-read
TEST #6 fio sequence-write
最近弄了一台 ucloud.cn 的vps。准确地说应该是云主机，跟我在别处买的vps的确是有些不同的地方。
首先是注册，ucloud对密码的安全性要求太高了。其实很早之前就拿到邀请码试用过三天，但是由于对密码的要求过于复杂，刚开始几次，每次登陆之前都得重置密码，比较蛋疼；后来终于记住了，相当不容易。
然后是选配置。ucloud的最低配置是单核、2G内存、2mbps单线，显然不是面向个人vps玩家了，不过对于创业公司什么的倒是很合适。对比了一下国内另外两家云主机的同样配置，价格上也还是挺有优势的。选配置的时候有个“高性能磁盘”选项很有意思，目测是为了数据库之类对磁盘IOPS要求比较高的场合设置的，勾上了价格也没多大变化。
最终我选择的配置是双核、2G、20GB数据盘、4M双线，2700/yr。
开通主机以后就是选择系统。我图省事选了个ubuntu 12.04 64bit的。本来还做好准备像我的个人vps那样，vnc连上去在命令行下通过mount上去的iso安装，结果发现等了一会儿直接就可以开始用了，看起来应该是像openvz方案一样事先准备好了对应的template改改配置就能上。而且非常贴心的一点是，apt的默认源是ucloud自建的同步源，apt-get update和install的时候就很爽～其他的OS没试过，不过去mirror看了下，除了ubuntu，还有debian、fedora、centos等发行版的源，甚至还有个10gen（也就是mongodb他们家）的源。
进入后台管理看了下，一眼就能认出浓浓的bootstrap的味道，感觉挺无趣的，好歹用个Flat UI什么的换换小清新的口味嘛-。- 不过后台功能还是挺赞的，尤其是与 upyun、dnspod 的战略合作，可以绑定他们两家帐号，方便管理。至于upyun/dnspod的牛逼之处就不用多说了，这三家能合力打造这样的平台，前景我非常看好。
开通的时候我选择的是华东双线机房，所以给分配了2个ip，一个电信一个联通，因为域名是托管在dnspod，可以为不同请求线路返回合适的ip，很给力。ping了一下，延迟只有11ms，相当不错。ssh登上去看了下，ifconfig只看到了个内网ip，还觉得挺神奇的。后来在ucloud的主页看到，这是他们的“弹性IP”解决方案，ip不是直接绑定在vps的网卡上。设想，对于线上4台年付费的web机器进行负载均衡，某一台down了，可以马上把另一个按小时付费的备机开起来，把ip切过去，这样即减少了故障时间，又相当节省，貌似不错。
所谓“云主机”，我觉得跟传统vps/服务器的主要区别有2个：一个是可以按需选择合适的配置，并且此后还可以不断调整升级且代价很小；另一个就是底层存储是基于网络的，所在服务器挂掉也不用担心，换个地方再启动起来就好了。
去年12月在杭州参加SegmentFault举办的Hackathon的时候曾经试用过XX云的主机，他们家的特色是有自建的BGP骨干网，网络比较给力；但问题是，XX云主机的磁盘IO烂到一定境界，实在是……后来听说他们是直接用NFS作为底层存储，以及看到各种吐槽他们家IO的……
所以这次用ucloud的时候就特意关注了下磁盘性能，跑点数据列出来附在后面供参考，可以看出性能相当不错，已fio的数据为参考，顺序读取697M，顺序写入419M，随机读取 6245 IOPS，随机写入 309 IOPS。其中随机写入偏弱，可能是多备份网络延迟的原因吧，不知道选择“高性能磁盘”效果会怎样，但是就算是309 IOPS，也比服务器用的机械硬盘快多了，跟别说被甩开n条街的XX云了……很好奇他们家这个是怎么实现的，真希望ucloud的技术团队可以分享一下经验～
至于ucloud的其他方面，因为用的时间还比较短，体验不多，没什么可说的，就是总体感觉良好。ucloud提供的这项服务，对于创业团队什么的来说，的确可以算是最合适的选择了。
下附磁盘测试数据：
TEST#1 dd写入
引用
$ dd if=/dev/zero bs=1M count=4096 of=test
4096+0 records in
4096+0 records out
4294967296 bytes (4.3 GB) copied, 15.1328 s, 284 MB/s
4096+0 records in
4096+0 records out
4294967296 bytes (4.3 GB) copied, 15.1328 s, 284 MB/s
TEST#2 hdparm -tT
引用
$ for i in 1 2 3; do sudo hdparm -tT /dev/vdb; done
/dev/vdb:
Timing cached reads: 9574 MB in 2.00 seconds = 4790.56 MB/sec
Timing buffered disk reads: 1714 MB in 3.02 seconds = 568.37 MB/sec
/dev/vdb:
Timing cached reads: 10018 MB in 2.00 seconds = 5013.55 MB/sec
Timing buffered disk reads: 1840 MB in 3.01 seconds = 611.33 MB/sec
/dev/vdb:
Timing cached reads: 9574 MB in 2.00 seconds = 4792.34 MB/sec
Timing buffered disk reads: 1908 MB in 3.00 seconds = 635.80 MB/sec
/dev/vdb:
Timing cached reads: 9574 MB in 2.00 seconds = 4790.56 MB/sec
Timing buffered disk reads: 1714 MB in 3.02 seconds = 568.37 MB/sec
/dev/vdb:
Timing cached reads: 10018 MB in 2.00 seconds = 5013.55 MB/sec
Timing buffered disk reads: 1840 MB in 3.01 seconds = 611.33 MB/sec
/dev/vdb:
Timing cached reads: 9574 MB in 2.00 seconds = 4792.34 MB/sec
Timing buffered disk reads: 1908 MB in 3.00 seconds = 635.80 MB/sec
TEST #3 fio random-read
引用
$ cat random-read-test.fio
[random-read]
rw=randread
size=1g
directory=/home/felix021/test/
$ fio random-read-test.fio
random-read: (g=0): rw=randread, bs=4K-4K/4K-4K, ioengine=sync, iodepth=1
fio 1.59
Starting 1 process
random-read: Laying out IO file(s) (1 file(s) / 1024MB)
Jobs: 1 (f=1): [r] [100.0% done] [26789K/0K /s] [6540 /0 iops] [eta 00m:00s]
random-read: (groupid=0, jobs=1): err= 0: pid=10676
read : io=1024.0MB, bw=24980KB/s, iops=6245 , runt= 41976msec
clat (usec): min=77 , max=35439 , avg=155.44, stdev=237.39
lat (usec): min=78 , max=35440 , avg=155.82, stdev=237.39
bw (KB/s) : min=18384, max=28256, per=100.22%, avg=25035.02, stdev=1702.27
cpu : usr=3.42%, sys=23.48%, ctx=262433, majf=0, minf=24
IO depths : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
submit : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
complete : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
issued r/w/d: total=262144/0/0, short=0/0/0
lat (usec): 100=3.05%, 250=93.84%, 500=2.44%, 750=0.22%, 1000=0.10%
lat (msec): 2=0.23%, 4=0.07%, 10=0.05%, 20=0.01%, 50=0.01%
Run status group 0 (all jobs):
READ: io=1024.0MB, aggrb=24980KB/s, minb=25579KB/s, maxb=25579KB/s, mint=41976msec, maxt=41976msec
Disk stats (read/write):
vdb: ios=260955/11, merge=0/10, ticks=25956/396, in_queue=25972, util=61.22%
[random-read]
rw=randread
size=1g
directory=/home/felix021/test/
$ fio random-read-test.fio
random-read: (g=0): rw=randread, bs=4K-4K/4K-4K, ioengine=sync, iodepth=1
fio 1.59
Starting 1 process
random-read: Laying out IO file(s) (1 file(s) / 1024MB)
Jobs: 1 (f=1): [r] [100.0% done] [26789K/0K /s] [6540 /0 iops] [eta 00m:00s]
random-read: (groupid=0, jobs=1): err= 0: pid=10676
read : io=1024.0MB, bw=24980KB/s, iops=6245 , runt= 41976msec
clat (usec): min=77 , max=35439 , avg=155.44, stdev=237.39
lat (usec): min=78 , max=35440 , avg=155.82, stdev=237.39
bw (KB/s) : min=18384, max=28256, per=100.22%, avg=25035.02, stdev=1702.27
cpu : usr=3.42%, sys=23.48%, ctx=262433, majf=0, minf=24
IO depths : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
submit : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
complete : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
issued r/w/d: total=262144/0/0, short=0/0/0
lat (usec): 100=3.05%, 250=93.84%, 500=2.44%, 750=0.22%, 1000=0.10%
lat (msec): 2=0.23%, 4=0.07%, 10=0.05%, 20=0.01%, 50=0.01%
Run status group 0 (all jobs):
READ: io=1024.0MB, aggrb=24980KB/s, minb=25579KB/s, maxb=25579KB/s, mint=41976msec, maxt=41976msec
Disk stats (read/write):
vdb: ios=260955/11, merge=0/10, ticks=25956/396, in_queue=25972, util=61.22%
TEST #4 fio random-write
$ cat random-write-test.fio
[random-write]
rw=randwrite
size=1G
directory=/home/felix021/test/
$ fio random-write-test.fio
random-write: (g=0): rw=randwrite, bs=4K-4K/4K-4K, ioengine=sync, iodepth=1
fio 1.59
Starting 1 process
random-write: Laying out IO file(s) (1 file(s) / 1024MB)
Jobs: 1 (f=1): [w] [92.5% done] [0K/1429K /s] [0 /348 iops] [eta 01m:09s]
random-write: (groupid=0, jobs=1): err= 0: pid=10733
write: io=1024.0MB, bw=1236.3KB/s, iops=309 , runt=848202msec
clat (usec): min=1 , max=1101.4K, avg=3231.07, stdev=10586.16
lat (usec): min=1 , max=1101.4K, avg=3231.53, stdev=10586.42
bw (KB/s) : min= 14, max=397248, per=95.34%, avg=1178.40, stdev=9976.63
cpu : usr=0.19%, sys=0.75%, ctx=49240, majf=0, minf=24
IO depths : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
submit : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
complete : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
issued r/w/d: total=0/262144/0, short=0/0/0
lat (usec): 2=0.01%, 4=0.06%, 10=54.82%, 20=25.75%, 50=2.45%
lat (usec): 100=1.28%, 250=0.84%, 500=0.36%, 750=0.08%, 1000=0.02%
lat (msec): 2=0.04%, 4=0.05%, 10=0.29%, 20=8.87%, 50=4.58%
lat (msec): 100=0.47%, 250=0.02%, 500=0.01%, 750=0.01%, 1000=0.01%
lat (msec): 2000=0.01%
Run status group 0 (all jobs):
WRITE: io=1024.0MB, aggrb=1236KB/s, minb=1265KB/s, maxb=1265KB/s, mint=848202msec, maxt=848202msec
Disk stats (read/write):
vdb: ios=1/145156, merge=0/13152, ticks=12/3297360, in_queue=3297220, util=99.78%
TEST #5 fio sequence-read
引用
$ cat read-test.fio
[random-read]
rw=read
size=1g
directory=/home/felix021/test/
$ fio read-test.fio
random-read: (g=0): rw=read, bs=4K-4K/4K-4K, ioengine=sync, iodepth=1
fio 1.59
Starting 1 process
random-read: Laying out IO file(s) (1 file(s) / 1024MB)
Jobs: 1 (f=1)
random-read: (groupid=0, jobs=1): err= 0: pid=10798
read : io=1024.0MB, bw=697191KB/s, iops=174297 , runt= 1504msec
clat (usec): min=0 , max=16300 , avg= 4.73, stdev=97.89
lat (usec): min=1 , max=16300 , avg= 4.95, stdev=97.89
bw (KB/s) : min=615400, max=779152, per=99.97%, avg=696994.67, stdev=81877.45
cpu : usr=11.44%, sys=57.75%, ctx=3787, majf=0, minf=26
IO depths : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
submit : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
complete : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
issued r/w/d: total=262144/0/0, short=0/0/0
lat (usec): 2=66.20%, 4=31.16%, 10=0.58%, 20=0.15%, 50=0.28%
lat (usec): 100=0.63%, 250=0.89%, 500=0.07%, 750=0.01%, 1000=0.01%
lat (msec): 2=0.01%, 4=0.01%, 10=0.01%, 20=0.01%
Run status group 0 (all jobs):
READ: io=1024.0MB, aggrb=697191KB/s, minb=713924KB/s, maxb=713924KB/s, mint=1504msec, maxt=1504msec
Disk stats (read/write):
vdb: ios=3697/0, merge=0/0, ticks=1280/0, in_queue=1268, util=74.56%
[random-read]
rw=read
size=1g
directory=/home/felix021/test/
$ fio read-test.fio
random-read: (g=0): rw=read, bs=4K-4K/4K-4K, ioengine=sync, iodepth=1
fio 1.59
Starting 1 process
random-read: Laying out IO file(s) (1 file(s) / 1024MB)
Jobs: 1 (f=1)
random-read: (groupid=0, jobs=1): err= 0: pid=10798
read : io=1024.0MB, bw=697191KB/s, iops=174297 , runt= 1504msec
clat (usec): min=0 , max=16300 , avg= 4.73, stdev=97.89
lat (usec): min=1 , max=16300 , avg= 4.95, stdev=97.89
bw (KB/s) : min=615400, max=779152, per=99.97%, avg=696994.67, stdev=81877.45
cpu : usr=11.44%, sys=57.75%, ctx=3787, majf=0, minf=26
IO depths : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
submit : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
complete : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
issued r/w/d: total=262144/0/0, short=0/0/0
lat (usec): 2=66.20%, 4=31.16%, 10=0.58%, 20=0.15%, 50=0.28%
lat (usec): 100=0.63%, 250=0.89%, 500=0.07%, 750=0.01%, 1000=0.01%
lat (msec): 2=0.01%, 4=0.01%, 10=0.01%, 20=0.01%
Run status group 0 (all jobs):
READ: io=1024.0MB, aggrb=697191KB/s, minb=713924KB/s, maxb=713924KB/s, mint=1504msec, maxt=1504msec
Disk stats (read/write):
vdb: ios=3697/0, merge=0/0, ticks=1280/0, in_queue=1268, util=74.56%
TEST #6 fio sequence-write
引用
$ cat write-test.fio
[random-read]
rw=write
size=1g
directory=/home/felix021/test/
$ fio write-test.fio
random-read: (g=0): rw=write, bs=4K-4K/4K-4K, ioengine=sync, iodepth=1
fio 1.59
Starting 1 process
Jobs: 1 (f=1): [W] [-.-% done] [0K/409.3M /s] [0 /102K iops] [eta 00m:00s]
random-read: (groupid=0, jobs=1): err= 0: pid=10816
write: io=1024.0MB, bw=419934KB/s, iops=104983 , runt= 2497msec
clat (usec): min=0 , max=10136 , avg= 7.71, stdev=123.62
lat (usec): min=0 , max=10136 , avg= 7.98, stdev=123.64
bw (KB/s) : min=177498, max=650096, per=110.68%, avg=464776.50, stdev=202324.17
cpu : usr=14.74%, sys=57.69%, ctx=199, majf=0, minf=27
IO depths : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
submit : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
complete : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
issued r/w/d: total=0/262144/0, short=0/0/0
lat (usec): 2=0.08%, 4=36.39%, 10=58.08%, 20=4.91%, 50=0.38%
lat (usec): 100=0.07%, 250=0.01%, 500=0.01%, 750=0.01%, 1000=0.01%
lat (msec): 2=0.01%, 4=0.01%, 10=0.04%, 20=0.01%
Run status group 0 (all jobs):
WRITE: io=1024.0MB, aggrb=419934KB/s, minb=430012KB/s, maxb=430012KB/s, mint=2497msec, maxt=2497msec
Disk stats (read/write):
vdb: ios=0/1382, merge=0/11, ticks=0/219176, in_queue=246612, util=77.43%
[random-read]
rw=write
size=1g
directory=/home/felix021/test/
$ fio write-test.fio
random-read: (g=0): rw=write, bs=4K-4K/4K-4K, ioengine=sync, iodepth=1
fio 1.59
Starting 1 process
Jobs: 1 (f=1): [W] [-.-% done] [0K/409.3M /s] [0 /102K iops] [eta 00m:00s]
random-read: (groupid=0, jobs=1): err= 0: pid=10816
write: io=1024.0MB, bw=419934KB/s, iops=104983 , runt= 2497msec
clat (usec): min=0 , max=10136 , avg= 7.71, stdev=123.62
lat (usec): min=0 , max=10136 , avg= 7.98, stdev=123.64
bw (KB/s) : min=177498, max=650096, per=110.68%, avg=464776.50, stdev=202324.17
cpu : usr=14.74%, sys=57.69%, ctx=199, majf=0, minf=27
IO depths : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
submit : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
complete : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
issued r/w/d: total=0/262144/0, short=0/0/0
lat (usec): 2=0.08%, 4=36.39%, 10=58.08%, 20=4.91%, 50=0.38%
lat (usec): 100=0.07%, 250=0.01%, 500=0.01%, 750=0.01%, 1000=0.01%
lat (msec): 2=0.01%, 4=0.01%, 10=0.04%, 20=0.01%
Run status group 0 (all jobs):
WRITE: io=1024.0MB, aggrb=419934KB/s, minb=430012KB/s, maxb=430012KB/s, mint=2497msec, maxt=2497msec
Disk stats (read/write):
vdb: ios=0/1382, merge=0/11, ticks=0/219176, in_queue=246612, util=77.43%
Apr
16
今天看到80386+里 BSF/BSR 这对指令貌似挺有意思，Bit Scan Forward/Reverse，它们的作用是正向/逆向扫描一个WORD(16bit)/DWORD(32bit)，找出第一个等于1的bit编号。比如对于BX=0x1010，执行 BSF CX, BX 得到的CX=4，而 BSR CX, BX 得到的CX=12。
咋一看是个神器啊。《编程之美》什么的，不是还有一道面试题说的就是怎样快速求出一个整数中bit=1的数量么。这货加上个while循环和移位，秒杀。最新版的Intel指令手册并没有明确说它需要多少个时钟周期，不过这里的数据指出，在80486+，BSF需要6～43个时钟周期才能完成（BSR则需要6～104个clocks），也就是说，它似乎并没有被特别优化，而是使用了CPU内的微码来完成循环，所以不要指望能带来性能上的BONUS，详情可参见这篇：求整数中比特为1的二进制位数。
这篇文章里面给出的用上BSF/BSR的代码是：
想试试这段代码，不过蛋疼的是这是VS的汇编语法，GCC不能识别，于是终于下了决心翻出GCC-Inline-Assembly-HOWTO，看了下，其实也不是很复杂，简单改了下，变成这样：
跑了一下，果然效率不行，跟最差的直接循环在同一个量级。
仔细看了下代码，发现这里用的是BSR，而且还用上了n和count两个变量，感觉不太爽，于是完全改成汇编，写成这样：
结果。。。基本没变。嗯，所以就这样吧。。。
咋一看是个神器啊。《编程之美》什么的，不是还有一道面试题说的就是怎样快速求出一个整数中bit=1的数量么。这货加上个while循环和移位，秒杀。最新版的Intel指令手册并没有明确说它需要多少个时钟周期，不过这里的数据指出，在80486+，BSF需要6～43个时钟周期才能完成（BSR则需要6～104个clocks），也就是说，它似乎并没有被特别优化，而是使用了CPU内的微码来完成循环，所以不要指望能带来性能上的BONUS，详情可参见这篇：求整数中比特为1的二进制位数。
这篇文章里面给出的用上BSF/BSR的代码是：
int f4(unsigned int num) {
int count = 0;
while(num) {
int n;
__asm {
bsr eax, num
mov n, eax
}
++count;
num ^= (1 << n);
}
return count;
}
int count = 0;
while(num) {
int n;
__asm {
bsr eax, num
mov n, eax
}
++count;
num ^= (1 << n);
}
return count;
}
想试试这段代码，不过蛋疼的是这是VS的汇编语法，GCC不能识别，于是终于下了决心翻出GCC-Inline-Assembly-HOWTO，看了下，其实也不是很复杂，简单改了下，变成这样：
int f4(unsigned int num) {
int count = 0;
while(num) {
int n;
__asm__ (
"bsr %1, %%eax\n\t"
"movl %%eax, %0\n\t"
: "=r" (n)
: "r" (num)
: "%eax"
);
++count;
num ^= (1 << n);
}
return count;
}
int count = 0;
while(num) {
int n;
__asm__ (
"bsr %1, %%eax\n\t"
"movl %%eax, %0\n\t"
: "=r" (n)
: "r" (num)
: "%eax"
);
++count;
num ^= (1 << n);
}
return count;
}
跑了一下，果然效率不行，跟最差的直接循环在同一个量级。
仔细看了下代码，发现这里用的是BSR，而且还用上了n和count两个变量，感觉不太爽，于是完全改成汇编，写成这样：
int f4(unsigned int num) { //注：x86下一般都是用EAX来存函数的返回值
asm (
"movl $0, %%eax\n\t" //这里是eax存的就是count
"jmp f4_cmp\n"
"f4_loop:\n\t"
"bsf %0, %%ecx\n\t" //ecx=bsf(num)
"incb %%cl\n\t" //cl += 1
"shrl %%cl, %0\n\t" //num >>= cl; shr貌似只接受 cl 和立即数？
"incl %%eax\n" //count++
"f4_cmp:\n\t"
"cmp $0, %0\n\t"
"jnz f4_loop\n\t"
:
: "r"(num)
: "%eax", "%ecx"
);
}
asm (
"movl $0, %%eax\n\t" //这里是eax存的就是count
"jmp f4_cmp\n"
"f4_loop:\n\t"
"bsf %0, %%ecx\n\t" //ecx=bsf(num)
"incb %%cl\n\t" //cl += 1
"shrl %%cl, %0\n\t" //num >>= cl; shr貌似只接受 cl 和立即数？
"incl %%eax\n" //count++
"f4_cmp:\n\t"
"cmp $0, %0\n\t"
"jnz f4_loop\n\t"
:
: "r"(num)
: "%eax", "%ecx"
);
}
结果。。。基本没变。嗯，所以就这样吧。。。
Mar
24
原文: Reed–Solomon codes for coders
参考: AN2407.pdf
WIKI: 里德-所罗门码
实现：Pypi ReedSolo
#译注：最近看到了RS码，发现还挺有意思的，找了一些资料学习了下，发现对于程序员来说，从这篇看起会比较容易。看完以后想着翻译一下试试，看看自己到底看懂了多少，于是就有了这篇。本文有部分错误，以及一些排版不对的地方，有兴趣的还是看原文更好:)
为程序员写的Reed-Solomon码解释
Reed-Solomon纠错码（以下简称RS码）广泛用于数据存储（如CD）和传输应用中。然而，在这些应用中，码字是藏在了电子设备里，所以无法一窥它们的模样以及它们是如何生效的。有些复杂的条形码设计也采用了RS码，能够暴露出所有的细节，对于想要获得这种技术如何生效的第一手技术的爱好者，这是一种很有趣的方式。
在这篇文章里，我是试图从程序员的视角（而不是数学家的视角）来介绍RS码的基本原理。我会用以当下流行的QR码作为例子来介绍。我选择了Python（主要是因为写出来的代码看起来整洁美观），但是我也会介绍一些不那么显而易见的Python特性，以便那些不熟悉Python的人也能看懂。里头涉及到的数学知识对读者有一定要求，并且一般是大学才教授的，但是应当能让对高中代数掌握较好的人看懂。
内容：
1 QR码结构
1.1 掩码
1.2 格式信息
1.3 数据
1.4 解码
2 BCH码
2.1 BCH错误检测
2.2 BCH纠错
3 有限域理论
3.1 乘法
3.2 基于对数的乘法
3.3 除法
3.4 多项式
4 RS码
4.1 RS生成多项式
4.2 RS编码
4.3 伴随式(Syndrome)计算
4.4 消除(erasure)纠正
4.5 错误(error)纠正
4.6 消除和错误纠正
参考: AN2407.pdf
WIKI: 里德-所罗门码
实现：Pypi ReedSolo
#译注：最近看到了RS码，发现还挺有意思的，找了一些资料学习了下，发现对于程序员来说，从这篇看起会比较容易。看完以后想着翻译一下试试，看看自己到底看懂了多少，于是就有了这篇。本文有部分错误，以及一些排版不对的地方，有兴趣的还是看原文更好:)
为程序员写的Reed-Solomon码解释
Reed-Solomon纠错码（以下简称RS码）广泛用于数据存储（如CD）和传输应用中。然而，在这些应用中，码字是藏在了电子设备里，所以无法一窥它们的模样以及它们是如何生效的。有些复杂的条形码设计也采用了RS码，能够暴露出所有的细节，对于想要获得这种技术如何生效的第一手技术的爱好者，这是一种很有趣的方式。
在这篇文章里，我是试图从程序员的视角（而不是数学家的视角）来介绍RS码的基本原理。我会用以当下流行的QR码作为例子来介绍。我选择了Python（主要是因为写出来的代码看起来整洁美观），但是我也会介绍一些不那么显而易见的Python特性，以便那些不熟悉Python的人也能看懂。里头涉及到的数学知识对读者有一定要求，并且一般是大学才教授的，但是应当能让对高中代数掌握较好的人看懂。
内容：
1 QR码结构
1.1 掩码
1.2 格式信息
1.3 数据
1.4 解码
2 BCH码
2.1 BCH错误检测
2.2 BCH纠错
3 有限域理论
3.1 乘法
3.2 基于对数的乘法
3.3 除法
3.4 多项式
4 RS码
4.1 RS生成多项式
4.2 RS编码
4.3 伴随式(Syndrome)计算
4.4 消除(erasure)纠正
4.5 错误(error)纠正
4.6 消除和错误纠正
