最近在学习redis，这时才知道了skip list，结合Mit 算法导论 lecture 12，在奋斗了2个早上的时间后有了下面的东东。

对于我们熟悉的binary search来说，我们需要能够做到random access才行。但是在普通的link这种数据结构中却不能做到。而这种情况下我们有很多类似的工具比如heap，tree，b tree，red－black tree。等等类似的都是来自AVL的变种。但是说实话，这些东东，的确是挺难实现的，需要做各种的旋转啊，调整啊，来保持平衡。特别是red－black tree。而这时的skip list 就为我们提供了一个很好的思路。

introduction

让我们先从简单的开始

如果最下面的数字是已经排序好的数列，我们想要快速查找其中一项，而不是简单的便利。我们可以增加一个link，也就是上面的一条，来让我们能够“跳过”一些元素，也就是减少一些不必要的比较。

那么在2条时，我们的访问程度是多少呢？L2 + L1 / L2, 也就是第二条link的个数+ 每一个小端个数，这个是最差情况。显然，让这个不等式和最小，需要 L2 = L1 / L2。 显然L1是一个定值。这里设为N,那么，2条link下，我们的查找复杂度是 2 * √n

如何再优化呢？这个思路很简单，就是在L2上面再构建一个link L3. 整个时间也就是 L3 ＋ L2 ／ L3 ＋ L1 ／ L2 ，根据不等式性质，他们的和最小时，也就是 L3 ＝ L2 ／ L3 ＝ L1 ／ L2。当L1 ＝ N时，他们的和时 3 * 立方根（N）

当第k层时， 我们的时间则是 k * k次方跟（N）

当k = lgN 时，我们的时间为 lgN * lg 次方跟（N），根据对数的换底公式，我们可以得出 时间是 2lgN. 哈，我们现在已经降到O(lgN).我们满足了。

这时我们可以想象一下，这个skip list的结构，其实就是一个binary tree。我们通过最上面的一层访问类似跟节点的情况，然后一层层link 相当于tree的孩子节点，整个比较过程和binary search 非常的相似。

insert

对于这些结构来说，搞定search不是难点，插入和删除则是最麻烦的东西。这里我们可以自己思考一下，为了保证我们的link的结构足够完美，可能需要记录没一段的个数，然后我们可能有一些节点要上几层或是下几层。但是这个其实，本质上和那些avl树又一样了。skip list则是基于一种随机的策略来决定这些节点。其实我们可以思考一下，最完美的分法就是和binary tree一样的，所以这种2倍数的关系就可以用抛硬币的方式来决定。

这里为了程序时间方便，我们创建一个无穷小的节点作为我们的其实节点，这样，我们所有的开始都是从最左边。

我们插入一个元素30，这时我们可以判断一下这个新的元素是否需要“升级”，这里我扔了一下，反面，不用升级了。

这里我们插入一个15，我扔了一下，反面。不用升级

这里我们插入一个20，我扔了一个正面，又扔了一个正面，额，好吧第三次终于是反面了。

这里涉及到了一点点的随机算法的证明，这些东西实在是让人烦躁。主要还是大学时候的概率学得就不咋地，现在也都忘了。从最直观的来看，就是一层层升级的概率会越来越低，在随机算法足够独立和大量的数目上来看，不难形成这样子的一个类似tree的结构。

delete

删除这里的操作简直就是blazingly simple,因为我们整个list layer 都是建立在随机上的，删除则是直接删除就好了

我在看到这里，基本已经受不了要吐槽了。实现这个也太简单了，相对red-black tree这种东西。

强连通图的应用场景我就不在这里赘述了。其中Kosaraju是最常见的一种。

这个也是Stanford 算法课弟四周的作业，现在看来是最难的一道题。那么这里我就给一个我自己的实现了。

这个作业的难度就在于他的输入是一个相当大的数据，处理不好，很容易溢出。那份大数据，我没有留在这里，感兴趣的同学可以自己下载。70多M，实在不适合放在github上面。

source_code

由于是xcode的环境，在g++下是过不去的。。。

最近一直想总结一点有关测试服务器性能的东西，今天先写一点入门的小东西了。 网站的stress test 工具很多，这里介绍一个我觉得最简单的webbench

安装webbench

wget http://www.ha97.com/code/webbench-1.5.tar.gz
tar zxvf webbench-1.5.tar.gz
cd webbench-1.5
make
make install

使用webbench

webbench -c 1000 -t 60 http://server_address/

c: 并发数， t 运行时间 下面是测试结果

Speed=2798 pages/min, 53286 bytes/sec.
Requests: 2798 susceed, 0 failed.

表示 每分钟处理请求2798， 每秒钟传输量53286

apache 的一点小问题

前几天换了一个阿里云的服务器，最低配置。内存只有512M，在做测试的时候遇到了一点小问题，这里记录一下。 服务器使用lamp默认配置，在低配置的情况下，我发现在-c 100 的情况下 mysql 就已经crash了。

这里是mysql日志

130803 13:26:40 InnoDB: Initializing buffer pool, size = 128.0M
InnoDB: mmap(137363456 bytes) failed; errno 12
130803 13:26:40 InnoDB: Completed initialization of buffer pool
130803 13:26:40 InnoDB: Fatal error: cannot allocate memory for the buffer pool
130803 13:26:40 [ERROR] Plugin 'InnoDB' init function returned error.
130803 13:26:40 [ERROR] Plugin 'InnoDB' registration as a STORAGE ENGINE failed.
130803 13:26:40 [ERROR] Unknown/unsupported storage engine: InnoDB
130803 13:26:40 [ERROR] Aborting

发现系统内存似乎已经不够用了。 用下面命令查看系统性能

top -i

top - 13:32:45 up 4 days, 18:01,  2 users,  load average: 1.54, 9.10, 8.42
Tasks: 242 total,  74 running, 168 sleeping,   0 stopped,   0 zombie
Cpu(s): 85.1%us, 14.5%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.3%st
Mem:    501892k total,   496672k used,     5220k free,     4000k buffers
Swap:        0k total,        0k used,        0k free,    35128k cached

PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
6527 www-data  20   0  295m  13m 3952 R  2.3  2.8   0:00.75 apache2
6531 www-data  20   0  294m  13m 3204 R  2.3  2.7   0:00.51 apache2
7439 www-data  20   0  293m  12m 3484 R  2.3  2.6   0:00.30 apache2
7441 www-data  20   0  293m  12m 3480 R  2.3  2.6   0:00.21 apache2
7455 www-data  20   0  293m  12m 3480 R  2.3  2.6   0:00.14 apache2
7456 www-data  20   0  293m  12m 3480 R  2.3  2.6   0:00.14 apache2
7463 www-data  20   0  293m  12m 3480 R  2.3  2.6   0:00.08 apache2
7465 www-data  20   0  294m  13m 3480 R  2.3  2.7   0:00.08 apache2
7466 www-data  20   0  294m  13m 3480 R  2.3  2.7   0:00.08 apache2
6491 www-data  20   0  294m  13m 3204 R  2.0  2.7   0:00.51 apache2
6495 www-data  20   0  294m  13m 3268 R  2.0  2.7   0:00.52 apache2
6526 www-data  20   0  295m  13m 3872 R  2.0  2.9   0:00.57 apache2
6529 www-data  20   0  294m  13m 3212 R  2.0  2.7   0:00.48 apache2
6536 www-data  20   0  294m  13m 3244 R  2.0  2.7   0:00.48 apache2
6537 www-data  20   0  294m  13m 3244 R  2.0  2.7   0:00.47 apache2
6538 www-data  20   0  294m  13m 3244 R  2.0  2.7   0:00.48 apache2
7442 www-data  20   0  293m  12m 3484 R  2.0  2.6   0:00.21 apache2
7458 www-data  20   0  293m  12m 3476 R  2.0  2.6   0:00.13 apache2
7464 www-data  20   0  294m  12m 3480 R  2.0  2.6   0:00.08 apache2
7467 www-data  20   0  294m  13m 3480 R  2.0  2.7   0:00.08 apache2
7468 www-data  20   0  294m  12m 3480 R  2.0  2.6   0:00.08 apache2
6528 www-data  20   0  295m  13m 3884 R  1.7  2.8   0:00.62 apache2
7457 www-data  20   0  293m  12m 3480 R  1.7  2.6   0:00.13 apache2
7469 www-data  20   0  294m  13m 3480 R  1.7  2.7   0:00.07 apache2
7470 www-data  20   0  294m  13m 3480 R  1.7  2.7   0:00.07 apache2
7492 www-data  20   0  293m  12m 3484 R  1.7  2.6   0:00.05 apache2
7484 www-data  20   0  293m  12m 3484 R  1.3  2.6   0:00.04 apache2
…

一下子看到好多的apache procress，让我大吃一惊。。。可见我有多弱了。。。原来每一个http请求，apache都开了一个进程来处理，而一个进程需要13M的物理内存。 而这一台服务器总共物理内存只有512M

apache 的工作模式

apache 的工作模式有几种，我们可以通过下面命令查看

apachectl -l

Compiled in modules:
core.c
mod_log_config.c
mod_logio.c
prefork.c
http_core.c
mod_so.c

这个表明我们在prefork工作模式下，也是最稳定用的最多的工作模式。 在这个模式下每一个用户的请求都会交给一个进程来处理，但是频繁的创建和销毁进程这种重量级操作降低不少系统性能，所以我们可以通过设置一些参数。但不管怎么样，都是一个请求一个进程。当进程数收到限制时，请求只能等待。而最大的请求书，显然受到系统硬件限制。

我们可以在查看默认配置

# prefork MPM
# StartServers: number of server processes to start
# MinSpareServers: minimum number of server processes which are kept spare
# MaxSpareServers: maximum number of server processes which are kept spare
# MaxClients: maximum number of server processes allowed to start
# MaxRequestsPerChild: maximum number of requests a server process serves
<IfModule mpm_prefork_module>
    StartServers          5
    MinSpareServers       5
    MaxSpareServers      10
    MaxClients           150
    MaxRequestsPerChild   0
</IfModule>

这个已经说的很清楚了，对于现在的服务器配置，尝试MaxClients 修改成 40

再次查看系统性能

top - 13:44:13 up 4 days, 18:12,  2 users,  load average: 12.10, 6.50, 8.88
Tasks: 209 total,  41 running, 168 sleeping,   0 stopped,   0 zombie
Cpu(s): 91.7%us,  7.9%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.3%st
Mem:    501892k total,   399804k used,   102088k free,     6936k buffers
Swap:        0k total,        0k used,        0k free,    71048k cached 

这是-c 100 已经没有问题了。

Speed=2780 pages/min, 52868 bytes/sec.
Requests: 2780 susceed, 0 failed.

之前常用的部署代码就是用svn，或是更老土的ftp。今天在写一个新玩具的时候，突然发现，每次的git pull实在是一个让人烦躁的东西，就网上查找了一下，整理在这里。参考原文

实现原理是当我们push 代码到remote repository时，通过git的post-receive hooks。执行

git checkout prod -f

来帮助我们实现自动部署

让我们从最简单的开始，现在本地创建一个git repository

$ mkdir test && cd test
$ git init 
$ echo 'Hello, world!' > index.html
$ echo 'Hello, world!' > index.html
$ git add index.html
$ git commit -q -m "The humble beginnings of my web site."

index.html 就是我们希望能够部署到服务器的代码

然后在服务器创建一个repository, 这里可不是服务器部署代码的位置

$ mkdir test.git && cd test.git
$ git init --bare
$ cat > hooks/post-receive
#!/bin/sh
GIT_WORK_TREE=/mnt/www/test git checkout prod -f
$ chmod +x hooks/post-receive

这是服务器的git代码目录

/repo/test.git

这里的 ‘/mnt/www/test’ 就是我们将要部署服务器代码的位置，一般的lamp，我们喜欢放在www里，当然这里需要根据不同的环境更换就好了。

这里我们在本地的git目录下增加一个remote

$ git remote add prod ssh://server_address/repo/test.git
$ git push prod +master:refs/heads/master

server_address 可以ip，域名。

我不太喜欢用这个命令行，我喜欢用SourceTree来做这个增加remote和最后的commit push 部分。

这时我们切换到服务器目录下，就可以看到我们的index.html 在我们向prod push的之后，已经自动check out 到我们指定目录下了。

之后我们只需要修改完成之后，git push prod 就可以自动部署代码了。

第一次用，这里标记一下，看看后面当发生冲突的时候，时一个什么样的情况。： ）

ruby on rails

mysql2 image not found soluation