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分鐘左右，結果就出來了。假如想再快點，還可以做雙核並行計算。不過自己這方面沒什麽研究，程序也要得比較急，就沒有多管。

看到很多散列表（hash table）的实现中，长度都是一个素数。至于为什么一定要用素数，一下子也没想出所以然来。上网搜索了一下相关的文章，发现很多人也在讨论这个问题。

http://www.cs.unm.edu/~saia/numtheory.html

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth-2

http://blog.csdn.net/ilibaba/archive/2009/03/05/3960142.aspx

长度是否要是素数，能不能是合数，这个问题大家的意见得不到统一。支持用素数的人的理由是，素数可以使得散列的分布更加均匀。

自己总结一下看这些文章的心得。一个散列运算可以等价如下式：

hash(k) = mix(k) mod m

散列计算中，求余往往是最后一步，因为没有机器拥有无限的内存，所以必须把结果放入到有限的桶（bucket）中。求余前的运算，假如混淆（mix）得比较好的话，那么m使用素数还是合数，分布是一样的。假如混淆（mix）得不够好的话，那么一个素数可以把一些common pattern加以区别。至于什么样的数据混淆用什么样的mix算法比较好，这个得经统计才可以得出结论。总的来讲，使用一个素数总没有错，虽然运行慢了点，却可以得到相对较好的统计特性。个人看法。

Knuth的The Art of Computer Programming中，也用的是一样的理由推荐用素数的m。手上没有书，他应该没有提到合数的问题。上面也仅仅是我个人的一些想法，没有经过严格的证明，我也没有能力去证明。当然，很欢迎有人来指正我的错误。

手上有《算法导论》，第十一章散列表，对这个问题也没有给出严格的证明。但是它提到这样的一个问题，若m=2^p-1，则所有以2^p为基数的解释的字符串，无论字符位置怎么变化，得出的散列值都是一样的。这个证明比较简单，用同余的性质就可以证明，最后的值，其实是各个字符值的和再对m取余，所以散列值不会随字符的位置发生变化。

UPDATE：

StackOverflow上也有对这个问题的讨论。

http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus

上面的文章的观点和我总结出来的基本一致。

中文实在不清楚Process和Procedure如何进行区别，所以题目写了英文。

SICP习题1.11

A function f is defined by the rule that f(n) = n if n = 3 and f(n) = f(n-1) + 2f(n-2) + 3f(n-3) if n >= 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an interative process

SICP中已经给了一个例子，把linear recursive转化为iterative。后面一个要求其实是要把tree recursive进行转化。

好吧，递归的很简单。

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

我比较笨点，迭代的想了好久，写出来个挺锉的。

(define (f n)
  (if (< n 3)
      n
      (f-aux  4 2 1 0 3 n)))

(define (f-aux product a b c count n)
  (if (> count n)
      product
      (f-aux (+ a (* 2 b) (* 3 c))
             (+ a (* 2 b) (* 3 c))
             a
             b
             (+ count 1)
             n)))

这个代码是有冗余的。并不需要专门用一个product去记录结果。写出这样的代码，其实是对“迭代”理解得还不够深刻。改进后的代码是这样的。

(define (f n)
  (if (< n 3)
      n
      (f-aux  4 2 1 2 n)))

(define (f-aux a b c count n)
  (if (> count n)
      c
      (f-aux (+ a (* 2 b) (* 3 c))
             a
             b
             (+ count 1)
             n)))

count并不是必要的，可以直接用n自减到0即可。

ChinaUnix的win_hate也给出了一个版本。我改写了一下，好看点。

(define (g n)
  (g-aux 0 1 2 n))

(define (g-aux x y z n)
  (if (= 0 n)
      x
      (g-aux y z (+ (* 3 x) (* 2 y) z) (- n 1))))

但是这个版本的定义域默认是非负整数，我觉得这是不合适的，因为题目中没有明确指出这一点。

总结一下，有几点比较有意思的：

1. 线性递归和树形递归的尾递归情况，可以转化为迭代，其他情况未考究；
2. 转化时，关键是总结出各个参数的关系，没有必要使用专门的参数去记录结果；
3. 理解迭代的关键点是，每一时刻参数都保持有函数进一步运算的必要信息，而递归把这些信息放在了栈上，由系统隐式操作。

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

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之学习心得。

qsort([]) ->
    [];
qsort([Pivot|T]) ->
    qsort([X || X <- T, X < Pivot])
    ++Pivot++
    qsort([X || X <- T, X >= Pivot]).

用到了list comprehension，很好的功能。

很久都没有写点技术相关的文章了，是不是说明自己越来越懒了呢，呵呵。

突然想起那天 TX 的笔试题，最后一题附加题是要求判断一个 vector<string> letter 中的元素是否存在于另一个 vector<string> news 中。第一下给出了一个很锉的算法——双循环。用屁股想想都知道，这个 O(m*n) 的算法是最笨的方法了。多想了一下，记得以前考虑过一个单词统计的问题，用的是 Hash 的方法。其实这里用 Hash 也是比较好的，给 news 做一个 Hash Table，然后 letter 中的元素经过 Hash 之后看是否在 Table 中，这样的复杂度是 O(m+n)，好多了。

当然，现在要讲的也不是这么小儿科的问题。Hash 倒是用得不少了，但是具体怎么实现，却没有去了解过。那么今天就忙里偷闲做一下功课吧。

我这里谈的 Hash，意义在于提供一种快速存取数据的方法，即是要通过一种算法建立键值和真实值的关系。一个真实值只可以对应一个键值，但是一个键值却可能对应多个真实值（亦即是发生碰撞）。熟悉 Python、Perl 等语言的同学，应该对 key pair 不陌生，呵呵。对一个值 value 进行 Hash，实质上就是创建一种 （key, value）的二元组关系。其中 key 最坏情况下是可以在 O(n) 复杂度内进行查找的，这样就可以大大加快搜索的过程。设计得好的话，key 可以在 O(1) 内找到。

挺出名的一个 Hash 函数

unsigned long hashpjw(register CONST char *str,
                      register unsigned long int size)
{
    register CONST char *p;
    register unsigned long h=0,g;

    asc_assert((NULL != str) && (size > 0));

    for(p = str; *p != ''; p++) {
        h = (h << 4) + (*p);
        if (0 != (g = h&0xf0000000)) {
          h = h ^ (g >> 24);
          h = h ^ g;
        }
    }
    return h % size;
}

OpenSSL 中的 Hash 函数

unsigned long lh_strhash(char *str)
{
    int i,l;
    unsigned long ret=0;
    unsigned short *s;

    if (str == NULL) return(0);
    l=(strlen(str)+1)/2;
    s=(unsigned short *)str;

    for (i=0; i < l; ++i)
        ret^=(s[i]<<(i & 0x0f));
    return(ret);
}

/* The following hash seems to work very well on normal text strings
* no collisions on /usr/dict/words and it distributes on %2^n quite
* well, not as good as MD5, but still good.
*/
unsigned long lh_strhash(const char *c)
{
    unsigned long ret=0;
    long n;
    unsigned long v;
    int r;

    if ((c == NULL) || (*c == 0))
    return(ret);
/*
unsigned char b[16];
MD5(c,strlen(c),b);
return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
*/

    n=0x100;
    while (*c)
    {
        v=n|(*c);
        n+=0x100;
        r= (int)((v>>2)^v) & 0x0f;
        ret=(ret(32-r));
        ret & = 0xFFFFFFFFL;
        ret^=v*v;
        c++;
    }

    return((ret>>16)^ret);
}

看到代码，觉得其实做一个 Hash 函数，关键不在于代码有多长，更多是分布的计算和碰撞的处理。现在暂时没有时间去深究。改日看了《算法导论》再来深入。