Liuw’s Thinkpad

可以大言不慚地吼著說：“我寫的！”

複用不好，很多冗餘代碼。設計不好，接口不明。寫法丑，不夠Pythonic。

唯一的優點是它確實能解決我的問題。數學建模一個題目“最佳陣容”，要算出所有得分會大于某個特定分數的出場陣容。

其實是一個0-1背包問題，但是約束條件比較多，算法自己又不在行，用回溯剪枝寫不出來。Lingo的規劃又只能做出一個解。

還好，動手算了一下，這個組合數也不過百萬級別，這對於現代的電腦完全是小case。所以用最丑的辦法寫了一個出來，當然，還是有點優化的。

程序我也不打算別人看懂，自己以后估計也不會再看，所以就不多解釋了。放這里做個留念，看看自己寫的程序有多丑。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Author: Liu Wei

def combination(items, n=None):
    if n is None:
        n = len(items)
    for i in xrange(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[i+1:]
            for c in combination(rest, n-1):
                yield v + c

def permutation(items, n=None):
    if n is None:
        n = len(items)
    for i in xrange(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[:i] + items[i+i:]
            for p in permutation(rest, n-1):
                yield v + p

# highest score for each player
scores = [
    [9.4, 9.8, 10, 9.5, 9.4, 9.9, 10, 10, 9.4, 9.7],
    [10, 9.4, 9.5, 9.9, 9.7, 9.9, 10, 10, 9.8, 9.5],
    [9.8, 10, 9.4, 9.7, 9.3, 9.1, 9.3, 9.9, 10, 9.6],
    [9.9, 9.6, 10, 10, 9.9, 9.4, 9.8, 9.8, 9.9, 9.8]
    ]

# final array
array = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    ]

# sparse array for 6 cols
sparse_array = [
    [0, 0, 0, 0, 0, 0], \
    [0, 0, 0, 0, 0, 0], \
    [0, 0, 0, 0, 0, 0], \
    [0, 0, 0, 0, 0, 0], \
    ]

def __sparse_array_check_valid():
    global sparse_array
    # 6 cols
    for i in xrange(6):
        sum = 0
        for j in xrange(4):
            sum += sparse_array[j][i]
        if sum > 3:
            return False
    return True

def __sparse_array_init():
    global sparse_array
    sparse_array =  [[0, 0, 0, 0, 0, 0], \
                    [0, 0, 0, 0, 0, 0], \
                    [0, 0, 0, 0, 0, 0], \
                    [0, 0, 0, 0, 0, 0], \
                    ]

def __sparse_array_set_row(p, r):
    global sparse_array
    a, b = p
    sparse_array[r][a] = 1
    sparse_array[r][b] = 1

def __sparse_array_clear_row(r):
    global sparse_array
    for i in xrange(len(sparse_array[r])):
        sparse_array[r][i] = 0

def sparse_array_output():
    global sparse_array
    print sparse_array

# generator for sparse arrays
def sparse_array_generator():
    global sparse_array
    # 4 rows
    __sparse_array_init()
    for r0 in combination(range(6), 2):
        __sparse_array_clear_row(0)
        __sparse_array_set_row(r0, 0)
        for r1 in combination(range(6), 2):
            __sparse_array_clear_row(1)
            __sparse_array_set_row(r1, 1)
            for r2 in combination(range(6), 2):
                __sparse_array_clear_row(2)
                __sparse_array_set_row(r2, 2)
                for r3 in combination(range(6), 2):
                    __sparse_array_clear_row(3)
                    __sparse_array_set_row(r3, 3)

                    if __sparse_array_check_valid():
                        yield sparse_array
                    #    sparse_array_output()

def __array_set_col(c):
    global array
    for i in xrange(len(array)):
        array[i][c] = 1

def __array_clean_col(c):
    global array
    for i in xrange(len(array)):
        array[i][c] = 0

def __array_init():
    global array
    array = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        ]

def set_allround_player(a):
    for i in a:
        __array_set_col(i)

def set_individual_player(sa, s):
    global array
    for i in range(4):
        for j in range(6):
            array[i][s[j]] = sa[i][j]

def array_generator():
    global array
    for g in combination(range(10), 4):
        # select cols for sparse array in big array
        s = [i for i in range(10) if i not in g]
        __array_init();
        # start to manipulate the array
        # first select all-round player
        set_allround_player(g)
        # then cope with individual event player
        for sa in sparse_array_generator():
            set_individual_player(sa, s)
            yield array

def calc_score(a):
    sum = 0
    for i in range(len(a)):
        for j in range(len(a[0])):
            sum += a[i][j] * scores[i][j]
    return sum

def final_generator():
    for a in array_generator():
        total_score = calc_score(a)
        if total_score >= 236.2:
            yield [a, total_score]

import os
os.chdir("d:/liuw/")
f = file("output", 'a')
for solution, total_score in final_generator():
    f.write(str(solution))
    f.write('\n')
    f.write(str(total_score))
    f.write('\n\n')
f.close()

用到了大量的generator，因為怕會內存不足。但是總yield一個全局數組總覺得有點別扭。話說我們這次的做題目用到了Lingo、Python、Matlab和C，果然是程序員的命，全部學計算機的人組個隊還是有好處的。

最後在電腦上跑了5分鐘左右，結果就出來了。假如想再快點，還可以做雙核並行計算。不過自己這方面沒什麽研究，程序也要得比較急，就沒有多管。

我们的项目需要改Xen用户空间的工具。Xen用户空间的工具是用Python写的，代码量还不小，用人肉方法去跟踪执行路径那是很笨的办法。我们需要trace调用，又不能改变函数原来的行为，那么最好的办法就是用decorator了。上网找一下，已经有人做过这样的工作了，我综合一下，改成下面的样子。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Decorators used to trace function/method calls
# derive from:
# http://wordaligned.org/svn/etc/echo/echo.py
# http://svn.osafoundation.org/chandler/trunk/chandler/util/autolog.py
#
# liuw
# 2010-5-27

import types

# Should use python log facility?
def do_log(s):
    print s

def _format_arg_value(arg_val):
    arg, val = arg_val
    return '%s=%r' % (arg, val)

def log_wrapper(fn, display_name=None):
    import functools
    if not display_name: display_name = fn.__name__

    code = fn.func_code
    arg_count = code.co_argcount
    arg_names = code.co_varnames[:arg_count]
    fn_defaults = fn.func_defaults or list()
    arg_defs = dict(zip(arg_names[-len(fn_defaults):], fn_defaults))

    @functools.wraps(fn)
    def wrapped(*v, **k):
        global indent

        positional = map(_format_arg_value, zip(arg_names, v))
        defaulted = [_format_arg_value((a, arg_defs[a]))
                     for a in arg_names[len(v):] if a not in k]
        nameless = map(repr, v[arg_count:])
        keyword = map(_format_arg_value, k.items())

        args = positional + defaulted + nameless + keyword

        do_log('%s(%s)' % (display_name, ', '.join(args)))
        return fn(*v, **k)
    return wrapped

def log_class(cls, methodAsFunction=False):
    """Python does not support class decorator, use it this way:
        class ClassName:
            ...
        ClassName = log_class(ClassName)
    """
    # disallow ALL builtin functions/methods
    allow = lambda s: not (s.startswith('__') and s.endswith('__'))

    names = cls.__dict__.keys()

    for name in names:
        if not allow(name): continue

        value = getattr(cls, name)

        if methodAsFunction and callable(value):
            setattr(cls, name, log_wrapper(value))
        elif isinstance(value, types.MethodType):
            # a normal instance method
            if value.im_self == None:
                setattr(cls, name, log_wrapper(value))

            # class and static method are more complex
            # class method
            elif value.im_self == cls:
                w = log_wrapper(value.im_func,
                               display_name='%s.%s' % (cls.__name__,
                                                       value.__name__))
                setattr(cls, name, classmethod(w))
            else:
                assert False

        # static method
        elif isinstance(value, types.FunctionType):
            w = log_wrapper(value,
                            display_name='%s.%s' % (cls.__name__,
                                                    value.__name__))
            setattr(cls, name, staticmethod(w))
    return cls

def log_module(m):
    # import m if m hasn't been imported
    if isinstance(m, str):
        d = {}
        exec 'import %s' % m in d
        import sys
        m = sys.modules[m]

    names = m.__dict__.keys()
    for name in names:
        value = getattr(m, name)
        if isinstance(value, type):
            setattr(m, name, log_class(value))
        elif isinstance(value, types.FunctionType):
            setattr(m, name, log_wrapper(value))

# ------------------------------TEST----------------------------------
class C1:
    @classmethod
    def f1(self, a, b=1, c=2):
        """f1"""
        pass

    @staticmethod
    def f2(d , e=3, f=4):
        """f2"""
        pass

    def f3(self, g):
        """f3"""
        pass
C1 = log_class(C1)

@log_wrapper
def test(x):
    pass

if __name__ == '__main__':
    inst = C1()
    inst.f1(10)
    inst.f2(20)
    inst.f3(1000)
    test(321)

functools.wraps这个decorator可以保证被修饰函数/方法的其他attribute与被wrap之前无异。比较让我感慨的是，我参考的有一部分是Chandler的代码，这个项目现在仍健在，实在不易。

Code copied from Xen.

def daemonize():
    # Detach from TTY

    # Become the group leader (already a child process)
    os.setsid()

    # Fork, this allows the group leader to exit,
    # which means the child can never again regain control of the
    # terminal
    if os.fork():
        os._exit(0)

    # Detach from standard file descriptors, and redirect them to
    # /dev/null or the log as appropriate.
    # We open the log file first, so that we can diagnose a failure to do
    # so _before_ we close stderr
    try:
        parent = os.path.dirname(XEND_DEBUG_LOG)
        mkdir.parents(parent, stat.S_IRWXU)
        fd = os.open(XEND_DEBUG_LOG, os.O_WRONLY|os.O_CREAT|os.O_APPEND, 0666)
    except Exception, exn:
        print >>sys.stderr, exn
        print >>sys.stderr, ("Xend failed to open %s. Exiting!" %
                             XEND_DEBUG_LOG)
        sys.exit(1)

    os.close(0)
    os.close(1)
    os.close(2)
    if XEND_DEBUG:
        os.open('/dev/null', os.O_RDONLY)
        os.dup(fd)
        os.dup(fd)
    else:
        os.open('/dev/null', os.O_RDWR)
        os.dup(0)
        os.dup(fd)
    os.close(fd)

    print >>sys.stderr, ("Xend started at %s." %
                         time.asctime(time.localtime()))

See more about Process Group from Wiki.

A note from ‘man 2 setsid’

A child created via fork(2) inherits its parent’s session ID. The ssession ID is preserved across an execve(2).

A process group leader is a process with process group ID equal to its PID. In order to be sure that setsid() will succeed, fork(2) and _exit(2), and have the child do setsid().

There are two predefined decorators in Python: @staticmethod and @classmethod.

I’m somewhat confused. For someone who has a shallow Java background, static method and class method are just the same.

See this for short.

And see Python PEP and manuals for details.

During the search about Python singleton pattern, I discovered [ActiveState recipe 66531].

In this Borg Pattern, instances’ internal dictionary points to the same place, so all instances share the same state. Also, [Alex Martelli], the author of this recipe, has a interesting comment: Borg Pattern != Singleton Pattern. I admit that I confuse Borg Pattern with Singleton Pattern at first.

It’s NOT a singleton object… it doesn’t NEED to be! This is a completely and deeply different pattern from Singleton, and thus I find the latest comment totally off-base. Singleton focuses (wrongly) on object IDENTITY: that’s what the Gof4 focuses on, that’s what “EffC++” focuses on, etc, etc. But we don’t really care about identity most of the time, but about state and behavior.

The “Borg” design pattern IS quite possible in C++ (just a bit more laborious, but not much) and was indeed once written up in C++ Report (but I forget the name it was given then and can’t find my old issue): you get as many objects as you want, with separate identities but all sharing state and behavior. That’s the POINT! Just about all the practical USEFULNESS of Singleton without the troublesome identity-issue that Singleton tends to give.

Here’s the code, quite simple, cool.

class Borg:
    __shared_state = {}
    def __init__(self):
        self.__dict__ = self.__shared_state

There are three ways to get this job done.

1 Module Implementation

The easiest implementation is to use a module scope variable. Module is persistent and shared by all references through its life time, no matter how it is renamed or modified.

See this [stackoverflow post on Python singleton]. Xen Xend makes use of this Python feature, which exposes a moudule function as interface to singleton class.

2 Class Implementation

The second implemention is class implementation, it’s not so convenient because Python does not support static variable itself. It certainly requires some tricks to get this job done.

According to this [ActiveState recipe 52558], it’s all about create exactly one instance of some class. But this is not so convient cause it uses automatic delegation.

3 Function Argument Default Value Implementation

Also another trick. The default value of a function argument is initialized only once and persistent. See the following example.

def f(x, l=[]):
    l.append(x)
    return l

This is least recommended.

想写个Python小程序，放到appengine上，把一个字符串反转。

原来是Python shell下面试的时候，中文的编码很奇怪，使用的是两字节的编码，不知道叫嘛。

于是写了一个小函数去判断双字节的非ASCII字符。

然后传到appengine上，发现不好用了。

后来小查一下，原来appengine传进来的编码已经把每个中文作为一个编码了。

又囧了一回。

总的来说，Python 2.5对于Unicode的支持还不是特别彻底。

没办法，谁让我以前从来没有担心过编码的问题呢。Orz

http://imliuw.appspot.com

写了一个Python CGI给Apache，但是运行的时候却是500 Internal Server Error。

查了一下errorlog，打印的错误信息是“Premature end of script headers”，google一把，发现类似的问题还真不少。原因就是Apache在等待脚本的输出，但是脚本没有输入。

但是我的脚本其实是有输出语句的。看来问题可能是在IO buffer那里了。

使用 -u 参数运行，问题解决。

前几天写的，动态生成函数。

非Stackless的Python做递归时实在有够慢，而且吃内存太多了。

不幸的是，我刚写完这个函数，就发现用Stackless Python跑原来的程序快得很。浪费时间了。

所以，最后还是用Stackless Python来跑了，不过这个东西还是放上来吧。跑起来比原来的CPython还是快不少的，因为用的都是循环。但是有一个限制，就是循环的最高嵌套数目是20。

# -*- coding: utf-8 -*-
#!/usr/bin/python

# non-recursive combination
# liuw

def MakeCombinationFunction(name, n, k):
    '''
This function returns a function object which will generate indexs
for combination.

name function name
n    total element count
k    take k elements from n, maximum is 20
    '''
    if k > n:
        k = n
    constructs = [('%sfor i%d in xrange(i%d+1, %d):\n'%(' '*(i+1)*4, i+1, i, n),
                   'i%d'%(i+1,))
                  for i in range(k)]
    f, a = map(None, *constructs)
    level = len(constructs)
    f = ' '.join(f)
    source = '    i0 = -1\n' + f + '%syield [%s]' % (' '*4*(level+1), ','.join(a))
    source = 'def %s():\n' % name + source
    scope = {}
    exec source in scope
    return scope[name]

昨天做东西的时候用到这个了。转过来的，觉得不错先记下了。

def comb(items, n=None):
    if n is None:
        n = len(items)
    for i in range(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[i+1:]
            for c in comb(rest, n-1):
                yield v + c

def perm(items, n=None):
    if n is None:
        n = len(items)
    for i in range(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[:i] + items[i+1:]
            for p in perm(rest, n-1):
                yield v + p

yield这个关键字，可以看一下limodou的一[Python 学习]2.5版yield之学习心得。