这几天手机上的待办事项里一直提醒着要做总结了，去年的年终总结迫于压力删除了，找都找不回来啊……所以以后的总结就隐去隐私部分吧：）不过，大概记得的3个都实现了，充分说明这玩意还是挺神的，冥冥之中会推动自己实现它们。
2013年，其实还算过得比较充实的，消化了不少技术类书籍：

• Python编程实践
• 程序语言的奥妙 : 算法解读
• SQL反模式 : SQL反模式
• 黑客与画家 : 硅谷创业之父Paul Graham文集
• MySQL性能调优与架构设计
• 简约之美 : 软件设计之道
• Python学习手册
• 深入浅出 Python
• 代码整洁之道
• Python编程
• CouchDB指南
• MongoDB指南

也参加了不少的技术会议，但是总感觉国内的企业没几家是在耐心积攒和发展技术的，全都是一股脑地用最新技术忽悠一阵……好了，咱没有文学青年的细腻，只好继续用问答式的总结模板了。

1. 今年你所完成的最重要的事情是什么？
   

* 成功从职场菜鸟转化成普通员工，顺便喂饱自己了，职业上发展还算顺利

2. 今年你所学到的最有用的是什么？
   

* 各种Python技术点，NoSQL入门

3. 满分10分，你在这一年对自己的满意度有几分？
   

* 总评：6分 及格

4. 你明年想要实现什么，要不要来个前所未有最棒的一年？
   

* **把《Data Structures and Algorithms Using Python》翻译完**
* 能换到Douban, Mozilla, Opera，Redhat其中之一
* dumpjs能上线，赚回租费
* 微健身，不求肌肉只求少点感冒
* 至少旅游一次

5. 如果现在是明年的12月31​日，你最想在你的生活中见到什么？
   

* 手上有《**Data Structures and Algorithms Using Python》的译本**

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

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

进入正题

前面就介绍下这本书，接下来是里面各种经典算法的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的配置也十分简单，也有很多样例，网上可以搜到的。这里也不多说啦～ 讲错的地方，欢迎拍砖