• 程序就像食谱，严格跟着食谱做饭，味道绝对不会差到哪里去，但是可能就不太好吃。
• 算法对于程序员，就像棋谱对于棋手，可能一时半回没啥用，但最终认得棋谱多的棋手始终会获胜的
• 链表的实现就像出门买杂货，逛完肉店买肉，然后再到鱼店买鱼，店之间并没有联系，但使之串起来的是自己的购物单，这张单子就是链表

还有很多对于计算机概念的有趣解释，大家就自己看吧 🙂

进入正题

前面就介绍下这本书，接下来是里面各种经典算法的Python实现，问题和算法神马的大家看书就好了～我就不摘抄了。 有错欢迎指正。

第47节：辗转相除法

或称欧几里得求最大公约数算法

#!/usr/bin/env python
# encoding: utf-8
def Euclid(x, y):
if x < y:
tmp = x
x = y
y = tmp
while y != 0:
rod = x % y
x = y
y = rod
return x
if __name__ == '__main__':
print Euclid(126, 90) # should be 18

第50节：桶排序

#!/usr/bin/env python
# encoding: utf-8
def bucket_sort(lis):
max_item = max(lis)
bucket = [-1 for x in xrange(max_item+1)]
for item in lis:
if item < 0:
raise ValueError("Can't handle %d" % item)
bucket[int(item)] = item
return filter(lambda x: x != -1, bucket)
if __name__ == '__main__':
print bucket_sort([8,2,1,5,9,7]) # should be [1,2,5,7,8,9]

第51节：基位排序—-桶排序的升级版

#!/usr/bin/env python
# encoding: utf-8
from copy import deepcopy
def bit_sort(lis):
bucket = [[] for x in xrange(len(lis))]
k = len(str(max(lis))) # sort time
array = [deepcopy(bucket) for x in xrange(k)]
for time in xrange(k):
if time == 0:
for l in lis:
array[0][int(str(l)[-1])].append(l)
else:
for b in array[time-1]:
for item in b:
try:
array[time][int(str(item)[-1-time])].append(item)
except IndexError:
array[time][0].append(item)
return array
if __name__ == '__main__':
for line in bit_sort([123, 602, 82, 777, 57, 510, 396, 196, 843, 138]):
print line
print "The Last line should be:[[57, 82], [123, 138, 196], [], [396], [], [510], [602], [777], [843], []]"

郭嘉统计局虽然经常更新地区数据，但是其数据结构糟糕透顶，plain
HTML有没有！都不提供SQL或者是XML数据类型！ 都还得写个解析器来加载这个结构，用LXML解析的过程我就不写了
去除各种table之后的数据库

110000 北京市 110100 市辖区 110101 东城区 110102 西城区 110105 朝阳区 110106 丰台区 110107
石景山区 110108 海淀区

转换以后：

省:北京
   ├─ 市辖区
   │  ├─ 东城区
   │  ├─ 西城区
   │  ├─ 朝阳区
   │  ├─ 石景山区
   │  ├─ 海淀区
   │  ╰─ 平谷区
   ╰─ 县
      ├─ 密云县
      ╰─ 延庆县

规律就是邮政编码！用了groupby和defaultdict这些基本的Python东西 下面是程序啦，用法是直接打省份的名称即可。
当然，函数已经是单独实现的，所以在其他地方用也行啦～

#!/usr/bin/env python
# encoding: utf-8
from itertools import groupby
from utils import ScaleTree
def make_city_tree(path):
"""
 make a tree of province, city, county of China

 :path: path to database
 :returns: tree

 """
def strip_zipcode(item):
"""
 Strip all zipcode from stats.gov.cn
 :returns: city_name
 """
return item[7:].decode('utf8').strip()
with file(path, 'r') as db:
tree = ScaleTree()
provinces = groupby(db, key=lambda x: x[:2])
for pid, province_data in provinces:
province_data = list(province_data)
province_name, cities = strip_zipcode(province_data[0]), province_data[1:]
for cid, city_data in groupby(cities, key=lambda x: x[:4]):
city_data = list(city_data)
city_name, counties = strip_zipcode(city_data[0]), city_data[1:]
tree[province_name][city_name] = map(strip_zipcode, counties)
return tree
if __name__ == '__main__':
tree = make_city_tree('db.txt')
pro = unicode(raw_input('省:'), 'utf8')
for x in tree.keys():
if pro in x:
cities = tree.get(x)
for t, city in enumerate(cities):
if t+1 != len(cities):
st = u"├"
else:
st = u'╰'
print u"\u2004\u2004\u2004%s─\u2004%s" % (st, city)
for d, county in enumerate(tree.get(x).get(city)):
if d+1 != len(tree.get(x).get(city)):
st = u"├"
else:
st = u'╰'
if t+1 != len(cities):
ct = u"│"
else:
ct = u"\u2004"
print u"\u2004\u2004\u2004%s\u2004\u2004%s─\u2004%s" % (ct, st, county)

最近换工作，面了几家公司，超大，大，中，小都有，不过就不提名字了。 唯一的感触就是自己实在是太浪费四年的时间在游戏上了，要是腾出时间搞算法那是极好啊。
不过我总觉得知识的欠缺是可以通过学习来弥补的，同时，记录也是学习的一部分，现在我就写写我还记得的几道面试题。

骑士巡游问题

一道简单的BFS（广度优先）算法题

在一个国际象棋棋盘上 (NN)，有一个棋子"马(Knight)"，处在任意位置(x, y)；
马的走法是日字型，即其可以在一个方向上前进或后退两格，在另一方向上前 进或 后退一格。 请编程找出马如何从位置(x, y)走到棋盘右下角(N,
N)的位置的步骤。 例如：假设棋盘大小为33，马处在（1，2）位置，马只需要走一步， 即 (1,2)-> (3,3)即可到达目的地。

具体代码我已经push到github上了，链接在此
对于从来没有研究过算法的我来说，整个题目的难处在理解队列这个概念上。
广度优先的队列之奇妙的地方在于，每一层的尝试，都先放入队列中，紧接着，挨个判断队列中的元素是否达成了目标。对，就这么简单。

Fibonacci数列

好吧～两家公司都考这斐波那契……

用Python生成指定长度的斐波那契数列

考递归：

def fib_recursion(n):
if 0< = n < 2:
return 1
else:
return fib_recursion(n-1)+fib_recursion(n-2)
print fib_recursion(99) # 调用即可

不错吧～完美地使用了递归，当然，如果能用字典存储，这样更完美了对吧？ 错！ 其实考的是iterable的使用，Python CookBook
19.3里那极为精妙的解法才可以称得上答案：

def fib():
x, y = 0,1
while True:
yield x
x, y = y,x+y
if __name__ == '__main__':
import itertools
print list(itertools.islice(fib(), 10))

LRU缓存

现场编程题，1小时之内写出可用的LRU cache util

其实当场没有写出来，主要是因为还不清楚list的pop()中如果有数字的话，就是O(n)的复杂度，我当时的水平最多写得出[这个源里的程度](https://github.com/mengzhuo
/django-lru-cache)。用的是dict的popitem，而且是面试官说在生产系统中也使用这样的方法。 后来，仔细看了Python
Cookbook（知道是好书了吧），发现collections的deque神器，不过正反向双list也是个不错的ADT选择，而且这些连面试官都不知道。
具体的应用以后写读书笔记时会和大家分享下的。

如果各位同学在coding过程中，需要打印变量，捕捉异常，但只能用print变量的方法解决问题，而你觉得不优雅，不方便，急需一种调试的方法的话，那这篇文章很适合你。
我学这些是因为在Django调试中，平时使用默认的Error
Page已经是非常方便了，但是，有次在对外API测试中可能会出现无法查看那个错误页的情况，两眼瞎，四处pirnt，最后还不能解决问题……如此屈辱后，我等痛下决心，一定找到更好的解决方法，因此有了本文。技巧

ipdb断点法［排错／尝试］

在你想打断点的地方，加上这句—-需要安装ipdb

import ipdb;ipdb.set_trace()

[](blog/wp-
content/uploads/2012/11/2012-11-17-213312的屏幕截图.png)

当程序运行到这里时，在启动服务器的console中将会弹出上面的提示符。这时就可以在这里像使用console编程时一样地随心所欲了～
顺便推荐几个好用的快捷键

有了这招，基本的疑难杂症都可以debug掉了～

logger大法［定位／记录］

这是今天的主角，相对上面的方法，这个的自动化程度不是一般的高，在不改变源代码的情况下就可以记录所有的django行为。
在Django的settings.py里面，可以看到下面这自动添加的LOGGING这个设置变量。默认情况下，Django只会在DEBUG=False时，当服务器遭到500错误，才会发邮件给admins。而我们现在要在代码中加入一个logger，这样，任何错误或者是希望打印出来的信息都不会逃走啦～而且还可以自定义等级记录哦～
在settings.py中

from logging.handlers import SysLogHandler
LOGGING = {
'version': 1,
'disable_existing_loggers': False,
'handlers': {
"syslogHandler":{
"class":"logging.handlers.SysLogHandler",
"formatter":"verbose",
'address': '/dev/log',
"facility":SysLogHandler.LOG_LOCAL6
},
},
'loggers': {
"project":{
"handlers":["syslogHandler"],
"level":"DEBUG", #整个project的logger等级为DEBUG
},
"project.app":{
"handlers":["syslogHandler"],
"level":"INFO", #而project下的app对应的是INFO等级
},
},
"formatters":{
'verbose': {
'format': '%(levelname)-8s[%(name)s][%(funcName)s:%(lineno)d] %(message)s',
},
}
}

在某些你想记录log的地方

import logging
logger = logging.getLogger(__name__)
logger.error('This is an error')

注意这个__name__，返回值是app+文件名，有利于我们定位bug和使用不同的handler，比如下面的传递路径示意：

[](blog/wp-
content/uploads/2012/11/2012-11-20-220942的屏幕截图.png)

如果一条log信息被project.app.views的handler抓住了，并且，propagate=False时，父级的handler，比如"project.app"，就不会收到此log。
至于logger语句放在哪里，我个人习惯跟着try except这段，用于捕捉异常，或者在方法开始时logger.info查看相关参数。
而logger默认等级有6种：NONE, DEBUG, INFO, WARNING, ERROR, CRITICAL(严重等级由低到高)
至于logger输出目的地，有很多种选择，可以输出到文件，邮件，http请求，也可以输出到syslog中。本文的例子就是输出到syslog中。
至于syslog的配置，网上也有不少好的文章，这里就不说了 当然这些logger等级时会在%(levelname)这个变量中出现，而一般的tail -f
最多只是输出他们，并不能主观地区分他们。所以需要另一个工具进行等级的划分和关键词的渲染（syntax
highlighting）。这里就严重推荐grcat这个小工具，能正则匹配，关键字各种格式化。

![日常例子一枚](/2012/12/2012-12-16-145748的屏幕截图-
610x214.png)

grcat的配置也十分简单，也有很多样例，网上可以搜到的。这里也不多说啦～ 讲错的地方，欢迎拍砖

本文献给那些看着参差不齐的中文文档／教程，但还在坚持折腾以上两个工具的童鞋。

声明：本人也是菜鸟，真正的有用的概念解释，请参看官方文档，以下都是我的个人理解。

virtualenv

这里是导言吗？ 用过Python的同学，肯定会对Python及程序的版本之间经常更换的api感到痛苦不以。就拿我折腾的Django来说吧，公司服务器上跑的是Django1.3、同事也是用1.3开发，但是因为我是新来，一个pip install django下去，就是1.4.2。好了，你自己写的Django Project自然没有问题，自己本地测试也没有问题。但是要和其他人交流的时候就蛋疼了，因为你的1.4.2跑不了1.3的程序……当然，这时，你可以选择卸载自己本地的Django，换成1.3，等你要重新测试自己的Django，怎么样，扯着蛋了吧。为了解决以上问题，virtualenv横空出世了。 正文 为了解决以上蛋疼问题，我们需要安装virtualenv。 sudo pip install virtualenv 安装好了以后，就可以在任何目录下新建一个virtual-environment（我更喜欢叫：盗梦空间），当然一般我习惯在项目的边上创建一个$project_name-env。例如： virtualenv demo-env 这下，只需要 source demo-env/bin/activate 就可以激活这个虚拟环境了。如下图所示： 注意到括号里的(demo-env)了没？对，我们已经进入了第一层梦境demo-env。 回到导言里的问题，我们需要在这里建立一个使用django1.3的环境，不让它干扰我们的本地环境。 pip install Django==1.3就可以了，然后在里面运行别人的Django程序，没有问题！装很多python程序，没有问题，这些都不会干扰你的本地环境，放心破坏吧！

PIP

刚才的virtualenv的介绍里已经说了pip的安装命令了。但你当pip只是个安装工具的话，那就大错特错了。pip还有一个更重要的功能—-
冻结当前梦境开发环境版本（freeze）。 pip freeze 看到了刚才安装的django
1.3了没有？这就是我们目前的生产环境，把这输出结果写到requirement.txt里，别的程序猿们就知道你的程序至少在这个环境下可以跑，这时他们拿着requirement.txt，新建个virtualenv，pip install -r requirement.txt 就可以运行你的程序了。 pip加速安装
通过pip安装程序，还可以用git和svn的方式，具体操作网上也有。但是对于懒人来说，直接用pip是最好不过的了，但是，有时这会很慢！！！慢到你抓狂。当然
，和apt-get一样，pip也可以换源，或者叫添加镜像。 新建一个~/.pip/pip.conf，往里面写入

[global]
index-url=http://e.pypi.python.org/simple
timeout = 30 require-virtualenv = true
download-cache = /tmp
[install]
use-mirrors = true
mirrors = http://d.pypi.python.org http://b.pypi.python.org http://c.pypi.python.org

下载应该就会像飞了一样，配置文件过于清晰，所以我也不用多说了吧 ：）