mzh/blog

《程序语言的奥妙》之Python实现--Part1

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

进入正题

前面就介绍下这本书,接下来是里面各种经典算法的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], []]"

中国县及县以上地区数据结构【Python】

郭嘉统计局虽然经常更新地区数据,但是其数据结构糟糕透顶,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)

最近一些面试题(Python)

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

骑士巡游问题

一道简单的BFS(广度优先)算法题

在一个国际象棋棋盘上 (N*N),有一个棋子”马(Knight)“,处在任意位置(x, y); 马的走法是日字型,即其可以在一个方向上前进或后退两格,在另一方向上前 进或 后退一格。 请编程找出马如何从位置(x, y)走到棋盘右下角(N, N)的位置的步骤。 例如:假设棋盘大小为3*3,马处在(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)的复杂度,我当时的水平最多写得出这个源里的程度。用的是dict的popitem,而且是面试官说在生产系统中也使用这样的方法。 后来,仔细看了Python Cookbook(知道是好书了吧),发现collections的deque神器,不过正反向双list也是个不错的ADT选择,而且这些连面试官都不知道。 具体的应用以后写读书笔记时会和大家分享下的。

Django调试方法三枚

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

ipdb断点法[排错/尝试]

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

import ipdb;ipdb.set_trace()

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

按键含义
lline:查看指定行,例如l 31
rreturn:执行到当前函数返回
ccontinue:继续执行代码,直到下个断点
whatis查询某个变量是什么

有了这招,基本的疑难杂症都可以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,比如下面的传递路径示意:

如果一条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这个小工具,能正则匹配,关键字各种格式化。

日常例子一枚

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

Virtualenv和pip小探

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

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

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

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