X server、Xorg、X window

X window、Xorg、X server这几个名字,听着都很熟悉,只知道这些东西是与linux上面的gui有关的,却对其内部的结构一无所知。今天花了点时间研究下,算是了解了个大概。

X window system是一个总称,它不仅包括了一些程序,还包括一些网络协议。X系统最初是由MIT于1984年开发,当时的X是用在Unix System V上面。在X的设计之初,设计者们希望能通过网络来使用图形界面,因此设计了很多的网络协议。随着不断的开发,在1987年X进化到11这个版本,这个版本的X进步明显,因此后来的X系统基本上都是在这一版的基础上进行改进的。在1994年发布了X11R6,后来的架构都是沿用这一版本。后来因为授权的问题,X系统由Xorg基金会接手进行维护。这就是为什么在Arch里面安装X的时候需要安装xorg-server xorg-xinit xorg-utils xorg-server-utils等等。

X使用了client-server模式,一个X server与多个X client进行通信。X server接受进行图形输出的请求,并且向X client返回用户的输入(鼠标、键盘等)。X系统的client-server模式,与我们平常所见到的刚好是相反的。比如有多个用户机要连接到一台服务器上面,那么用户机上需要安装的是X server,而服务器上安装的则是X client。这点可能开始很难理解,但是理解X server和X client分别是起什么作用之后,就会明白这是非常自然的设计。

X server的主要功能就是管理主机上的硬件,包括键盘、鼠标、显示器、显卡。因为用户机不可能与服务器的硬件配置相同,所以要将X server安装在用户机上面。服务器上的X client向用户机上面的X server发出绘制窗口的请求,然后由X server来完成请求。此外,X server还要将用户的输入通知给X client。

X client的主要功能就是接受由X server发来的用户输入行为,然后进行处理,再将绘图请求返回给X server。

浅拷贝与深拷贝

对象赋值实际上是只是对象的引用,如果想要复制某个对象,需要通过完全切片或者工厂函数以及使用copy模块的方法来完成。但是这三种方法都是所谓的“浅拷贝”。首先明确,“浅拷贝”和“深拷贝”的概念仅仅是针对容器类型的对象,因为非容器类型没有拷贝这一说法。他们的区别在于:

  • 浅拷贝将创建一个新的容器对象,然后把对原容器中元素的引用插入到新容器中。
  • 深拷贝将创建一个新的容器对象,然后递归地把原容器中元素的“拷贝”插入到新容器中。

继续阅读浅拷贝与深拷贝

Tips on Python collections

原文链接
Alex Marandon介绍了几个python的技巧,感觉很实用。如下:

检查列表是否为空

判断某个列表是否为空,大多数人都会这样做:
[cc lang=”python”]
if len(mylist):
# Do something with my list
else:
# The list is empty
[/cc]
其实不需要用len函数,因为空列表的值本身就是False。所以可以这样做:
[cc lang=”python”]
if mylist:
# Do something with my list
else:
# The list is empty
[/cc]
继续阅读Tips on Python collections

强大的itertools

最近几天一直在做python challenge,收获很多。比如这个经典的题目:
a = [1, 11, 21, 1211, 111221, …],问a[30]由多少位数字组成?

序列本身让人感觉无从下手,绞尽脑汁也想不出这个数列有什么规律。只好去看论坛里面的提示。提示说到,用搜索引擎搜索”morris 1, 11, 21, 1211″,看看会有什么结果。照着做了,发现原来这个数列是这样生成的:
1就是1个1 ==> 11
11是2个1 ==> 21
21是1个2和1个1 ==> 1211
1211是1个1、1个2和2个1 ==> 111221
……

接下来实现这个算法,得到a[30]的长度为5808。虽然实现起来不难,但是也有一点麻烦。随后又去看了答案,才发现原来可以这么写:
继续阅读强大的itertools

一个简单的python程序

闲来无事,为了“get hands dirty”,写了一个获取用户微博的python程序。首先调用了twitter的api,取得xml格式的数据,然后用minidom解析xml。最后将数据写成html文件保存起来。生成html用的是PyH这个库。
[cc lang=’python’]
#!/usr/bin/env python2

from pyh import *
import urllib
from xml.dom import minidom

def get_tweets(screen_name):
textList = []
timeList = []
url = ‘http://api.twitter.com/1/statuses/user_timeline.xml?screen_name=%s’ % screen_name
f = urllib.urlopen(url)
xmldoc = minidom.parse(f)
statusList = xmldoc.getElementsByTagName(‘status’)
for item in statusList:
textList.append(item.getElementsByTagName(‘text’)[0].firstChild.data)
timeList.append(item.getElementsByTagName(‘created_at’)[0].firstChild.data)
return (textList, timeList)

if __name__ == ‘__main__’:
(textList, timeList) = get_tweets(‘amazingjxq’)
page = PyH(‘Tweets’)
page<‘ + textList[i].encode(‘utf-8’))
page<

django两则

1. request.method

曾经弱智的用了两个view来完成一件事情。同一个view函数,其实是可以根据当前http请求的方法区别状态的。例如,在某个登录的url所对应的view中,如果收到的http请求是get方法,说明用户只是要打开登录页面,这时只要展现相关的页面就可以了。而如果是post方法,则说明用户在表单中填入了用户名和密码,提交到了服务器。这时需要完成用户验证的相关操作,并跳转到指定页面。
[cc lang=”python”]
def login_view(request):
if request.method == ‘POST’:
pass
else:
form = ContactForm()
return render_to_response(‘core/login.html’, {‘form’:form})
[/cc]

2. 使用django中的form

可以用django.forms定义自己的form类,而不需要在模板中自己写html的form。所有的form都是django.forms.Form的子类。ContactForm的定义:
[cc lang=”python”]
from django import forms

class ContactForm(forms.Form):
subject = forms.CharField(max_length=100)
message = forms.CharField()
sender = forms.EmailField()
cc_myself = forms.BooleanField(required=False)
[/cc]
django中定义了多种field类型,由于验证用户提交数据的有效性。

在模板中显示form:
[cc lang=”html”]

{{ form.as_p }}

[/cc]

Tail Recursion(尾递归)

最早接触递归,是碰到“汉诺塔”的时候。感叹还有如此巧妙的解法。之后又被警告,“递归虽好,但也不能随便用”。记得当时试验过,汉诺塔的递归解法到10几层的情况,速度已经不能让人接受了。效率低下是递归给我留下的最深的印象。

那递归能不能优化呢?

求某个数的阶乘,我们可以用以下的递归实现:

因为需要用n乘以factorial(n-1),所以每递归一次都要占用一个栈空间。factorial(5)的运行过程如下:
[cc]
5 * factorial(4)
4 * factorial(3)
3 * factorial(2)
2 * factorial(1)
1 * 1
[/cc]
如果参数增大,栈空间的占用可想而知。

不过我们完全可以换一种方式:
[cc lang=”c” tab_size=”2″ lines=”40″]
int factorial2(int n, int acc)
{
if(n==0) return acc;
return factorial2(n-1, acc * n);
}
[/cc]
这样递归跟前面的有什么不同?把每一步的中间结果作为函数的一个参数。这样一来,完全可以用一个栈空间来完成整个运算。只需要把当前函数的栈空间替换为factorial2(n-1, acc * n)就可以了。
[cc]
factorial2(5,1)
<= fatorial2(4,5) <= factorial2(3,20) <= factorial2(2,60) <= factorial2(1,120) <= 120 [/cc] 整个过程中只使用一个栈空间,每一步只是把当前的空间替换掉。这样便提高了递归的效率。 像上面这样,如果某个函数在返回是除了返回它的返回值之外不做其他额外的操作,那这个函数就尾递归的。尾递归的函数,其实是可以转换成while循环的。 函数式编程语言中都进行了尾递归优化,使得递归的效率更高。

About Haskell 1:Functional Programming

Haskell到底是一门什么样的语言?为什么听起来这么非主流?下面是出自Haskell Wiki的介绍:

Haskell is a computer programming language. In particular, it is a polymorphically statically typed, lazy, purely functional language, quite different from most other programming languages.

Functional(函数式) vs Imperative(命令式)

其实严格来说,并不应该把这两个摆在对立的位置上。函数式与命令式并非是完全相反的。有很多的命令式语言也包含一点函数式语言的特性。但是在两种编程范式下的思考方式却有着巨大的差别。

目前我们所接触过的大部分语言,都是属于命令式编程的范围,包括c/c++、java、perl、python等等。就应用的范围来讲,命令式语言比函数式语言应用的更为广泛。关于两者之间的区别,有这样一个形象的比喻:

Functional programming is like describing your problem to a mathematician. Imperative programming is like giving instructions to an idiot.
— arcus, #scheme on Freenode

在解决问题的过程中,函数式编程着重于描述“What is it?”,命令式的则着重于“How to get it”。举个例子,假如需要确定若干个单词中,是否每个单词都是由奇数个字母所组成的。那么命令式语言的解决方法如下:
[cc lang=”c++”]bool allOdd(vector words)
{
bool result = true;
for (int i = 1; i < words.size(); ++i) { int len = words[i].length(); if (!odd(len)) { result = false; break; } } return result; }[/cc] 而函数式的却是这样: [cc lang="haskell"] allOdd words1 = and (map odd (map length words1)) [/cc] map是函数式编程中的一个基本的函数。它的两个参数分别是一个函数f(即length函数)和一个list(也可以认为是数组,即words1)。map的功能就是将函数f应用到list中的每一个元素上,得到一个由f(x)所组成的新的列表。map length words1的结果就是words1中所包含的各个单词的长度。odd根据参数奇偶性返回True或者False。不难理解,map odd (map length words1)就是一个表示这组单词的长度是否为奇数的序列。最后and函数将这个序列中的所有Bool值and起来,自然得到结果。

函数式编程强调的是函数的应用,而命令式更关注变量和程序状态的变化。“函数”在这两种范式中也有区别。函数式编程中的函数被调用时,只要参数相同,产生的结果必定相同。命令式却无法保证。比如c/c++中的函数,就有可能会受到全局变量的影响。

我个人的感觉,函数式与命令式编程的最大区别就是函数式编程中没有循环,全部用递归来实现迭代。另外一个特点,就是非常短。最著名的就是用Haskell实现quicksort。仅仅需要两行代码。
[cc lang=”haskell”]
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
–quick sort in haskell
[/cc]

目前函数式编程在商业软件中比不上命令式语言应用的广泛,大部分都是用在研究领域。但函数式编程有着很多的优点是命令式所无法比拟的。更短的代码往往意味着更少的bug,出错的几率也就更小。因为求解问题的方式是“What is it?”,代码维护起来也就更加方便。

Flattr:独特的“微支付”

提出Social Micropayment概念的是Flattr。social不social暂且不管,这样新鲜的服务的确让人眼前一亮。什么是Flattr呢?如果抛开了“钱”,那么Flattr就是与Reddit、Digg类似的服务。与Reddit和Digg不同的是,如果用户觉得某文章很有价值,选择了“Flattr it”,那么就要支付一部分钱给文章的作者。一篇文章被Flattr的次数越多,越容易广泛的流传,吸引更多的读者。

Flattr支付的方法也很有创意。首先由用户自己设定每个月所花费的金额(最少€2)。用户给出Flattr的次数增多,并不会使得用户花费更多的钱,而是将每个月的总金额平均分配到每一次Flattr里面。

与广告相比,这明显是一种更好的方式。读者不会在页面上看到令人心烦的广告,作者也可以得到应有的回报。我们每天都在从许多的博客上索取资源,却从未给出过回报。哪怕是一毛两毛。并不是我们都不想给,也不是缺乏支付的途径,国内有支付宝和网银,国外有Paypal。而是因为支付的流程太过复杂,太浪费时间。每次块儿八毛的都用支付宝或者网银,也有点说不过去。

Flattr的服务可以说是一举两得。既可以让有价值的文章快速传播,又可以让作者有实实在在的“回报”。看好来自瑞典的Flattr。

PS:Flattr的创造者之一是曾经创办海盗湾的Peter Sunde Kolmisoppi。