Recently in python Category

 

发信人: draculalord ( 嗯?), 信区: Python
标 题: 也谈链表及其他Re: python标准库貌似没有实现链表?
发信站: 水木社区 (Mon Mar 21 18:49:46 2011), 转信

实际上刚开始学习一些高级语言的时候我也有同样的疑问,而且即使有链表对应物的语言,链表常常也很少被实际使用。
如果是在国外听数据结构的课,老师一般会警告你这只是一个理论概念,实际应用应该实际考察,在通常情况下链表不是一个很好的结构。
通常链表会作为一个很好的反例,告诉大家脱离实际硬件环境来谈论所谓算法复杂度是没有任何意义的。
这是因为,链表已经不适合当今的计算机硬件发展。当今的计算机硬件对内存是否连续更为敏感,而链表恰恰会破坏这种顺序读取。
由于locality很差所以常常造成page fault和cache miss
这也是为什么大多数教师不再推荐使用链表的原因。而且现今的硬件内存拷贝实际相当迅速。
并且python的list算法不是通常的单项表,也不是通常的数组。
具体可以看这里:http://wiki.python.org/moin/TimeComplexity
在List末尾append/pop都是O(1)的,
如果要在头部或者中部插入是O(n),任何破坏连续性的操作都会被要求realloc,所以任何此类操作都是O(n)
但是当今的常用硬件,使用C写的链表和python的list,在insert的时候只有n>50000才让链表比list快那么一点点。
这还没有考虑其他实际操作的复杂度。加上前面说的破坏locality,导致链表完全没有吸引力。在对象特别多的时候通常我们直接抽象它为数据库,也不要去想什么链表了。

在需要用到linked list特性的地方,比如常常需要从头部append或者pop
这时候有python的deque. (这里我记错了,特此更正,deque如果做insert还是会导致内存拷贝/移动,这里面的关键思想就是目前硬件的内存拷贝相当快,不是相当长的东西都可以接受)
deque也不是通常的简单数据结构,它是经过认真权衡过后得到的一种混合式数据结构。
他是一个链式块结构,每个块包含62个对象,以此来平衡对locality的优化和对push, pop的优化。有人问为啥是62个而不是其他数:那是因为deque是个双向链表,一个节点64个指针,一个指向前一个指向后,剩下就是62个指针用来指向对象

要做到对insert到中间的优化是用btree和array结合的办法,有个第三方包blist
但是我估计很少有应用会真正用到这个。insert是O(log n)
http://pypi.python.org/pypi/blist/

其实python是大师设计的语言,他们来决定底层具体的数据结构,作为一般人,你没有必要去质疑大师们精心设计的东西。
如果你真的对性能有很大要求,python也许并不适合你,python不是作为纯粹针对高性能计算诞生的东西,
他是一种胶水语言,它只对常见的List长度,常用的算法结构进行优化。他希望达到的目的是把现实的应用抽象出来,让使用者不用关心具体的数据结构和算法。
pythonic是一种面向大众的编程态度

如果你要用它来做其他事情,可以看看有没有你需要的第三方模块,或者可以用C来实现自己的一个模块,python本来就是C写的,所以这实际上也一点不困难。
比如python里面没有一个数据结构是能用来很好表示数值运算中使用的大型矩阵或者数组的,这时候就诞生了第三方包:numpy

GAE需要python2.5支持,而ubuntu从10.04开始就只支持python version >= 2.6了, 所以只能自个去编译python2.5了

----------

ubuntu10.04已经默认安装了python2.6

sudo apt-get install libssl-dev libsqlite3-dev sqlite3

 Python 自带的sqlite3模块只是sqlite的一个接口,包含实现部分, 需要先安装sqlite3再编译python,否则会找不到模块

下载python2.5源码, 解压缩

vim /Path/to/Python-2.5/Modules/Setup.dist

将如下行修改为(去掉开头的#号):

204:# Socket module helper for SSL support; you must comment out the other
205:# socket line above, and possibly edit the SSL variable:
206:SSL=/usr/local/ssl
207:ssl ssl.c
208: -DUSE_SSL -I$(SSL)/include -I$(SSL)/include/openssl
209: -L$(SSL)/lib -lssl -lcrypto

保存退出 => ./configure => make  => make altinstall

 

去http://pypi.python.org/pypi/ssl/1.15下载ssl-version.tar.gz并安装

去http://www.pythonware.com/products/pil/下载Imageing-version.tar.gz并安装

以上两条命令都是python2.5 setup.py install

 

安装easy_install:

wget http://pypi.python.org/packages/2.5/s/setuptools/setuptools-0.6c11-py2.5.egg

sh setuptools-0.6c11-py2.5.egg

安装gae所需的django

easy_install-2.5 django==1.1.1

 

==========================

到此就安装完毕了

执行python2.5 /usr/local/lib/python2.5/test/test_socket_ssl.py 进行socket ssl测试

正常的话会打印出:

test_rude_shutdown ...
test_basic ...
test_timeout ...

执行python2.5并import sqlite3 ,无错则sqlite3正常

---------------------------------------

ubuntu 10.10应该也可以如此安装,但是10.04是LTS, 没有去测试10.10

 

参考文章:

GAE Python SDK on ubuntu 10.10 - SSL, Sqlite problems

relat - python25

Run GAE SDK for Python and Django on Ubuntu Maverick

Python SQLite 编程

ubuntu下安装python2.5.4支持ssl

在使用RRDTool的Python Lib库的时候, 每次都要import rrdtool-python-lib的绝对路径

import sys

sys.path.append('/usr/local/rrdtool-1.2.27/lib64/python2.4/site-packages/')

import rrdtool

import tempfile


rrdpython文档中说只要运行site-python-install这个命令就可以不用append那么长了囧, 作为一个python初心者我只能updatedb然后locate site-python-install. 然后CentOS告诉我没有...
G, 在rrdtool 1.3.1的Makefile中发现了这么一段.
site-perl-inst: site-perl-install

site-perl-install: all bindings/perl-piped/Makefile bindings/perl-shared/Makefile

cd bindings/perl-piped && $(MAKE) install

cd bindings/perl-shared && $(MAKE) install

site-tcl-install: all

cd bindings/tcl && $(MAKE) tcl-install

site-python-install: all

cd bindings/python && $(PYTHON) setup.py install


OK, 在安装完之后,进入/PATH/TO/RRDTOOL-VERSION-SRC/bindings/python目录
执行
python2.4