Archive for 算法-编程

作者写得很容易让人明白,真是好书。 Python创建一个对象时,比如PyIntObject,会分配内存,进行初始化。然后用一个PyObject *变量,而不是通过PyIntObject* 变量来保存和维护这个对象。在python内部各个函数直接传递的都是泛型指针 PyObject *。指针所指的对象是什么类型的我们不知道,只能从指针所指的对象的ob_type域动态判断(PyTypeObject),python正是通过这个域实现了多态   书上举了Print的例子 void Print(PyObject * object){ object -> ob_type -> tp_print(object) } 如果传给Print的指针是一个PyIntObject *,从PyObject指针找到ob_type指针再调用类型里对应的输出操作。作者在前面对这几个关键对象做了讲解,这里很好理解。     对象池   数值比较小的整数在程序中会频繁使用,为解决频繁内存申请和释放,使用对象池。对象池里的每一个PyInetObject对象都能够被任意的共享。大整数和小整数的分界点默认设定为[-5,257),修改方式,修改源码重新编译python。 对于大整数对象,python提供一块内存空间,由大整数轮流使用。数量为82个,也可以通过修改源码改变。 PyIntObject创建的过程,如果是小整数对象,则返回在小整数对象池中的对应的对象。如果不是,使用通用整数对象池     可以很容易的理解一些问题: >>> a1=[1,2,3] >>> b1=a1 >>> b1 == a1 True >>> b1 is a1 True >>> b2 = [1,2,3] >>> a1 == b2 True >>> a1 is b2 False >>> c1=1 >>> c2 = c1 >>> c1 == c2 True >>> c1 is c2 True >>> c3 =1 >>> c3 == c1 True >>> c3 is c1 True   ==判定具有相同的值,is判定是同一个对象。A1 b1是对同一个列表的引用,is返回True,a1 b2不是,返回False。下面的c3 c1 返回True,是对同一对象的引用。  

Continue

在编写chrome扩展的时候,遇到“即将停止支持清单版本 1。请升级到版本 2。”的警告。 解决方法: 在manifest.json文件中增加:

{
  ...,
  "manifest_version": 2,
  ...
}
官方文档:http://developer.chrome.com/extensions/manifestVersion.html

Continue

几个比较常用的,翻译了一点官方文档。文档http://docs.python.org/2/library/functions.html#built-in-functions startswith,endswith str.endswith(suffix[, start[, end]]) str.startswith(prefix[, start[, end]]) >>> s="python" >>> s.startswith('py') True >>> s.startswith('th',2) True >>> s.startswith(('py','yt')) True >>> s.startswith(('py','yt'),1) True 判断字符串是否以suffix结尾,以prefix开始,是,返回true。stat,end是截取字符串。从python2.5开始,支持元祖。 lambda 匿名函数 >>> f = lambda x:x+1 >>> f(2) 3 >>> (lambda x,y:x*y)(2,3) 6 内建函数开始: zip([iterable, ...]) 返回一个元组列表,由每个参数队列的第i个元素组成元祖。列表的长度是参数队列里面最短的一个的长度。一个参数返回一个一元元组??的列表,无参数返回空列表。zip(*[iter(s)]*n)是个逆操作? >>> a=[1,2,3] >>> b=[4,5,6] >>> c=[4,5,6,7,8,9] >>> zip(a,b) [(1, 4), (2, 5), (3, 6)] >>> zip(a,c) [(1, 4), (2, 5), (3, 6)] >>> zip(a) [(1,), (2,), (3,)] >>> zip() [] >>> zip(*[(1, 4), (2, 5), (3, 6)]) [(1, 2, 3), (4, 5, 6)] >>> x,y = zip(*[(1, 4), (2, 5), (3, 6)]) >>> print x,y (1, 2, 3) (4, 5, 6) filter(function, iterable) 返回一个列表,由iterable里元素能使function返回真的元素构成。当iterable是元组或者字符串时,返回类型不变,其他返回list。如果function为None,将假定一个function,iterable的元素都符合(文档咋没看懂,感觉正好相反)。 filter(function, iterable)等价[item for item in iterable if function(item)],这个肯定是列表啊,不一定等价 function为None,等价[item for item in iterable if item]。 >>> filter(lambda x:x>2,[1,2,3,4]) [3, 4] >>> filter(None,[1,2,3,4]) [1, 2, 3, 4] >>> filter(lambda x:x>'c',"abcdef") 'def'   map(function, iterable, ...) 将每一个iterable的元素带入function,组成列表返回。 >>> map(lambda x:x+2,[1,2,3,4]) [3, 4, 5, 6] reduce(function, iterable[, initializer]) 从左到右依次取iterable中的元素,带入function。initializer是初始值,function有两个参数,有初始值第一个参数为初始值,第二个从iterable中取,然后执行function,结果带入第一个参数,第二个参数取iterable下一个元素。 >>> a=[1,2,3,4] >>> reduce(lambda x,y: x+y,a) 10 >>> reduce(lambda x,y: x+y,a,10) 20

Continue

以前看过一部分了,现在拿起来重新看。不准备像作者一样一步一步的修改代码测试验证,我只是懂得机理,知道是个什么东西就行,作者叙述的内容已经经过验证不会有什么错误。代码我也是下载的python2.5版本的,对照着看看。   Python中,对象就是c中的结构体在堆上申请的一块内存,一般的,对象是不能被静态初始化的,并且也不能再栈空间上生存。唯一例外就是类型对象,内建类型对象(整数类型对象,字符串类型对象)都是静态初始化的。   PyObject  

typedef struct _object {

Py_ssize_t ob_refcnt;

struct _typeobject *ob_type

} PyObject
  Py_ssize_t 作者说当作int看,书上就写的int。整型变量ob_refcnt实现了基于引用计数的垃圾收集机制。对于对象A,有新的PyObject *引用该对象,A的引用计数增加,当删除时,减少。当A的引用计数减少到0时,A从堆上删除,释放内存。 结构体_typeobject是对应一个对象类型的类型对象,描述类型信息。   PyIntObject
typedef struct {

PyObject_HEAD

long ob_ival;

} PyIntObject
  PyObject_HEAD就是_object中的成员,在整型对象中,long型变量ob_ival就是存储的整数的值。作者用这个例子说明,python的对象都是基于PyObject的,并且还有属于自己的对象信息。   PyVarObject
#define PyObject_VAR_HEAD             \

PyObject_HEAD                  \

Py_ssize_t ob_size; /* Number of items in variable part */

typedef struct {

PyObject_VAR_HEAD

} PyVarObject
专为变长对象准备,整型的ob_size指明变长对象中容纳元素的个数,而不是字节数量。   PyTypeObject  
typedef struct _typeobject {

PyObject_VAR_HEAD

const char *tp_name; /* For printing, in format "<module>.<name>" */

Py_ssize_t tp_basicsize, tp_itemsize; /* For allocation */

struct _typeobject *tp_base;

…

} PyTypeObject
类型对象,结构体好长,也看不懂,复制作者有介绍的几个。 tp_name 类型名。tp_basicsize创建该类型对象分配的内存空间大小信息, tp_itemsize一个元素在内存中的长度,对不定长度的对象使用。 结构体中另外两部分:与类型对象相关联的操作信息,和类型信息。 tp_base 指定基类,tp_new创建对象,tp_init 初始化对象。tp_hash生产hash值   类型对象的类型, 每一个对象都有一个类型,比如:a=10, type(a),返回<type 'int'>,说明对象a的类型为int。但是int为类型,也是一个PyTypeObject对象,他的类型是啥呢。type(int)测试,返回<type 'type'>。type(type),<type 'type'>

Continue

总结的很好,《golang web 编程》作者维护的golang博客:http://beego.me/ 。。。。。。。。。。。。。。。。 我们在写Go代码的时候经常用到import这个命令用来导入包文件,而我们经常看到的方式参考如下:

import(
    "fmt"
)
然后我们代码里面可以通过如下的方式调用
fmt.Println("hello world")
上面这个fmt是Go语言的标准库,他其实是去goroot下去加载该模块,当然Go的import还支持如下两种方式来加载自己写的模块: 1.相对路径 import “./model” //当前文件同一目录的model目录,但是不建议这种方式来import 2.绝对路径 import “shorturl/model” //加载gopath/src/shorturl/model模块 上面展示了一些import常用的几种方式,但是还有一些特殊的import,让很多新手很费解,下面我们来一一讲解一下到底是怎么一回事 1.点操作 我们有时候会看到如下的方式导入包
import(
    . "fmt"
)
这个点操作的含义就是这个包导入之后在你调用这个包的函数时,你可以省略前缀的包名,也就是前面你调用的fmt.Println("hello world")可以省略的写成Println("hello world") 2.别名操作 别名操作顾名思义我们可以把包命名成另一个我们用起来容易记忆的名字
import(
    f "fmt"
)
别名操作的话调用包函数时前缀变成了我们的前缀,即f.Println("hello world") 3._操作 这个操作经常是让很多人费解的一个操作符,请看下面这个import
import (
    "database/sql"
    _ "github.com/ziutek/mymysql/godrv"
)
_操作其实是引入该包,而不直接使用包里面的函数,而是调用了该包里面的init函数,要理解这个问题,需要看下面这个图,理解包是怎么按照顺序加载的: 程序的初始化和执行都起始于main包。如果main包还导入了其它的包,那么就会在编译时将它们依次导入。有时一个包会被多个包同时导入,那么它 只会被导入一次(例如很多包可能都会用到fmt包,但它只会被导入一次,因为没有必要导入多次)。当一个包被导入时,如果该包还导入了其它的包,那么会先 将其它包导入进来,然后再对这些包中的包级常量和变量进行初始化,接着执行init函数(如果有的话),依次类推。等所有被导入的包都加载完毕了,就会开 始对main包中的包级常量和变量进行初始化,然后执行main包中的init函数(如果存在的话),最后执行main函数。下图详细地解释了整个执行过 程: [caption id="" align="alignnone" width="569" caption="golang import"]golang import[/caption]   通过上面的介绍我们了解了import的时候其实是执行了该包里面的init函数,初始化了里面的变量,_操作只是说该包引入了,我只初始化里面的 init函数和一些变量,但是往往这些init函数里面是注册自己包里面的引擎,让外部可以方便的使用,就很多实现database/sql的引起,在 init函数里面都是调用了sql.Register(name string, driver driver.Driver)注册自己,然后外部就可以使用了。 这样我们就介绍完了全部import的情况,希望对你理解Go的import有一定的帮助。

Continue

1.数组,Array make-array 构造一个数组。 [9]> (make-array '(2 3)) #2A((NIL NIL NIL) (NIL NIL NIL)) [10]> (make-array '(3 3)) #2A((NIL NIL NIL) (NIL NIL NIL) (NIL NIL NIL)) 其中 n 是数组的维度。 [11]> #2a((1 2 3) (4 4 4)) #2A((1 2 3) (4 4 4)) 可以使用:initial-element 参数初始化数组元素的值。 [12]> (make-array '(2 3) :initial-element 2) #2A((2 2 2) (2 2 2)) 取出数组内的元素我们调用 aref,要替换数组的某个元素,我们使用 setfaref。 > (setf arr (make-array '(2 3))) #2A((NIL NIL NIL) (NIL NIL NIL)) > (aref arr 0 1) NIL > (setf (aref arr 0 1) 'b) B > (aref arr 0 1) B > arr #2A((NIL B NIL) (NIL NIL NIL)) 2.字符串 一个字符 c#\c 表示 字符比较函数 char< (小于), char<= (小于等于), char= (等于), char>= (大于等于) , char> (大于),以及 char/= (不同) aref 来取出元素,但对一个字串,你可以使用更快的 char 函数。 [30]> (aref "abc" 1) #\b [31]> (char "abc" 1) #\b 比较两个字串,你可以使用通用的 equal 函数,但还有一个忽略大小写的比较函数 string-equal。 连接字符串 [7]> (concatenate 'string "not " "to worry") "not to worry" 3.结构 定义结构使用 defstruct, [8]> (defstruct point x y) POINT 定义了一个 point 具有两个字段 xy,操作方法: [9]> (setf p (make-point :x 0 :y 0)) #S(POINT :X 0 :Y 0) [10]> (point-x p) 0 [11]> (point-y p) 0 [12]> (setf (point-y p) 2) 2 [13]> p #S(POINT :X 0 :Y 2) 测试是否是一个point: [14]> (point-p p) T make-point , point-p , copy-point , point-xpoint-y 函数都是在定义结构时隐式定义了。 4.哈希表 (Hash Table) 当列表的长度大幅上升时(或是 10 个元素),使用哈希表会来得比较快。 [1]> (setf ht (make-hash-table)) #S(HASH-TABLE :TEST FASTHASH-EQL) [2]> (gethash 'color ht) NIL ; NIL [3]> (setf (gethash 'color ht) 'red) RED [4]> (gethash 'color ht) RED ; T [5]> ht #S(HASH-TABLE :TEST FASTHASH-EQL (COLOR . RED)) [6]> (setf (gethash 'size ht) '10) 10 [7]> ht #S(HASH-TABLE :TEST FASTHASH-EQL (SIZE . 10) (COLOR . RED)) [12]> (remhash 'size ht) NIL [13]> ht #S(HASH-TABLE :TEST FASTHASH-EQL (COLOR . RED)) make-hash-table构造一个哈希表,gethash第一个参数是键值,第二个是哈希表。返回的第一个参数是键值对应的值,不存在返回nil。第二个参数表示是否存在对应的值,不存在为nil,应该主要为了区别方便判断,比如nil可能为值。remhash是删除一个记录。 [14]> (setf ht2 (make-hash-table :size 5)) #S(HASH-TABLE :TEST FASTHASH-EQL) [15]> (setf ht3 (make-hash-table :test #'equal)) #S(HASH-TABLE :TEST FASTHASH-EQUAL) 参数:size指定哈希表的大小,:test指定查询时候比较时用的函数,从构造完返回的值有显示:test的不同。 common lisp函数还真不是一般的多,从第一次看就感觉有很多函数没必要有,现在的感觉是无论用其他的能不能实现,只要你想到的就必须用一个函数可以直接实现。感觉好怪

Continue

python中的and-or可以用来当作c用的?:用法。比如 1 and a or b,但是需要确保a为True,否则a为False,还要继续判断b的值,最后打印b的值。 今天看到一个好方法避免这种情况,记录一下: (1 and [a] or [b])[0] 可以保证[a]为True。

Continue

1.映射函数 [1]> (setf l '(1 2 3)) (1 2 3) [8]> (mapcar #'(lambda (x) (+ x 10)) l) (11 12 13) maplist 接受同样的参数,将列表的渐进的下一个 cdr 传入函数 [9]> (maplist #'(lambda (x) x) l) ((1 2 3) (2 3) (3)) 2.树 看完这一节,才对lisp的其中一个优点有所理解。就像lisp的名字“Lisp” 起初是 “LISt Processor” 的缩写。都是列表啊。 Cons 对象可以想成是二元树, car 代表右子树,而 cdr 代表左子树。图就不传了,原图有点错误,这个比较好理解。 我们有下面的列表。 [13]> (setf x 1) 1 [15]> (and (integerp x) (zerop (mod x 2))) NIL [16]> (setf x 2) 2 [17]> (and (integerp x) (zerop (mod x 2))) T [18]> (setf x 2.0) 2.0 [19]> (and (integerp x) (zerop (mod x 2))) NIL 用来判断x是整数,并且被2 整除,这不是函数形式,想把其中的x改成y的时候。我们将他看成整个列表进行操作。看到这里我才明白,汗。 [20]> (subst 'y 'x '(and (integerp x) (zerop (mod x 2)))) (AND (INTEGERP Y) (ZEROP (MOD Y 2))) 单引号的功能前边有介绍,但是没这样的例子,当时还是仅仅的理解为'(a b c)。 [24]> (cons 'a 'b) (A . B) 这是一个非正规列表,称之为 [caption id="attachment_808" align="alignnone" width="96" caption="点状列表"]点状列表[/caption] 。 common lisp列表操作的函数好多,大概试了,就不记录了,等以后查看文档。

Continue

1.列表(Lists) cons把两个对象结合成一个有两部分的对象,称之为 Cons 对象。概念上来说,一个 Cons 是一对指针; 第一个是 car ,第二个是 cdr 。 任何非空的列表,都可以被视为一对由列表第一个元素及列表其余元素所组成的列表。 [1]> (setf x (list 'a 'b 'c)) (A B C) [2]> (car x) A [3]> (cdr x) (B C) 看图理解cons。 [caption id="attachment_801" align="alignnone" width="298" caption="lisp list"]lisp list[/caption] 可以这么些: [8]> (setf y (cons 'a (cons 'b (cons 'c nil)))) (A B C) 与图中所画内容相对应了 嵌套列表 [9]> (setf z (list 'a (list 'b 'c) 'd)) (A (B C) D) [10]> (car (cdr z)) (B C) [caption id="attachment_802" align="alignnone" width="300" caption="lisp嵌套列表"]lisp嵌套列表[/caption] 如果参数是一个 Cons 对象,函数 consp 返回真。

(defun our-listp (x) (or (null x) (consp x)))  因为所有不是 Cons 对象的东西就是一个原子 (atom),判断式 atom 可以这样定义:
(defun our-atom (x) (not (consp x)))
NIL 是一个原子,同时也是一个列表。 (null x)就是判断x为nil时,返回t。当然空列表也是nil。 2.等式 (Equality) 每一次你调用 cons 时, Lisp 会配置一块新的内存给两个指针。所以如果我们用同样的参数调用 cons 两次,我们得到两个数值看起来一样,但实际上是两个不同的对象: [14]> (eql (cons 'a nil) (cons 'a nil)) NIL 本质上 equal 若它的参数打印出的值相同时,返回真: [15]> (equal (cons 'a nil) (cons 'a nil)) T 3.lisp的指针 书上给了一个例子: [22]> (setf x '(a b c)) (A B C) [23]> x (A B C) [24]> (setf y x) (A B C) [25]> y (A B C) [26]> (eql x y) T 当我们给 y 赋一个相同的值时, Lisp 复制的是指针,而不是列表。当你赋一个值给变量或将这个值存在数据结构中,其实被储存的是指向这个值的指针。当你要取得变量的值,或是存在数据结构中的内容时, Lisp 返回指向这个值的指针。 函数 copy-list 接受一个列表,然后返回此列表的复本。 [27]> (setf y (copy-list x)) (A B C) [28]> (eql x y) NIL 4.列表的存取 [29]> (nth 0 '(a b c )) A [30]> (nth 1 '(a b c )) B [35]> (nthcdr 0 '(a b c d)) (A B C D) [36]> (nthcdr 1 '(a b c d)) (B C D) [37]> (nthcdr 2 '(a b c d)) (C D) 取第几个元素用nth,nthcdr是取第n个cdr,nth 等同于取 nthcdrcar。并且都是零索引。 Common Lisp 定义了函数 first 直到 tenth 可以取得列表对应的元素,但不是 零索引。 函数 last 返回列表的最后一个 Cons 对象。此外, Common Lisp 定义了像是 caddr 这样的函数,它是 cdrcdrcar 的缩写 (car of cdr of cdr)。所有这样形式的函数 cxr ,其中 x 是一个字串,最多四个 ad ,在 Common Lisp 里都被定义好了。

Continue

1.变量 let引入新的局部变量。 [33]> (let ((x 1) (y 2)) (+ x y)) 3 defparameter创造一个全域变量。 [37]> (defparameter *ga* 123) *GA* [38]> *ga* 123 用 defconstant 来定义一个全域的常量 [39]> (defconstant limit 8 ) LIMIT [40]> limit 8 检查某些符号,是否是一个全域变量或常数,用 boundp [41]> (boundp 'limit) T [42]> (boundp '*ga*) T 2.赋值 setf给全域或局域变量做赋值,如果 setf 的第一个参数是一个符号(symbol),且这个符号不是某个局部变量的名字,那么 setf 将设置这个符号为全局变量。还是使用 defparameter 显式地创建全局变量比较好。 [44]> *ga* 1 [45]> (let ((n 10)) (setf n 2) n) 2 [46]> (setf x (list 'a 'b 'c)) (A B C) 传入 setf 的第一个参数,还可以是一个表达式或一个变量名。在这种情况下,第二个参数的值被插入至第一个参数所引用 (refer)的地方。 [47]> (setf (car x) 'n) N [48]> x (N B C) [53]> (setf a 1 b 2 c 3) 3 [54]> a 1 [55]> b 2 [56]> c 3 相当于

(setf a b)
(setf c d)
(setf e f)

3. 类型
在 Common Lisp 里,数值才有类型,而不是变量。typep判断类型。
[57]> (typep 25 'integer)
T

类型 (Types)

Continue