By

在欧拉工程中，很多时候都需要用到素数，而得到素数比较好就是用筛法生成。筛法还是很容易理解的，随便找一本教科书的可以找到。

有了这个函数后，要得到100以内的素数就非常容易了。

1
2
3
4
5
6
7
8
9
10
11
12
13
def getPrimes(n):
    primes = [True for i in xrange(n + 1)]
    primes[0] = primes[1] = False
    for x in xrange(2, n + 1):
        if not primes[x]:
            continue
        m = x * x
        while m <= n:
            primes[m] = False
            m += x
    return [i for i in xrange(n + 1) if primes[i]]

print get_primes(100)

2014年8月16日更新：
才发现这个函数的速度还不理想，于是改成

1
2
3
4
5
6
7
8
9
def getPrimes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    i = 2
    while i * i <= n:
        if primes[i]:
            primes[i * i:n + 1:i] = [False] * ((n - i * i) / i + 1)
        i += 1
    return [i for i in xrange(n + 1) if primes[i]]

之所以这么改，可参看Python筛法求素数的优化

联系作者

By

知道这题，是在冼镜光的《C名题精选百则》中。记得这题是自己做出来的，所以稍微回忆一下，就能记起来。也许算法之所以这么难，就是因为不是自己想出来的，所以虽然看过，却很容易忘记。或许应该不只是看算法，而要知道原始作者的思考过程，这样才能真正理解。就像要想理解TCP/IP协议一样，比较好的办法是自己去设计TCP协议，看如何保证可靠传输。扯远了。

对于这题，很容易写出如下程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def max_con_sum(s):
    length = len(s)
    max_sum = s[0]
    i = 0
    temp_sum = s[0]
    while i + 1 < length:
        i += 1
        if temp_sum < 0:
            temp_sum = 0;
        temp_sum += s[i]
        if temp_sum > max_sum:
            max_sum = temp_sum

    return max_sum
L = [2,-3,3,50]
print max_con_sum(L)

而如果还想知道最大连续子序列的开始位置和结束位置，之需要再增加额外的记录信息即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def max_con_sum(s):
    length = len(s)
    max_sum = s[0]
    start = 0;
    end = 0
    i = 0
    temp_sum = s[0]
    while i + 1 < length:
        i += 1
        if temp_sum < 0:
            temp_sum = 0;
            start = i
        temp_sum += s[i]
        if temp_sum > max_sum:
            max_sum = temp_sum
            end = i

    return (max_sum,start,end)
L = [2, -3, 3, 50]
max_sum,start,end =  max_con_sum(L)
print max_sum,start,end

联系作者

By

给你一个list L, 如 L=[2,8,3,50], 对L进行选择排序并输出交换次数,
如样例L的结果为1

对于这题，无非就是写一个选择排序，在排序过程中记下交换的次数。很意外的是Pythontip上竟然会有那么多人写错，
按照选择排序的定义，写一个应该是分分钟的事。或许这帮人都没看书。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
L=[2,8,3,50]
length = len(L)
count = 0
for i in xrange(length):
    minum = L[i]
    index = i
    for j in xrange(i + 1, length):
        if L[j] < minum:
            minum = L[j]
            index = j
    if index != i:
        L[i],L[index] = L[index],L[i]
        count += 1
print count

联系作者

By

扔蛋问题说的是，100层楼，给两个特制鸡蛋。从某层扔下鸡蛋，鸡蛋就会碎。问至少要测试多少次才能试出这个层数。对于这个问题，许多人都可以背出答案14层。但如果是200层呢?

事实上，还可以对这题进行扩展，假设n层，e个鸡蛋，求至少要测试多少次，才能测出这个层数。

对于这题，可以用动态规划。还是在面4399时，面试官要我解释什么是动态规划，当时没能解释清楚。现在想来，动态规划有两个重要的因素，一个是最优子结构，还有一个是重叠子问题。按我的理解，最优子结构说的是，当前的最优解包含了子问题的最优解。重叠子问题说的是，子问题具有重叠部分。

而对于这题，可以写出一个递推公式,设n为楼层数,e为鸡蛋数。
f(n,e) = 1 + min{max{f(n - r, e),f(r - 1, e -1)}} 其中r属于{2,3,…,n - 1},初始条件为f(n,1) = n, f(1,e) = 1, f(2,e) = 2. 这里要求n,e都是正整数。
写成程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def egg(n, e=2):
    dp = [[n for i in xrange(e + 1)] for j in xrange(n + 1)]
    for i in xrange(1, n + 1):
        dp[i][1] = i
    for i in xrange(1, e + 1):
        dp[1][i] = 1
        dp[2][i] = 2
    for i in xrange(3, n + 1):
        for j in xrange(2, e + 1):
            for r in xrange(1, n):
                dp[i][j] = min(dp[i][j], 1 + max(dp[i - r][j], dp[r - 1][j - 1]))

    return dp[n][e]

print egg(100, 2)

对于鸡蛋数为2时，还有特殊的解法。在鸡蛋数为2时，楼层数与测试次数如下：
1 1
2 2
3 2
4 3
5 3
6 3
7 4
8 4
9 4
10 4
11 5
…
于是可以猜测,对于楼层数n ,只要找到第一个x ,使得 x * (x + 1) / 2 >= n即可，对于100,正好是14。类似地，对于开头提出的鸡蛋数为2，楼层数为200时，测试层数也可以类似的求解

联系作者

By

取石子游戏说的是有两堆任意数量的小石子，游戏由两个人轮流取石子，对于取法，游戏规定有两种，一种是可以在任意的一堆中，取走任意多的石子；一种是在两堆中同时取走相同数量的石子。游戏规定，最后把石子全部取完的为胜者。现在假设初始时两堆石子的数目为a和b, a <= b，假设双方都采取最好的策略，问先取的人是胜者还是败者。

对于这题，可以得到在以下情况下，先取的人必败，其它情况下，先取的人必胜。
1 2
3 5
4 7
6 10
8 13
9 16
…

可以看出，这两个数字之间一定有规律，而说到规律，很容易想到的是黄金分割比。记得那时还很粗心的将其中的数字写错了，于是任晓祎同学就过来纠正了。时光飞逝啊，已经过去三年了。

联系作者

By

最短编辑距离说的是两个字符串A和B，求用最少的字符操作将字符串A转化为字符串B。这里所说的字符操作包括
1.删除一个字符
2.插入一个字符
3.将一个字符改为另一个字符

分析：
先比较A和B的第一个字符，分两种情况
1.两个字符相等
此时只需要计算A和B剩下字符的编辑距离
2.两个字符不相等
此时有三种选择，
（1）删除A的第一个字符，之后求A剩下的字符与B的编辑距离
（2）在A中插入B的第一个字符，之后求A与B剩下字符的编辑距离
（3）将A的第一个字符变成B的第一个字符，之后求A剩下的字符与B剩下的字符的编辑距离
之后返回这三种情况的最小值，再加上1，即是A转化为B的最短编辑距离

依照上述方法，很容易写出一个递归方法

1
2
3
4
5
6
7
8
9
10
11
12
def edit_distance(a, b):
    if a == '':
        return len(b)
    if b == '':
        return len(a)
    if a[0] == b[0]:
        return edit_distance(a[1:], b[1:])
    else:
        return min(edit_distance(a[1:], b), edit_distance(a, b[1:]), edit_distance(a[1:], b[1:])) + 1
A="fxpimu"
B="xwrs"    
print edit_distance(A, B)

唯一的缺点是，这种方法太慢了，于是想到用动态规划，此时最好还是从后面考虑，也就是考虑A和B最后一个字符的相等情况，再根据上面的分析计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def edit_distance(a, b):
    la = len(a)
    lb = len(b)
    dp = [[0 for i in xrange(lb + 1)] for j in xrange(la + 1)]
    for i in xrange(1, la + 1):
        dp[i][0] = i
    for j in xrange(1, lb + 1):
        dp[0][j] = j
    for i in xrange(la):
        for j in xrange(lb):
            if a[i] == b[j]:
                dp[i + 1][j + 1] = dp[i][j]
            else:
                dp[i + 1][j + 1] = min(dp[i + 1][j], dp[i][j + 1], dp[i][j]) + 1
    return dp[la][lb]

A="fxpimu"
B="xwrs"
print edit_distance(A, B)

联系作者

By

两年前面试4399时，和面试官说起用Python来做欧拉工程，于是面试官很感兴趣地说，有没有写一些小模块来求解，当时只是摇头，想想写写算法题还可以，写模块就太大了。现在想来，模块也无非是一些函数的集合，在接欧拉工程的过程中，就会经常遇到一些问题，需要用类似的方法解决，如果把这些共同的部分写在一起，不也是一个模块了？

质因子分解是经常需要用到的，这里给一个解决的办法。例如要求120的质因子分解，先用2去除，一直到不能整除为止，记得到2^3,以及剩下的15，之后用3去除，得到3以及剩下的5，之后用5去除，得到5以及0，分解过程结束。写成程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from collections import defaultdict
def get_divisors(n):
    divisors = defaultdict(int)
    if n % 2 == 0:
        while n % 2 == 0:
            divisors[2] += 1
            n /= 2
    i = 3
    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                divisors[i] += 1
                n /= i
        i += 2
    if n > 1:
        divisors[n] += 1
    return divisors

有了这个方法就可以用来求一些数的最小公倍数，例如求，2 3 5 8 的最小公倍数

1
2
3
4
5
6
7
8
9
10
L = [2, 3, 5, 8]
factors = defaultdict(int)
for i in L:
    divisors = get_divisors(i)
    for d in divisors.iterkeys():
        factors[d] = max(factors[d], divisors[d])
res = 1
for d in factors.iterkeys():
    res *= d ** factors[d]
print res

联系作者

By

  • 判断一个字符串是否是IP地址
    ^([1-9]?[0-9]{1}|1[0-9]{2}|2[0-4][0-9]|25[0-5])(.([1-9]?[0-9]{1}|1[0-9]{2}|2[0-4][0-9]|25[0-5])){3}$
  • 邮箱匹配 r'^(?!\.)(?![\w.]*?\.\.)[\w.]{1,64}@(?=[-a-zA-Z0-9.]{0,255}(?![-a-zA-Z0-9.]))((?!-)[-a-zA-Z0-9]{1,63}\.)*(?!-)[-a-zA-Z0-9]{1,63}$'

联系作者

By

在Sphinx中，如果你调用的是C的api，并使用更新属性的功能，而此时，你想将更新后的索引冲刷到硬盘，你就会发现C的api中没有提供这个功能。而在Java,PHP,Python中，都提供了FlushAttributes这个接口来完成这个功能，于是你不得不另外在写一个程序来调用这个接口。

仔细想想，Sphinx都是用C++写的，而C的API中竟然没有提供这个接口，反倒是其它语言有提供，真是匪夷所思。所幸，代码都是开源的，想要自己有这个接口，自己动手写一个就好了，也许这就是开源的好处。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int sphinx_flush_attributes(sphinx_client * client) {
    char *buf, *req, *p;
    int req_len = 0;
    if (!client) {
        printf("not valid client\n");
        return -1;
    }
    buf = malloc ( 12 + req_len ); // request body length plus 12 header bytes
    if ( !buf ) {
        set_error ( client, "malloc() failed (bytes=%d)", req_len );
        return -1;
    }

    req = buf;

    send_word ( &req, SEARCHD_COMMAND_FLUSHATTRS );
    send_word ( &req, VER_COMMAND_FLUSHATTRS );
    send_int ( &req, req_len );

    // send query, get response
    if ( !net_simple_query ( client, buf, req_len ) )
        return -1;

    // parse response
    if ( client->response_len < 4 ) {
        set_error ( client, "incomplete reply" );
        return -1;
    }

    p = client->response_start;
    return unpack_int ( &p );
}

之后还要添加
SEARCHD_COMMAND_FLUSHATTRS = 7，
VER_COMMAND_FLUSHATTRS = 0x100，
以及在头文件中添加int sphinx_flush_attributes(sphinx_client * client)；即可。

联系作者

By

很早之前就知道MMSEG分词算法，网上也有各种语言的实现。最近了解Sphinx-for-Chinese的分词后，才知道它也是使用的MMSEG，并且CoreSeek也是使用的MMSEG。也许MMSEG是互联网上使用知名度最高的分词算法了吧，因为它简单并且高效。

更进一步了解后，知道MMSEG是台湾人蔡志浩提出来的。蔡志浩是一位心理学教师，在美国伊利诺伊读博士期间，选修了语言学，在这个过程中，随手写了MMSEG。看蔡志浩网站，总是很舒心，因为蔡老师的文笔很好，总会用通俗的语言把问题讲清楚，而且蔡老师的博客涉及范围极广，设计，心理，写作，社会观察，旅游等等。也正是因为他的博客，我才用实名建立自己的博客。以下回归正题。

MMSEG总的说来就是四个规则。
1.最长匹配原则
2.最大平均长度
3.最小长度方差
4.最大单字单词的语素自由度

算法步骤：
1.选定一个分词个数，得到可行的分词情形
2.利用4条原则得到最优分词可能
3.得到最优分词的第一个词，回到步骤1继续分词

举个例子最好理解。下面是要对“研究生命起源的原因主要是因为它的重要性”进行分词。
1.首先选定分词个数为3，则可以得到可行的分词情形如下：
研 究 生
研 究 生命
研究 生命 起
研究 生命 起源
研究生 命 起
研究生 命 起源
2.利用4条原则得到最优分词可能
运用第1条原则后，可以得到最优分词可能为一下两条
研究 生命 起源
研究生 命 起源
运用第2条原则，这两个结果相同
运用第3条原则，可以得到最优的结果为
研究 生命 起源
3.从最优结果中得到第一个词，也就是“研究”，之后对“生命起源的原因主要是因为它的重要性”运用相同的步骤进行分词

有必要对原则4进行解释，这条原则说的是单字的成为语素的自由度。当分到”主要是因为“就会用到。对于”主要是因为“
第1步骤中得到：
主 要 是
主 要是 因为
主要 是 因
主要 是 因为
第2步骤中，由前三条原则，只剩下一下两个
主要 是 因为
主 要是 因为
之后再运用第4条原则，这里单字”是“为独立语素的可能比”主“要大，所以最优结果为
主要 是 因为

见过的MMSEG算法实现中，素心如何天上月的http://yongsun.me/2013/06/simple-implementation-of-mmseg-with-python/无疑是最简明清晰的。Python确实不错，短短100行就把算法的精髓展示出来，并且几乎可以不用写注释了。模仿他的实现，写了一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#coding:utf-8
from collections import defaultdict
import codecs
from math import log

class Trie(object):
    class TrieNode():
        def __init__(self):
            self.value = 0
            self.trans = {}
    def __init__(self):
        self.root = self.TrieNode()
    def add(self, word, value=1):
        cur = self.root
        for ch in word:
            try:
                cur = cur.trans[ch]
            except:
                cur.trans[ch] = self.TrieNode()
                cur = cur.trans[ch]
        cur.value = value
    def _walk(self, node, ch):
        if ch in node.trans:
            node = node.trans[ch]
            return node, node.value
        else:
            return None, 0
    def match_all(self, s):
        ret = []
        cur = self.root
        for ch in s:
            cur, value = self._walk(cur, ch)
            if not cur:
                break
            if value:
                ret.append(value)
        return ret

class Dict(Trie):
    def __init__(self, filename):
        super(Dict, self).__init__()
        self.load(filename)

    def load(self, filename):
        with codecs.open(filename, "r", "utf-8") as f:
            for line in f:
                word = line.strip()
                self.add(word, word)
class CharFreq(defaultdict):
    def __init__(self, filename):
        super(CharFreq, self).__init__(lambda: 1)
        self.load(filename)
    def load(self, filename):
        with codecs.open(filename, "r", "utf-8") as f:
            for line in f:
                line = line.strip()
                word, freq = line.split(' ')
                self[word] = freq
class MMSEG():
    class Chunk():
        def __init__(self, words, chars):
            self.words = words
            self.lens = map(lambda x: len(x), words)
            self.length = sum(self.lens)
            self.average = self.length * 1.0 / len(words)
            self.variance = sum(map(lambda x: (x - self.average) ** 2, self.lens)) / len(words)
            self.free = sum(log(float(chars[w])) for w in self.words if len(w) == 1)
        def __lt__(self, other):
            return (self.length, self.average, -self.variance, self.free) < (other.length, other.average, -other.variance, other.free)
    def __init__(self, dic, chars):
        self.dic = dic
        self.chars = chars
    def __get_chunks(self, s, depth=3):
        ret = []
        def __get_chunk(self, s, num, seg):
            if not num or not s:
                if seg:
                    ret.append(self.Chunk(seg, self.chars))
                return
            else:
                m = self.dic.match_all(s)
                if not m:
                    __get_chunk(self, s[1:], num - 1, seg + [s[0]])
                else:
                    for w in m:
                        __get_chunk(self, s[len(w):], num - 1, seg + [w])
        __get_chunk(self, s, depth, [])
        return ret
    def segment(self, s):
        while s:
            chunks = self.__get_chunks(s)
            best = max(chunks)
            yield best.words[0]
            s = s[len(best.words[0]):]

if __name__ == "__main__":
    dic = Dict("dict.txt")
    chars = CharFreq('chars.txt')
    mmseg = MMSEG(dic, chars)
    print ' '.join(mmseg.segment(u"北京欢迎你"))
    print ' '.join(mmseg.segment(u"研究生命起源的原因主要是因为它的重要性"))
    print ' '.join(mmseg.segment(u'开发票'))
    print ' '.join(mmseg.segment(u'武松杀嫂雕塑是艺术，还是恶俗？大家怎么看的？'))
    print ' '.join(mmseg.segment(u'陈明真做客《麻辣天后宫》的那期视频哪里有？'))
    print ' '.join(mmseg.segment(u'压缩技术是解决网络传输负担的 有效技术。数据压缩有无损压缩和有损压缩两种。在搜索引擎中用到的压缩技术属于无损压缩。接下来，我们将先讲解各种倒排索引压缩算法，然后来分析搜索引擎技术中词典和倒排表的压缩。'))

用到的两个文件dict.txt和chars.txt

联系作者