Python标准库小窥[1]:weakref

平时工作经常能碰到一部分标准库的代码,但是常常因为琐事没有细细地研究这些标准库,直到最近发觉Python不愧是battery
included的语言,因此决定从PyMOTW好好学学。 那么就从最常见,但最容易忽略的weakref开始吧!
先让我们看看weakref想解决什么问题。 PyMOTW是这样说的:

Refer to an “expensive” object, but allow it to be garbage collected if
there are no other non-weak references.

引用一个"开销大"的对象,并在只剩下弱引用时允许垃圾回收机制回收这个对象。 PyMOTW中的例子
当obj被显式地删除后(模拟gc回收了),弱引用的proxy和ref的引用对象消失了,不能再取回了。 达到了之前希望的只剩下弱引用时允许回收。
如果还有强引用,这些弱引用仍能正常获取值。 问题就来了,这个蛋疼的东西到底有什么用? 那就是当个智能Cache
比如你有一堆图片文件buffer,你希望通过字典类组成一个cache来存储它们,以获得可观的O(1)读取速度。但是,当这个cache中的图片越来越多时,由于Python自带的gc(垃圾回收机制)没办法收回字典内引用了的项,导致cache越来越大,内存消耗加大,可你又不想用其他方法暂存这些数据到硬盘(因为慢啊!),这时,如果有种方法让这些存储项能自动清除,并能该有多好!
这就是PyMOTW中的Cache例子
可以看到,使用dict的例子中,如果删除了所有引用(all_refs),cache仍然保留着这些"开销大"的对象,而用WeakValueDictionary就完成了正常回收的过程,保证了cache不会过多地占用系统空间。
还有一种用途,就是保证循环引用可回收 比如有以下节点 A B C,他们相互有指向下个节点的引用(->)表示

A->B
B->C
C->A
即A->B->C->A

当这个引用形成了环形时,如果把其中两个节点(B、C)删除掉,这个环仍能正常工作,

A->B->C->A

但是当我们删掉最后的A节点后,gc就不明白该不该回收这些节点,因此,造成了内存泄漏(leaking) 这个情况正如PyMOTW所示:

After 2 references removed:
one->two->three->one
Collecting...
Unreachable objects: 0
Garbage:[]
Removing last reference:
Collecting...
gc: uncollectable
gc: uncollectable
gc: uncollectable
gc: uncollectable
gc: uncollectable
gc: uncollectable
Unreachable objects: 6
Garbage:[Graph(one),
 Graph(two),
 Graph(three),
 {'name': 'one', 'other': Graph(two)},
 {'name': 'two', 'other': Graph(three)},
 {'name': 'three', 'other': Graph(one)}]

如果使用弱引用的dict就没有这个问题啦~ 注意,由于WeakDict是构建于dict之上的,因此,不要遍历(iter)这个对象,因为里面的值随时发生变化

Python如何查找Follow关系

Twitter中Follower和Followee,现需要找到互相关注的两个人(不关心顺序) 例如:现有列表

 l = [(1, 2), (2, 3), (3, 2), (3, 4), (4, 1),
(4, 3), (4, 3)]

可以通过下列函数生成

def gen_pairs():
return (random.randint(0, 30), random.randint(0, 30))
l = [gen_pairs() for x in xrange(20)]

解法一:

import collections
[x for x, y in collections.Counter([tuple(sorted(x)) for x in l]).iteritems() if y > 1]
  1. [tuple(sorted(x)) for x in l] 首先是将列表的内容按小到大重新排列
  2. 通过计数器collections.Counter,来统计重复的数量
  3. if y > 1 将大于一个的放入结果集中

最后统计用时best of 3: 38.9 µs per loop 老湿,还能给力点吗? 解法二:
[Stackover上的解答](http://stackoverflow.com/questions/22161370/algorithm-to-find-
follow-relationship-like-twitter/22161585#22161585 “Stackover上的解答” )

[x for x in set_l if x[::-1] in set(l)]

快了6倍……答主说到这个算法最快也就是O(n)了,因为必须遍历所有项有木有啊!

2013年终总结

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

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

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

  1. 今年你所完成的最重要的事情是什么?
    
* 成功从职场菜鸟转化成普通员工,顺便喂饱自己了,职业上发展还算顺利
  1. 今年你所学到的最有用的是什么?
    
* 各种Python技术点,NoSQL入门
  1. 满分10分,你在这一年对自己的满意度有几分?
    
* 总评:6分 及格
  1. 你明年想要实现什么,要不要来个前所未有最棒的一年?
    
* **把《Data Structures and Algorithms Using Python》翻译完**
* 能换到Douban, Mozilla, Opera,Redhat其中之一
* dumpjs能上线,赚回租费
* 微健身,不求肌肉只求少点感冒
* 至少旅游一次
  1. 如果现在是明年的12月31​日,你最想在你的生活中见到什么?
    
* 手上有《**Data Structures and Algorithms Using Python》的译本**

《程序语言的奥妙》之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)