2010年5月22日星期六

go language

差不多一个月前我仔细看了 Tim C, Erlang, Java and Go Web Server performance test, 并在我自己的笔记本上跟着使用 ab 做了一些测试, 其中还测试了两个 Python 的 web 框架, web.py Tornado , web.py 弱得简直不堪使用了, 而在Asynchronous Servers in Python 测试中性能强悍的 Tornado 应该算是我所知道的 Python web 框架中较好的一个了, 不过也不是很好,对比其他非 Python 的 web server ,哈哈。 go 的并发性能还是不错的,这让我很想学习各种 go 的应用。 于是我下载了几个跟 go 相关项目的源代码, 包括 web.go Go-Redisgomemcached gosqlite3。 无一例外的,都不能编译成功使用。

其中最常见的一个问题是,我的 go 环境对“;”的严格要求, 而这些新的项目是在比较新的 go 环境中开发的,很多地方已不需要添加“;”。 话说我的 go 版本比较低,是去年年底 2009,12,11 的源码编译的。 于是我开始一个个地给那些我的 go 环境需要“;”的地方添加“;”, 然而这是一件浩大的工程。。。遂放弃了。。。

心想,go 语言也真是的,这么普通的规则也更改了, 哪天真的用其做了一些东西出来,升级岂不是要整死人了?

不过真的很看好 go 语言,等我有了比较好的网络环境了再更新 go 的源代码, 领略一下这些构建在优秀的 go 语言上的新项目的魅力吧!

附:

一个简单的 Hello world 的 go server :

package main

import (
"http";
"io";
"runtime";
)

func HelloServer(c *http.Conn, req *http.Request) {
io.WriteString(c, "hello, world!\n");
}

func main() {
runtime.GOMAXPROCS(2); // 2 cores
http.Handle("/", http.HandlerFunc(HelloServer));
err := http.ListenAndServe(":8080", nil);
if err != nil {
panic("ListenAndServe: ", err.String())
}
}

一个粗糙的 fibonacci :

package main

import "fmt"

func main() {
var a uint8 = 0;
var b uint8 = 1;

for i :=0; i<10; i++ {
a, b = b, a + b;
fmt.Printf("%d\n", a);
}
}

一个简单的 channel 例子 (摘自 infoq-cn):

package main

import "fmt"

func main() {
ch := make(chan int);

go func() {
result := 0;
for i:=0; i<100000000; i++ {
result = result + i
}
ch <- result;
}();

/* Do something for a while */
fmt.Println("Have a rest!");
fmt.Println("Have a rest, too!");

sum := <- ch; // This will block if the calculation is not done yet.
fmt.Println("The sum is:", sum);

/* create a channel with buffer size 5 . */
ch2 := make(chan int, 5);
/* Send without blocking, ok will be true if value was buffered. */
ok := ch2 <- 42;
/* Read without blocking, ok will be true if a value was read. */
val, ok := <-ch2;
fmt.Println("ok is:", ok);
fmt.Println("val is:", val);
}

一篇比较全面介绍 Go 语言的文章: Go Lang介绍

--
http://magicoding.appspot.com/entry/1
2010,04,27

二分查找算法

JavaEye 在几天前发表了一篇关于二分查找算法的文章: 你是那10%可以实现二分查找算法的程序员吗?,讲得好像让所有的程序员都很尴尬的样子。最后文章还给出了一位 JavaScript 高手对二分查找算法的实现。但是这个算法其实也是有 bug 的。。。我们可以查看 Python 里的 bisect 模块,对于二分查找算法,分为 bisect_right 和 bisect_left 两种情况,这是由于所查找的元素在预排序算法中可能有多个存在或者元素可能会是一种复杂的数据结构,所以当然就必须考虑是查找左边的位置还是右边的位置,或者插入左边的位置还是右边的位置了。对于简单的元素不需要考虑插入左边的位置还是右边的位置,不过 Python 文档中举的例子中的元素是个复杂的数据结构,所以需要考虑这种需求。

附上那位写了《JavaScript高级程序设计》的作者使用 JavaScript 实现的代码:

//Copyright 2009 Nicholas C. Zakas. All rights reserved.
//MIT-Licensed, see source file
function binarySearch(items, value){

var startIndex = 0,
stopIndex = items.length - 1,
middle = Math.floor((stopIndex + startIndex)/2);

while(items[middle] != value && startIndex < stopIndex){

//adjust search area(调整查找范围)
if (value < items[middle]){
stopIndex = middle - 1;
} else if (value > items[middle]){
startIndex = middle + 1;
}

//recalculate middle(重新计算中项索引)
middle = Math.floor((stopIndex + startIndex)/2);
}

//make sure it's the right value(确保返回正确的值)
return (items[middle] != value) ? -1 : middle;
}

可以在 Firebug 或者其他浏览器的 JavaScript 调试器中测试这段代码, 也可以把这段代码翻译成 Python 代码,再添加一个小小的测试:

# coding=utf8
def binarySearch(items, value):

startIndex = 0
stopIndex = len(items)
middle = (stopIndex + startIndex) // 2

while items[middle] != value and startIndex < stopIndex:

#adjust search area(调整查找范围)
if value < items[middle]:
stopIndex = middle - 1
elif value > items[middle]:
startIndex = middle + 1

#recalculate middle(重新计算中项索引)
middle = (stopIndex + startIndex) // 2

#make sure it's the right value(确保返回正确的值)
return (items[middle] != value) and None or middle

if __name__ == '__main__':
items = [1, 2, 3, 4, 4, 4, 4, 4, 5, 6]
print binarySearch(items, 4)

检测运行一下,当然就发现问题了。

最后附上 Python 标准库中的实现代码:

## from file: /path/to/python-install-prefix/lib/pythonx.x/bisect.py
def bisect_right(a, x, lo=0, hi=None):
"""Return the index where to insert item x in list a, assuming a is sorted.

The return value i is such that all e in a[:i] have e <= x, and all e in
a[i:] have e > x. So if x already appears in the list, a.insert(x) will
insert just after the rightmost x already there.

Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""

if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if x < a[mid]: hi = mid
else: lo = mid+1
return lo

bisect = bisect_right # backward compatibility

def bisect_left(a, x, lo=0, hi=None):
"""Return the index where to insert item x in list a, assuming a is sorted.

The return value i is such that all e in a[:i] have e < x, and all e in
a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
insert just before the leftmost x already there.

Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""

if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if a[mid] < x: lo = mid+1
else: hi = mid
return lo

嗯,学习算法知识的话,到 Python 的标准库中查看源代码也是一种非常好的学习方式啊!

--
http://magicoding.appspot.com/entry/0
2010,04,26

2010年5月6日星期四

谢谢大家的关注

谢谢大家关注我的博客。
由于去年离职之后到现在一直没有工作,所以未能翻墙来更新维护这个博客,今天使用一款叫做 Mr.zhang 的工具翻墙发了这些文字。
目前用 Tornado 写了个 blog 放在 Google AppEngine 上,不需翻墙访问。
http://magicoding.appspot.com
等我有了工作了再维护这个博客了。
Fedora 13 好像也快出来了,好期待啊!