但是目前 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。

主要的问题是 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 里配置。(吭爹的名字，八杆子打不着)

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

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 年产权的商品房里，腾出来的大片土地就又是一笔财源。只要忠厚的中国人都不说话，政府又何乐而不为？

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 即可。

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

这其实是 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 即可。

这些函数有什么相同之处呢，它们都是用来创建新的文件描述符的 (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

某智现在做的，还算是在忍受范围内，没有之前那一堆“火狐魔镜”之类的东西了。不过依然让人不爽，比如默认搜索引擎设成 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”)。所以最后的这个换行应该特殊处理。

http://www.quora.com/Apple-Inc-2/Is-Apple-really-going-to-try-and-kill-Google

拭目以待吧。

P.S. 我本来要发 twitter 的，结果这字数限制实在让人崩溃，一句话都说不完。还是自家地盘爽。

刚发现了 screen 的这个选项，使能之后，退出程序或者按 ctrl-z 之后不会留下“残余”。

1
2
3
4

altscreen on|off

If  set to on, "alternate screen" support is enabled in virtual terminals,
just like in xterm.  Initial setting is `off'.

(git 需要设置下 pager，linuxtips.manki.in):

1

git config --global core.pager 'less -+X -+F'

• 首先环境变量 TERM 应该设成 xterm-256color (保证你有这个文件 /usr/share/terminfo/x/xterm-256color)。

在 ~/.bashrc 里写

1

export TERM=xterm-256color

但是要注意的是，这一行必须写在导入系统设置之前，也就是这样

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

# User specific aliases and functions

export TERM=xterm-256color

# Source global definitions
if [ -f /etc/bashrc ]; then
        . /etc/bashrc
fi

if [ -f /etc/profile ];then
        source /etc/profile
fi

否则，就是这副很普通的样子，

正确的话是这个俨然闪闪放光的样子，

所以默认的 .bashrc 把 “User specific aliases and functions” 放在前边，还是大有深意的。

(当然，影响的只是 ls，vim 等应该不受影响。)

• screen 里不需要特殊的配置。有人提到需要换成 screen-256color (在 .screenrc 里写 term screen-256color)，但是我在 fedora 17 上没遇到什么问题。

• 然后是 solarized 的主题，就不细说了，把 gnome-terminal 和 vim 设好就 ok。

P.S. vim 的 set t_Co=256，貌似是没有任何作用，跟我用了 solarized 的 colorscheme 有关？不管怎么设，vim 和 gvim 都是一个样子的。

P.S. 数学小贴士：完全平方数都有奇数个因子，其它整数都有偶数个因子。

搜索了一番，这里 提到了对 blogger 的 redirect。代码在这 (github.com)。

其实就是几条 URL 匹配规则。因为 octopress 虽然基本是静态的，但是其实是有一个小的 web 框架的 (sinatra)，所以还是比较灵活。

我把我用的 heroku 部署相关的东西放这了 (github.com)。octopress 需要的 patch 在这 (github.com)。

我这人特别不喜欢遇到 404 的链接，所以到了我迁移网站的时候，就理所当然要努力保证兼容性了。感谢 octopress，其实就是改个配置的事儿。

1
2

# file : _config.yml
permalink: /:year/:month/:title.html

然后用这个小工具把 blogger 上原来的文章和留言都抓过来。这段代码还有不少版本，我也是根据前人的稍微修改了下，具体使用的过程网上也有不少文章。这里还要感谢 blogger，把打包下载做得这么容易，让用户很容易就跑了。什么是大国心态?

然后由于我之前(好像)用的是 feedburner，所以这块就省事了，订阅我博客的人应该不需要什么改动。

然后写篇声明，写完后把 DNS 一改，就 ok 了，无缝迁移，哈哈。目前发现只有各个月的 archive 页面丢掉了，其它链接应该没有 404 的。

还有一点是，之前就开始用 disqus，所以留言也都还保留着。这个也很好，感谢 disqus。

网站放在 heroku 上，因为我不是很愿意把 blog 内容搞个 public repo，放到 github 上。但是 octopress 文档里的部署到 heroku 的方法不很 (很不!) 爽，因为要把生成的乱七八糟的内容都加到 repo 里。所以找了一个办法，给 octopress 打了个补丁:

还搜到了一个办法是利用 heroku 的 custom buildpack，嗯，太复杂。

octopress 是挺漂亮的，但是在 google 的过程中，发现大家都长一个样…

用 markdown 写的第一篇 blog，撒花。

P.S.

feed 还是出问题了，如果之前订阅的是 http://blog.zhangsen.org/feeds/posts/default, Google Reader 其实记录的仍然是这个地址，而不是重定向的 feedburner，TODO, FIXME。