Archive for 算法-编程

common lisp的列表(Lists)，等式 (Equality)

lisp | 2012-10-24 20:39:36 | 0 COMMENT

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"]

[/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嵌套列表"]

[/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 等同于取 nthcdr 的 car。并且都是零索引。 Common Lisp 定义了函数 first 直到 tenth 可以取得列表对应的元素，但不是 零索引。 函数 last 返回列表的最后一个 Cons 对象。此外， Common Lisp 定义了像是 caddr 这样的函数，它是 cdr 的 cdr 的 car 的缩写 (car of cdr of cdr)。所有这样形式的函数 cxr ，其中 x 是一个字串，最多四个 a 或 d ，在 Common Lisp 里都被定义好了。

common lisp变量和赋值，类型判断

lisp | 2012-10-23 13:26:22 | 0 COMMENT

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)

common lisp学习笔记二，quote，if，and和or

lisp | 2012-10-22 11:08:09 | 0 COMMENT

1.quote Lisp 提供 quote 作为一种保护表达式被求值的方式。Common Lisp 定义 ' 作为 quote 的缩写。 [62]> (quote (+ 3 5)) (+ 3 5) [64]> '(+ 3 5) (+ 3 5) 这意味着 Lisp 程序可以写出 Lisp 代码。 Lisp 程序员能（并且经常）写出能为自己写程序的程序。 2. if [20]> (if t 'a 'b) A [21]> (if nil 'b 'a) A 第一个参数是判断，第二个是为true时求值，第三个是false求值。 3. and和or 逻辑操作符 and 和 or 与条件式 (conditionals) 类似。两者都接受任意数目的参数，但只对能够决定返回值的那几个参数来作求值。如果所有的参数都为 真 （即不为 nil )，那么 and 会返回最后一个参数的值，如果其中一个参数为 假 ，那么之后的所有参数都不会被求值。 or 也是如此，只要碰到一个是 真 的参数，就停止对之后的所有的参数求值。 [23]> (and t t (+ 1 3) t) T [24]> (and t t (+ 1 3) nil) NIL [25]> (and t t (+ 1 3) nil t) NIL [26]> (or nil nil (+ 4 5)) 9 [28]> (or nil nil (+ 4 5) nil) 9 [29]> (or nil nil (+ 4 5) (- 8 7) nil) 9 其实也可以这么理解，对每一个参数求值，当and遇到nil，或者or遇到非nil，终止求值，返回nil或者非nil。没遇到就返回最后一个参数的值。

common lisp的符号、数字、列表和字符串

lisp | 2012-10-19 20:41:34 | 0 COMMENT

符号，字母开头，包括字母数字和连接符。 5 17 -34 +6 2/4 1/3 3.1415 1.722e-15 #c(1.722e-15 0.75) 有趣撒~ lisp支持分数形式，下面几个测试： [1]> (+ 3 2/3) 11/3 [2]> (+ 3.0 2/3) 3.6666667 [3]> (* 2.0 1/3) 0.6666667 [4]> (* 3.0 1/3) 1.0 [5]> (* 3.00 1/3) 1.0 [6]> (/ 3.0 1/3) 9.0 [7]> (/ 2.0 1/3) 6.0 lisp支持复数形式#c(r,i),r为实部，i为虚部。 lisp字符串包含在双引号中，#\a #\3表示字符。反斜杠为转义字符。命名约定：在全局变量开头和结尾带有“*”，常量都已“+”开头结尾。构造一个列表：（list 4 5 6） [4]> (cons 'a '(b c)) (A B C) 用函数 cons 来构造列表。如果传入的第二个参数是一个列表，则返回一个由第二个参数所组成的新列表，其中新列表的第一个元素是传入的第一个参数。 [6]> (cons 'a (cons 'b nil)) (A B) 来取出列表元素的基本函数是 car 和 cdr 。列表的 car 是第一个元素，而列表的 cdr 是第一个元素之后的所有元素 [13]> (setq l '(a b c)) (A B C) [14]> l (A B C) [15]> (car l) A [16]> (cdr l) (B C) 这个像erlang里列表操作，或者应该说erlang学的lisp。 nil唯一一个既是原子又是列表的对象。

common lisp入门安装

lisp | 2012-10-18 13:59:30 | 0 COMMENT

又准备开始学lisp，前些时候就想学，但是就怕贪多嚼不烂。现在又想：喜欢就学，先学习语法，不用深。说不定以后就用到。 lisp方言很多，没什么太多了解，先学一个撒~ 下载地址：www.clisp.org，一路next安装windows版完成。一个lisp的IDE：http://www.daansystems.com/lispide/ [1]> 10 10 [2]> (* 2 3) 6 感觉想极了编译原理里面学的，三元式还是啥的来。 [3]> (format t "hello world") hello world NIL t 是标准输出，NIL是对format求值的结果。列表的第一个元素是函数名。nil代表false，t代表true。写成函数形式： [4]> (defun hello-world () (format t "hello world")) HELLO-WORLD [5]> (hello-world) hello world NIL 求值后，得到一个名为HELLO-WORLD的函数，函数没有参数。

Network programming with Go

Golang | 2012-10-05 22:44:29 | 3 COMMENT

很不错的教程，讲的很详细。《Network programming with Go》http://jan.newmarch.name/golang/，照着教程写了一个小程序。

//server.go
package main

import(
    "fmt"
    "net"
    "os"
    "time"
)

func handleClient(conn *net.UDPConn){
    var buf [512]byte

    n, addr, err := conn.ReadFromUDP(buf[0:])
    if err != nil{
        return
    }
    fmt.Println(string(buf[0:]))
    daytime := time.Now().String()
    fmt.Println(n,addr)
    conn.WriteToUDP([]byte(daytime),addr)

}

func checkError(err error){
    if err != nil{
        fmt.Fprintf(os.Stderr,"Fatal error:%s",err.Error())
        os.Exit(1)
    }
}

func main(){
    service := ":1200"
    udpAddr, err := net.ResolveUDPAddr("up4",service)
    checkError(err)

    conn,err := net.ListenUDP("udp",udpAddr)
    checkError(err)

    for{
        handleClient(conn)
    }
}

//client.go
package main

import(
    "fmt"
    "net"
    "os"
)

func checkError(err error){
    if err != nil{
        fmt.Fprintf(os.Stderr,"Fatal error:%s",err.Error())
        os.Exit(1)
    }
}

func main(){
    if len(os.Args) != 2{
        fmt.Fprintf(os.Stderr, "Usage:%s host:port", os.Args[0])
        os.Exit(1)
    }
    service := os.Args[1]
    udpAddr, err := net.ResolveUDPAddr("up4",service)
    checkError(err)

    conn,err := net.DialUDP("udp",nil,udpAddr)
    checkError(err)

    _,err = conn.Write([]byte("hello"))
    checkError(err)

    var buf [512]byte
    n,err := conn.Read(buf[0:])
    checkError(err)
    fmt.Println(string(buf[0:n]))
    os.Exit(0)
}

,以后再扩展功能，先睡觉。

golang中strings包学习第二篇

Golang | 2012-09-26 10:16:58 | 0 COMMENT

func Join(a []string, sep string) string

,连接字符串，以sep作为分隔符例子：

s := []string{"foo", "bar", "baz"}
fmt.Println(strings.Join(s, ", "))

输出：

foo, bar, baz

,源代码分析 1.判断a的长度，0时，返回空字符串，长度为1时，返回a[0]. 2.否则，在变量n中保存将要生产字符串的长度。计算方法len(a)-1个sep的长度 + 数组a中字符串长度和。 3.创建一个长度为n的byte数组。将数据复制到数组中，copy()将返回复制元素的个数，用bp来记录复制的位置。最后转成string返回。

func Split(s, sep string) []string

，分割字符串，sep为空字串时，与上一篇讲到的一样，相当于每个字符之间的间隔。s中没有sep，返回值里只有一个元素s。例子：

fmt.Printf("%q\n", strings.Split("a,b,c", ","))
fmt.Printf("%q\n", strings.Split("a man a plan a canal panama", "a "))
fmt.Printf("%q\n", strings.Split(" xyz ", ""))
fmt.Printf("%q\n", strings.Split("", "Bernardo O'Higgins"))

输出：

["a" "b" "c"]
["" "man " "plan " "canal panama"]
[" " "x" "y" "z" " "]
[""]

，源代码return genSplit(s, sep, 0, -1) 看看func genSplit(s, sep string, sepSave, n int) []string。

func genSplit(s, sep string, sepSave, n int) []string

，有几个函数都用到这个函数，通用分割字符串的函数。 n 是返回分割的个数，-1时，返回所有。

sepSave是被分割的位置在sep所在位置的偏移，被用于SplitAfter和SplitAfterN这些函数，使用len(sep)作为sepsave可以返回sep最后一个字符前面的字串作为一个分割。

1.n为0时，返回nil。 2.sep为空字串，return explode(s, n), 3.当n<0时，应该返回所有，n为Count(s, sep) + 1，表示长度。 4.定义几个变量，c是用于比较是否和sep相等，都是先比较第一个字符。相等再看字符串长度为一，则找到；不为一，比较整个sep。a是被返回的数组，na是在数组中存储的位置。东西零碎 utf8包的内容，写下来的目的是使自己是真正的明白，而不是一看知道是这么回事，但是不想为什么要这样写。现在感觉自己用来学习的时间很少，珍惜一下。

golang中strings包学习

Golang | 2012-09-22 22:50:00 | 0 COMMENT

打算把golang的常用包都看一遍，分析一下包的代码，觉得从中会学到golang的编程方法^_^。

func Index(s, sep string) int

返回s中第一次出现sep的位置，如果没有返回-1. 例子：代码：

fmt.Println(strings.Index("chicken", "ken"))
fmt.Println(strings.Index("chicken", "dmr"))

输出：

4
-1

看源码中index的实现方法， 1.取得sep的长度。如果长度为零，返回0。否则取sep第一个字符。 2.如果长度为1，for循环比较s[i]和sep[0]，相等，返回i。都不相等，返回-1。 3.如果长度大于1，for循环比较（先比较s[i]和sep[0],不相等就i++，再比较s[i:i+n] == sep。）成立返回i，否则返回-1。比较的上限是i+n。相关函数：

func Contains(s, substr string) bool

如果substr在s中，返回true。代码：

fmt.Println(strings.Contains("seafood", "foo"))
fmt.Println(strings.Contains("seafood", "bar"))
fmt.Println(strings.Contains("seafood", ""))
fmt.Println(strings.Contains("", ""))

输出：

true
false
true
true

源代码中用index函数实现，return Index(s, substr) >= 0。

func LastIndex(s, sep string) int

，返回在s中最后一次出现sep的位置，不存在返回-1。例子就过了，源代码分析，与index()相似，但是判断的时候是从s的后边向前判断。

func Count(s, sep string) int

，统计sep在s中出现的次数，非重叠的，比如s=“eeee”，sep="ee",结果返回2. 例子：

fmt.Println(strings.Count("cheese", "e"))
fmt.Println(strings.Count("five", "")) // before & after each rune

结果：

3
5

，我对第二个例子不理解，在群里问了一番，开始回答的我没明白。后来第二个给我回答我才明白：这里“”字符串指的就是字符串中每个字符之间的空字符串T_T,函数返回了s中有几个这样的空字符串。后面的英文注释直接看不懂T_T,悲催。现在看应该是每个字符的前面加后面。。。源代码中“”时，返回utf8.RuneCountInString(s) + 1，这里不用len，我测试了一下对于一个中文len返回的长度是3，这里不符，所以用utf8.RuneCountInString。utf8.RuneCountInString是使用range来遍历的字符串，与len计数不同，一个中文长度为1。但是在接下来遍历s和sep都是用的len()，也就是说比如 fmt.Println(strings.Count("我的我的", "\x88"))你会得到结果2，这是因为 ”我的“会被\xe6\x88\x91\xe7\x9a\x84遍历，你将从中找到\x88。 fmt.Println(strings.Count("five", "")) 然后还是分两种情况，len(sep)=1和大于1两种情况。

golang的Panic和Recover

Golang | 2012-09-15 09:10:42 | 0 COMMENT

在看《build web application with golang》地址：https://github.com/astaxie/build-web-application-with-golang 看到Panic和Recover这一节，对Panic和Recover有了了解。 Go没有例如像Java那样的异常机制：不能抛出一个异常。作为代替，它使用了panic和recover机制。一定要记得，这应当作为最后的手段被使用，你的代码中应当没有，或者很少的令人恐慌的东西。这是个强大的工具，明智的使用它。那么，应该如何使用它。 Panic

是一个内建函数，可以中断原有的控制流程，进入一个令人恐慌的流程中。当函数F调用panic，函数F的执行被中断，但是F中的延迟函数会正常执行，然后F返回到调用它的地方。在调用的地方，F的行为就像调用了panic。这一过程继续向上，直到发生panic的goroutine中所有调用的函数返回，此时程序退出。恐慌可以直接调用panic产生。也可以由运行时错误产生，例如访问越界的数组。

Recover

是一个内建的函数，可以让进入令人恐慌的流程中的goroutine恢复过来。Recover仅在延迟函数中有效。在正常的执行过程中，调用 recover会返回nil，并且没有其他任何效果。如果当前的goroutine 陷入恐慌，调用recover可以捕获到panic的输入值，并且恢复正常的执行。

最容易理解就是给个例子，文章里有例子：

package main

import(
    "fmt"
    //"os"
)

var user = ""
func inita() {
    defer func(){
        fmt.Print("defer##\n")
    }()
    if user == "" {
        fmt.Print("@@@before panic\n")
        panic("no value for user\n")
        fmt.Print("!!after panic\n")
    }
}

func throwsPanic (f func()) (b bool){
    defer func(){
        if x:= recover(); x != nil{
            fmt.Print(x)
            b = true
        }
    }()
    f()
    fmt.Print("after the func run")
    return
}

func main(){
    throwsPanic(inita)
}

执行结果： D:\go>go run b.go @@@before panic defer## no value for user 如上面所说的： panic在user=""时，打断了函数的执行，fmt.Print("!!after panic\n")没有执行。但函数中的延迟函数会正常执行，打印了 ”defer##“。然后返回到调用该函数的地方，继续上面的过程。直到执行完所有函数的defer，退出程序。 Recover可以捕获到panic的值，上面的打印“no value for user”。并且恢复正常的执行。

pdb调试python程序

Python | 2012-09-06 18:02:51 | 2 COMMENT

以前在windows下一直用的idel带的功能调试python程序，在linux下没调试过。（很多时候只是print）就从网上查找一下~ 方法：python -m pdb a.py a.py是python文件。 (Pdb)模式下的常用命令: q 退出debug h 即help，打印所有可以命令 h w 打印命令 w 的含意 n 执行当前行直到到达下一行或直到它返回 s 执行当前行，一有可能就停止（比如当前行有一个函数调用）。它和n(next)的区别是当前行中有函数调用时s(step)会停止当前行的执行而去调用那个函数，而n不会停止，直到计算完成这一行（到达下一行）。 b(reak) [[filename:]lineno | function[, condition]] 设置断点，可以是行号或函数。如 b 10, b foo, b foo,n == 5，最后在函数foo()入口处设置一个断点，但仅当n的值是5时才有效。当b命令无参数时，打印所有断点。 tb(reak) [[filename:]lineno | function[, condition]] 临时断点，只hit一次。 disable [bpnumber [bpnumber ...]] 使指点行的断点（们）失效 enable [bpnumber [bpnumber ...]] 使指定行上的断点（们）有效 c 继续执行程序，直到遇到下一个断点 w 即where，打印当前执行点的位置 l [first, [,last]] 输出当前行附近的源码 p expression 执行一个表达式当打印其值。 a(rgs) 打印当前函数的参数及其值 <直接回车> 重复执行上次的命令并遇到pdb不认识的命令时，会将它当成python表达式执行。如果你想执行的表达时，最前面加上 ! 字符，比如 !n == 5 多个debug命令可以写在一行上，中间用两个分号分隔，如 s;;s。