我总是后知后觉，现在才开始折腾 goagent。之前买过 VPN，最近一直用 ssh tunnel。试了 goagnet 才发现真心好用啊。

但是目前 GAE 貌似大面积被封了，所以 goagent 一开始安装都有问题，根本没法传到服务器上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

$ python uploader.zip
APPID:zhngsn-p4
Application: zhngsn-p4 
Host: appengine.google.com
INFO - - [Jul 21 17:45:56] Server: appengine.google.com
Rolling back the update.
Traceback (most recent call last):
  File "/usr/lib64/python2.7/runpy.py", line 162, in _run_module_as_main
    "__main__", fname, loader, pkg_name)
  File "/usr/lib64/python2.7/runpy.py", line 72, in _run_code
    exec code in run_globals
  File "uploader.zip/__main__.py", line 10, in <module>
    main()
[...]
  File "uploader.zip/google/appengine/tools/appengine_rpc.py", line 365, in Send
  File "/usr/lib64/python2.7/urllib2.py", line 400, in open
    response = self._open(req, data)
  File "/usr/lib64/python2.7/urllib2.py", line 418, in _open
    '_open', req)
  File "/usr/lib64/python2.7/urllib2.py", line 378, in _call_chain
    result = func(*args)
  File "/usr/lib64/python2.7/urllib2.py", line 1215, in https_open
    return self.do_open(httplib.HTTPSConnection, req)
  File "uploader.zip/fancy_urllib/__init__.py", line 367, in do_open
urllib2.URLError: <urlopen error [Errno 32] Broken pipe>

墙很高啊。

尝试用 tsocks，通过现有的 ssh tunnel 上传，一样的 URLError。有人提到可以设置 https_proxy 环境变量，但是手上又没有 http 代理 (socks5 代理能转成 http 代理么) 。

本来要放弃了，但是转念一想，刚才我还上传了 GAE 上的一个小网站呢。于是用 google 官方的 GAE SDK 试了下，还真成了。

goagent 代码其实很简单，需要上传到 GAE 的 app 就在 server/python 目录下。

所以，到 server/python 目录下，编辑 app.yaml，把申请的 app 名字填到第一行:

1

application: your-app-name

然后，把官方的 SDK 下载下来后，

1

/path/to/google_appengine/appcfg.py update .

就 OK 了。没被重置，也不需要每次都输密码。如果申请了多个应用做负载均衡，就依次修改 app.yaml，运行 appcfg.py update，把每一个都部署上。

go 版本在 server/go, 应该是一样的。

部署完后 (我搞了四个做负载均衡) 运行 local/proxy.py。

一台机器上安的 fedora 17，是用 beta 发布安装的。文档中提到 beta 发布会自动升级到正式版本，不需要改什么配置，所以就一直没在意。但是过了一段时间后，就开始出问题了。

主要的问题是 yum update 的时候报一大堆的 404 错误。类似这样的，

1
2
3

http://mirrors.sohu.com/fedora/releases/17/Everything/x86_64/os/drpms/LibRaw-0.14.3-3.fc17_0.14.3-4.fc17.x86_64.drpm:
[Errno 14] HTTP Error 404 - Not Found :
http://mirrors.sohu.com/fedora/releases/17/Everything/x86_64/os/drpms/LibRaw-0.14.3-3.fc17_0.14.3-4.fc17.x86_64.drpm

不只 LibRaw 这个包，还有很多，NetworkManager, alsa-plugins-pulseaudio 等等等等。

这个 404 错误显然是 yum 试图用 drpm 来升级，而它尝试的地址都不对，在源里是不存在的。但是当单独升级每个包的时候，好像不会报错。

尝试了 yum clean all, 没什么作用。最后偶然发现很多包的 repo 信息是 @koji-override-0/$releasever，而正常情况下应该是 fedora, fedora-updates 这样的。

于是首先用 yum list extras 找出所有这样的不正常的包.

1
2
3

yum list extras [glob_exp1] [...]
      List  the  packages installed on the system that are not available in any
      yum repository listed in the config file.

把上边得到的列表用 sed/cut 处理一下，用一个 for 循环，一个一个地单独升级，就能修复到正确的 repo 了。

然后呢… 发现不好使，有的包还是会尝试用 drpm。

最后的办法是先暂时把 drpm 支持关掉。升级完再打开。

而支持 drpm 的特性叫做 presto, 在 /etc/yum/pluginconf.d/presto.conf 里配置。(吭爹的名字，八杆子打不着)

• Python (cpython) 的 dict 是用哈希表实现的。

• 碰撞的处理方法是 open addressing，因为 chaining 的 overhead 太高 (哈希表里记录的只是哈希值和相关的 object 的地址，不记录实际 object，所以如果用链表来做 chaining 的话，光 next 指针就占去了很多空间)。(不知道我理解得对不对)。

Open addressing is preferred over chaining since the link overhead for
chaining would be substantial (100% with typical malloc overhead).

• 一般的哈希表在选择哈希函数时，都希望产生的哈希值尽量随机，但是 python 的哈希函数不是这样的。dict 和其它一些地方使用的哈希函数其实就是 python 的内置函数 hash ，它的返回值非常的不随机。比如对于最重要的两种 key，整数和字符串，整数的哈希值就是它本身，而字符串的哈希值计算也很简单。且看

1
2
3
4

>>> map(hash, (0, 1, 2, 3))
[0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
[-1658398457, -1658398460, -1658398459, -1658398462]

这样的好处是如果 key 是连续的整数或者字符串，几乎不会有碰撞。而且哈希值基本都是连续的，效率也比较高。

• 有时候，好处也是坏处。这样做的坏处是，表里会有数据连续地存在一块，而不是相互散开 (这正是哈希表，也称散列表的意义所在啊)，也就是，一旦有碰撞发生，用线性探测的方法来寻找可用位置是绝对不可行的。python 用的探测方法是一种 quadratic probing，保证不会受到连成块的数据的影响。

• 既然是使用 open addressing，也就是说整个哈希表存储在一段连续的内存中，或者说是一个数组 (dict 是用 C 实现的)。这意味着，当数组快满时 (比如超过 2/3)，需要把数组扩大 (resize)。

• python 保证在修改元素的时候不会发生 resize，也就是保证了可以一边遍历 dict，一边修改元素。但是其它的操作就不一定了，所以会有这样的错误:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

>>> a = {1:2, 3:4}
>>> for k in a:
...  del a[k]
...
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: dictionary changed size during iteration

>>> a = {1:2, 3:4}
>>> for k in a:
...  a[2*k]=1
...
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: dictionary changed size during iteration

参考

• http://www.laurentluce.com/posts/python-dictionary-implementation/

• http://hg.python.org/cpython/file/tip/Objects/dictobject.c

• http://en.wikipedia.org/wiki/Hash_table#Collision_resolution

逻辑几乎相同的两段代码，python 比 C 慢 50 倍？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/* Find the sum of all numbers which are equal to the sum of the factorial of
   their digits. */

#include <stdio.h>

int solve()
{
    int f[10];
    int i, limit, sum;

    f[0] = 1;
    for (i=1; i<10; i++)
        f[i] = f[i-1]*i;
    limit = 7*f[9];
    sum = 0;
    for (i=3; i<=limit; i++) {
        int s = 0;
        int j = i;
        while (j>0) {
            s += f[j%10];
            j /= 10;
        }
        if (i==s)
            sum += i;
    }
    return sum;
}

int main()
{
    printf("%d\n", solve());
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Find the sum of all numbers which are equal to the sum of the factorial of
# their digits.

import math

def solve():
    f = [math.factorial(i) for i in range(10)]
    limit = 7*f[9]
    ret = []
    for i in range(3, limit+1):
        s = 0
        j = i
        while j>0:
            s += f[j%10]
            j /= 10
        if i==s:
            ret.append(i)
    return ret

print sum(solve())

1
2
3
4
5
6
7
8
9
10
11
12
13

$ time python 34-sum-of-digit-factorial.py
40730

real    0m5.053s
user    0m4.850s
sys     0m0.145s

$ time ./a.out
40730

real    0m0.115s
user    0m0.111s
sys     0m0.002s

这是 Project Euler 的第 34 题。

端午回家，又到村庄的农田旁边走了走。原本的良田，现在是这样了。

农田被圈成了工地，道路早已废弃许久。走在曾经被植被覆盖的乡间，竟然也能被吹一脸土。

围墙里是曾经的农田。

路对面的耕地还没有被征去，但是农民早不敢投入任何成本，随便种下的葡萄苗，只等着被征的时候多换点拆迁款。

收拾得这么干净，也是一种无奈吧。

真正让人震惊的，是后边不远处的烟囱。正在建的小区，是打算把附近的村庄拆掉，然后把村民都迁过来的。但是化工厂就在旁边，这是怎样的居心？

现在如火如荼的拆迁，显然就是地方政府的圈钱运动。而中央政府睁只眼闭只眼，道理也很简单，在中国是哪些人还有自己的土地？只有农民还在名义上拥有属于自己的土地。只要动用“拆”这个字，就能把所有人赶到了 70 年产权的商品房里，腾出来的大片土地就又是一笔财源。只要忠厚的中国人都不说话，政府又何乐而不为？

在 C 语言里，其实是可以动态分配二维数组的。只调用一次 malloc，就可以得到一个二维数组，并且支持 p[i][j] 这样的下标操作。代码如下:

1
2
3
4
5
6
7
8
9
10

int **alloc_2d(int rows, int cols)
{
    int **p, *data;
    int i;
    p = malloc(rows*sizeof(int *) + rows*cols*sizeof(int));
    data = (int*)(p+rows);
    for (i=0; i<rows; i++)
        p[i] = data + i*cols;
    return p;
}

释放的时候调用 free 即可。

再看我之前那些用一维数组模拟二维数组的拙劣代码，真是不堪回首。

生成素数的一般方法是用“筛”，古老的 Sieve of Eratosthenes，来生成 [1,n] 之间的所有素数。这里的问题稍有变化，要求计算某个区间 [m,n] 内的素数，其中 m 和 n 都有可能很大，但是 n-m 不大。

这其实是 SPOJ 上的第二道题 (PRIME1)。

由于 m 和 n 很大，所以不能用试除法 (trial division)，而且 Sieve of Eratosthenes 也不可行。

这种情况可以用分段的筛 (segmented sieve)。也就是先用 sieve 计算出 [1,sqrt(n)] 上的素数。然后用这个素数表，在 [m,n] 上再次应用 sieve，得到所求的素数。两次的筛都不是很大，可以放在内存中，而且速度也可以接受。如果 n-m 还是很大，还可以再次分成几段来做 sieve，这是这里的做法。 (我怎么觉得后面这种情况才是 segmented sieve 呢?)

一个类似的用这种分段策略的题目是，假设一个文件里有 4 billion 个整数，数字都是普通的 int，也就是有 32 位。要求找到一个不在这个文件里的整数，限制可用内存为 10MB 。

用一般的 bitmap 肯定是不行的。可以采用分段策略，通过两次遍历完成。把 2³² 这个区间分成若干段，第一次遍历求每一个区间中数字出现的个数。然后找出一个必然存在缺失数字的区间，对这个小的区间创建 bitmap，进行第二次遍历，找到一个缺失的数字。空间复杂度满足要求，因为假设有 M 个小区间，每个区间有 N 个数，那么 M*N=2^32，第一次遍历需要 M*4B，第二次遍历需要 N*4B (假设 bitmap 都用 int 数组)。所以 M 和 N 都取为 2¹⁶ = 65536 即可。

dup, pipe, epoll_create 这些函数都有一些变种，dup3, pipe2, epoll_create1 。为什么会这样？原因是这些接口设计时考虑不足，导致无法进行扩展，当新需求出现的时候，只能再添加新的接口。

这些函数有什么相同之处呢，它们都是用来创建新的文件描述符的 (file descriptor)。这个需求就是跟文件描述符相关。

在通过 fork/exec 创建一个新进程的时候，默认的行为是子进程继承父进程的所有已打开的文件。为了安全性，一般会把文件设成 close-on-exec，也就是说执行 exec 的时候，自动把文件关闭。否则的话，父进程的文件就会泄漏给子进程。

比如浏览器里，假设一个 tab 是银行付款页面，另一个 tab 是“某个”页面，这个页面需要用一个 plugin，而浏览器通过 fork/exec 来运行这个 plugin。如果文件描述符没有设置为 close-on-exec，那么银行页面的文件就有可能泄漏给这个 plugin。然后…

所以一般都会通过 fcntl 来设置一个 flag, FD_CLOEXEC，保证在 fork/exec 的时候自动关闭文件。但是由于 open 和 fcntl 之间总是存在一定的时间差，所以在多线程的程序里会有潜在的危险。一个办法是用锁，保证 open 和 fcntl 之间不会进行 fork，但是这并不可行 (且看引用原文的描述)。

最好的办法就是给 open 添加一个 flag，使得文件在打开时就已经设为 close-on-exec。

但是… 能打开文件 (也就是创建文件描述符) 的函数不只有 open。由于 UNIX 众所周知的设计特点，socket/accept/pipe/dup/epoll 都能创建文件描述符。而最大的问题是，不是所有的函数都像 open 那样有一个 flags 参数。比如 int pipe(int pipefd[2])。管道固然是个绝佳的概念，但是谁也没想到，后人竟然想对管道设置 flag。

但是为了保证原子性得设置 close-on-exec，必须要有 flag 参数，所以对这些函数只能创建新的接口，dup3, pipe2 等等就是这样来的。这个解决方案不算完美，但也没有更好的办法了 (比如 linus 提出过一个“间接系统调用”的方案)。

而另一些函数，比如 int socket(int domain, int type, int protocol)，虽然没有 flag，但有一个 type 参数。由于 type 的取值范围很有限，而且 type 和 flag 还算有点相似，所以开发者决定复用这个参数，把 SOCK_CLOEXEC 看作新的 type。这样函数接口就不需要修改了。

这样，所有能创建文件描述符的接口就都(相当于)有 flag 参数了，不仅可以用于设置 close-on-exec，而且也能方便将来的其它扩展。比如 XXX_NONBLOCK (现在已有)，和提了好久的 non-sequential file descriptor 的支持。

引用: udrepper.livejournal.com

端午回家，升级了下家里电脑的 firefox，发现主页竟然给改成 firefox.com.cn 上的一个地址了，又是某智做的好事。而且是默认项，“恢复默认设置”也不管用。解决办法是设成 about:home，就能恢复 firefox (真正)默认的主页了。

某智现在做的，还算是在忍受范围内，没有之前那一堆“火狐魔镜”之类的东西了。不过依然让人不爽，比如默认搜索引擎设成 baidu ，这符合 mozilla 的官方政策吗？再次怀疑 mozilla 搞这些的必要性。

翻译是一件看起来简单做起来难的事。在维基百科上查到了这么一段话，想翻译成中文，吭吃吭吃好不容易写完，感觉却还是佶屈聱牙。

“There is also some confusion whether newlines terminate or separate lines. If a newline is considered a separator, there will be no newline after the last line of a file. The general convention on most systems is to add a newline even after the last line, i.e. to treat newline as a line terminator. Some programs have problems processing the last line of a file if it is not newline terminated. Conversely, programs that expect newline to be used as a separator will interpret a final newline as starting a new (empty) line.” (en.wikipedia.org)

“换行字符可以看作是行的结束符，也可以看作行之间的分隔符，这两种处理方式之间存在一些歧义。如果换行字符被当作分隔符，那么文件的最后一行就不需要再有换行字符。但是多数系统的做法是在最后一行的后面也加上一个换行字符，也就是把换行字符看作是行的结束符。这样的程序在处理末行没有换行字符的文件时，可能会存在问题。相反地，有的程序把换行符看作分隔符，就会把最末尾的换行字符看作是新行的开始，也就是多出了一个空行。” (zh.wikipedia.org)

P.S. 写了个简单的 tail 程序，却总是多出一行来。结果发现，用 getline 等函数其实就相当于把换行符当作了分隔符，而不是结束符 (C++ 的 getline 的定义就是 getline ( istream& is, string& str, char delim ), 指明了 “delim”)。所以最后的这个换行应该特殊处理。