Mac的磁盘空间真的是令人抓狂。每次不知道咋回事，就报磁盘空间将要爆满，我就赶紧去删掉一些没用的文件, 或者执行下clean_my_mac.sh, 过不了几天，又爆满。

今天已经想不到要删哪个没用的文件，使用du -sh *又太慢，于是只好上网找解决办法。上网查了之后，找到了OmniDiskSweeper这个清理磁盘空间，竟然很好用。 清理后，空间如下。

1
2
3

➜  ~ df -h
Filesystem      Size   Used  Avail Capacity  iused    ifree %iused  Mounted on
/dev/disk1     233Gi  143Gi   90Gi    62% 37424607 23556639   61%   /

需要注意的是，使用OmniDiskSweeper时，回到上层目录是用方向键中的向左方向键。

前些天，有个姑娘说想学Python，我一听，双眼放出万丈光芒，心想如果我教会她，万一姑娘一时高兴，以身相许，老妈就再也不用担心我了，那岂不是美滋滋。于是准备要怎么教她学编程，夜晚，躺在床上，回忆自己的编程经历，想起高一时与朝辉一起学习VBasic的点点滴滴，想起大一时为了考C语言二级的突击学习，真是岁月如梭。一顿感慨后，心中已有了大致的想法，于是有了这篇文章。

几乎所有的编程语言，都是由3种基本的程序结构组成，顺序，循环，选择，弄懂这三种后，就可以写程序了。下面且听我一一道来。

print

先来看看print语句

1
2

print('邓世龙')
输出 邓世龙

1
2
3
4

a = 1
b = 2
print(a, b)
输出 1 2

顺序结构

然后来看顺序结构, 顺序结构很容易理解，就是程序是一句句往下执行，

1
2
3
4
5
6

a = 1
b = 2
a = 3
b = 4
print(a, b)
输出 3 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

s = 0
print(s)
s = s + 1
print(s)
s = s + 2
print(s)
s = s + 3
print(s)
s = s + 4
print(s)

输出如下
0
1
3
6
10

接下来看看循环结构。现在我们要完成一个计算任务，计算1 + 2 + 3 + … + 10的和，我们可以从1一直加到10，这就需要循环。在绝大多数编程语言里，都提供for或者while来完成循环，这里先来看for, 而在这之前，先了解下list, 也就是列表。

list(列表)

list相当于其它编程语言里的数据，主要是用来存放统一类型的数据

1
2
3
4
5
6
7
8
9
10
11
12
13

x = [1, 2, 3, 4, 5, 6]
print(type(x))  # 显示x的类型
print(len(x))   # 求列表的长度
print(x[0])     # 取第一个值
print(x[2])     # 取第三个值
print(dir(x))   # 显示列表的变量和方法

输出如下
<class 'list'>
6
1
3
['__add__', '__class__', '__contains__', '__delattr__', '__delitem__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 'append', 'clear', 'copy', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']

range

1到6的列表手写问题也不大，但1到100，1到1000的列表如果手写会疯掉的，所以Python提供了range这个函数。

1
2
3
4
5
6
7
8
9
10
11

x = list(range(10))
print(x)
y = list(range(1, 10))
print(y)
z = list(range(1, 10, 2))
print(z)

输出如下
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 3, 5, 7, 9]

循环结构 for

下面就是for循环的语法，注意for循环后面有冒号，之后print还要缩进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# for循环 打印1到10
n = 10
for i in range(1, n + 1):
    print(i)
    
输出如下:
1
2
3
4
5
6
7
8
9
10

现在我们就可以编写求1 + 2 + 3 … + 10的和的程序

1
2
3
4
5
6
7
8
9
10

# 循环，for循环求和, 求1 + 2 + ... + 10的和, 

s = 0
n = 10
for i in range(1, n + 1):
    s = s + i
print(s)

输出
55

选择 if

现在我们要求1到10以内，所有偶数的和，这就会用到选择。

那么如何判断是偶数呢？对2取余就行了，如果余数是0，就是偶数

1
2
3
4
5

print(4 % 2 == 0)  # % 是求余操作
print(3 % 2 == 0)
输出
True
False

现在加上if判断，求1到10以内所有偶数的和

1
2
3
4
5
6

s = 0
n = 10
for i in range(1, n + 1):
    if i % 2 == 0:
        s = s + i
print(s)

选择 and

如果要求30以内，既能被3，又能被5整数的所有整数的和，这时候就会用到and操作

1
2
3
4
5
6
7
8

s = 0
n = 30
for i in range(1, n + 1):
    if i % 3 == 0 and i % 5 == 0:  # 有15，30
        s = s + i
print(s)
输出
45

选择 or

如果要求10以内，能被3，或能被5整数的所有整数的和, 这时候就会用到or操作

1
2
3
4
5
6

s = 0
n = 10
for i in range(1, n + 1):
    if i % 3 == 0 or i % 5 == 0:  # 有 3，5，6，9，10
        s = s + i
print(s)

continue 进入下一次循环

求10以内，能被3或能被5整数, 但不能被2整除的所有整数的和，这时候可以继续使用and和or的组合来判断，但更方便的，还是用continue,

1
2
3
4
5
6
7
8
9
10

s = 0
n = 10
for i in range(1, n + 1):
    if i % 2 == 0:
        continue
    if i % 3 == 0 or i % 5 == 0:  # 有 3，5，9
        s = s + i
print(s)
输出
17

循环 while

for循环也可以用while循环来代替, while后面跟着判断条件，如果条件为True, 也就是为真，就会一直执行while循环里的内容; 如果为False，就会跳出循环。例如求1 + 2 + … + 10的和，用for循环编写如下

1
2
3
4
5

s = 0
n = 10
for i in range(1, n + 1):
    s = s + i
print(s)

改成while，如下

1
2
3
4
5
6
7

s = 0
i = 1
n = 10
while i <= n:
    s = s + i
    i = i + 1
print(s)

既然有了for循环, 为何还要有while循环呢？考虑这样一个问题，求前6个能被3或5整除的整数的和。这时如果用for循环，就不是很合适，因为你不知到要到什么时候才能结束, 这种情况用while循环就很方便。

1
2
3
4
5
6
7
8
9
10
11
12

s = 0
i = 1
count = 0
n = 6
while count < n:
    if i % 3 == 0 or i % 5 == 0: # 前6个为 3，5，6，9，10, 12
        s = s + i
        count = count + 1
    i += 1
print(s)
输出
45

也就是说for循环主要用于确定循环次数的场合，而while循环主要用途循环次数不定的场合

循环 break

break用于跳出循环，上面的例子也可以修改为如下程序

1
2
3
4
5
6
7
8
9
10
11
12

s = 0
i = 1
count = 0
n = 6
while True:
    if i % 3 == 0 or i % 5 == 0: # 前6个为 3，5，6，9，10, 12
        s = s + i
        count = count + 1
        if count == n:
            break
    i += 1
print(s)

下面再讲讲set, dict还有函数，就可以编写实际代码了。

set

set就是集合，主要用来提高查询速度

1
2
3
4
5
6

s = list(range(1, 100000000))
x = set(s)
print('#')
print(99999999 in s)
print('##')
print(99999999 in x)

在上面的例子中99999999 in s这里会有些卡顿，因为它要从s里的第一个数从前往后一个一个比较，而99999999 in x这里执行非常快，因为set是优化过的数据结构，底层实现是哈希表，可以很快的进行查询

dict

dict，也就是字典，和set类似，只不过多了个value值，也用来提高查询速度，应用广泛，例如查询身份证号对应的一些个人用户信息等等

1
2
3
4

d = {'a': 65, 'b': 66}
print(d['a'])
输出
65

函数

函数就是一些可以重复利用的代码段。例如要求1到10的所有整数的和，与求2到5所有整数的和，这是两个类似的问题，就可以编写求和函数来解决，求和函数如下。声明一个函数是用def关键字，然后是函数名，后面跟着参数。

1
2
3
4
5
6
7
8
9
10
11

def my_sum(a, b):
    s = 0
    for i in range(a, b + 1):
        s = s + i
    return s

print(my_sum(1, 10))
print(my_sum(2, 5))
输出
55
14

到了这里，三种程序结构就讲完了，弄懂这三种结构就可以编写更大一些的程序，解决实际问题。而实际上，绝大多数程序，都是由这三种基本结构构成的，无非就是更复杂的数据结构和算法，还有调用库函数。

最后问题来了，我在哪里输入这些代码呢？Jupyter notebook了解下。

本来觉得没必要写的，但是呢，少年看到这个用法觉得还是挺新奇的，竟然还可以这么玩，于是记录下。

前些天，监控系统那边提了需求，要求应用必须加上访问时长日志，并得知道是谁访问的，于是就想到了使用Django的Middleware. 请求进来的时候记下时间，返回的时候记下时间，两者相减，就是请求的时长。代码如下

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

import logging
import time
from datetime import datetime

from django.utils.deprecation import MiddlewareMixin

logger = logging.getLogger(__name__)


class LoggingMiddleware(MiddlewareMixin):
    def process_request(self, request):
        request.start_time = time.time()

    def process_response(self, request, response):
        execute_time = time.time() - request.start_time
        path = request.path
        username = '-'
        method = request.method
        if hasattr(request, 'user') and not request.user.is_anonymous:
            username = request.user.username
        code = response.status_code
        now = datetime.now().strftime('%Y-%m-%d %H:%M:%S')
        res = "{} {} {} {} {:.2f} {}".format(now, username, path, method, execute_time, code)
        logger.info(res)
        return response

之后在Django配置里，LOGGING->formatters里加上

1
2

very_simple:
    format: '%(message)s'

LOGGING->handlers里加上

1
2
3
4
5

monitor:
    level: 'INFO'
    class: 'logging.handlers.RotatingFileHandler'
    filename: 'monitor.log'
    formatter: 'very_simple'

在LOGGING->loggers里加上

1
2
3
4

'helper.middleware.logging_middleware':
   handlers: ['monitor']
   level: 'INFO'
   propagate: False

其中helper.middleware.logging_middleware是LoggingMiddleware这个类的存放位置，

最后在项目settings的MIDDLEWARE的最前面加上’helper.middleware.logging_middleware.LoggingMiddleware’

如此日志就会输出到monitor.log

已知一个整数数组x, 对于任何一个元素x[i]而言, 在x[i]右边, 而且值不比x[i]小的元素(亦即j > i而且x[j] >= x[i]的x[j])都叫做x[i]的右支配元素(Right Dominator). 在x[i]所有的右支配元素中最靠近x[i]的那一个, 就叫做最靠近的右支配元素(Right Nearest Dominator). 当然, 不见得每一个元素都有支配元素的, 如最大元素就没有,问题是, 编写一个程序, 接收一个数组, 把数组中每一个元素最靠近的右支配元素找出来

说明: 看个例子比较容易明了这个问题的要求。如果数组的内容是2, 1, 3, 5, 4那么3, 5, 4都是2的右支配元素, 但3是最靠近的一个, 所以3是2的最靠近右支配元素, 同理1与3的最靠近右支配元素分别是3与5, 5与4都没有最靠近右支配元素; 对5而言, 右边没有元素比它大;就4而言, 右边没有元素了。

看起来程序并不难写,因为可以x[1], x[2] …, x[i],…一个接一个查过去; 当查到x[i]时，就查x[i+1], x[i+2]…, 于是第一次找出比x[i]大或相等的元素, 就是x[i]的最靠近右支配元素了。但是这样的做法效率并不高。举例而言, 如果一个数组的元素是从大到小排好的但是最后一个元素是整个数组的极大值(例如,5, 4, 3, 2, 1, 6)。若数组有n个元素, 处理x[0]要比较n-1次, 处理x[1]时比较n-2次, 一般而言, 处理x[i]时要比较n - i次。所以就一共用了(n-1) + (n-2) + … + 3 + 2 + 1 =n (n-1)/2, 差不多是n ** 2次的比较.

因此, 挑战是, 能不能写出比较次数与n成正比的程序?

参考文献: 这个题目与解法来自 Hubert Wagener在1988年的一篇文章。Wagener是用这个观点来决一个计算几何(Computational Geometry)中的重要问题, 不过他的重点是平行式的算法,但是他的文章中两个解法都有。有兴趣的朋友可以参看

H Wagener. Triangulating a Monotone Polygon in Parallel. Computational Geometry and Its Applications, Lecture Notes in Computer Science, No 333, Springer-Verlag. 1988, Pp 136-147

解答见dominator.py

这个问题一般叫做过半数(Majority)问题, 也有人称为投票(Voting)问题, 但以前者说法居多。假设有1, 2, … n等n个人参加投票, 他们只能圈选一个人, 但是却可以选任何一人, 甚至于可以选不在这n个人中的另一个都行。例如, 如果5个人投票, 分别投1、8、1、100、1; 1、3、5都投给1, 2投给8, 4投给100。问题是, 写一个程序接收这些投票结果, 看看有没有人的得票过半数, 就以上例来看, 1的得票数就过半数了.

说明: 这是个名题, 也与其他问题一样有简单但效率低的解法, 但也有较有技巧且效率高的做法, 简单做法是, 把投票结果先从小到大排好, 把投给同一个人的票就收在一起, 接着从头查起, 看看一连串相同的值的个数, 如果有过半数的, 那个人就当选了。用上面的例来看, 从小到大排好是1, 1, 1, 8, 100, 很显然1有3个, 过半数了, 因此1会当选。

这是一个大家都会想到的想法, 但事实上, 排大小的这一步是不必要的, 能开发出这样的程序吗? 不过要记住一点, 不能对候选人的数目作任何假设, 因为如果假定候选人是1, 2, …, k, 那么这个题目就简单至极而不会变成名题了。为什么呢? 准备一个有k个元素的
数组, 然后……(一定马上就知道是怎么回事了吧!)。

参考文献: 这个题目起源于容错(Fault Tolerant)计算机系统中的一个问题, 是在1981年由 J. Moore(发现匹配字符串的 Boyer-Moore方法的那一个More)提出来的。1982年, J Misra与 David Gies两人合写了一篇深入探讨程序写作的文章, 同年 M.J.Fischer与S. L Salzberg提出了个比此例复杂的方法, 比较1.5n+1次就可以找出结果, 而且还证明了不管用什么办法,比较次数都不可能少于1.5n - 2次。推荐读读上述的文章, 以及所附的文献, 了解问题的来龙去脉。

1. M.J. Fischer and S L Salzberg. Solution to Problem 81-5, Journal of Algorithms, Vol3(1982), pp.375~379
2. Misra and D Gries. Finding Repeated Elements, Science of Computer Programming Vol2(1982), pp.143~152
3. J.Moore. Problem 81-5, Journal of Algorithms. Vol 2(1981), Pp 208-209

解答见voting.py

已知一个整数数组, 在这个数组中的一个递增序列, 就是把若干元素删除后所留下的元素按从小到大的顺序排列。举例而言, 如果数组是1,3,5,7,8,2,9,4,10,6, 那么1,5,8,9,10是个递增序列, 3,5,8,9,10也是一个递增序列, 1,3,5,7,9,10 也是递增序列。简单地说, 可以依数组元素的次序选出若干元素, 使得从小到大排好 ,那么这就是个递增序列。例如3,8; 2,9; 7,10; 2,4,6; …。但是9,4,10; 5,7,8,2,9等却不是递增序列。 问题是, 写一个程序接收一个整数数组, 找出这个数组中最长的递增序列的长度。以上面的例子来看, 1,3,5,7,8,9,10是最长的递增序列, 所以程序输出7的结果。

说明: 递增序列的意义已如上述, 程序要如何写? 看起来似乎很难下手, 但总是有迹可寻的,为什么呢? 递增序列不会凭空出现, 一定是先有了几个, 然后又出现一个新元素, 看看这个新元素能不能加到已有的递增序列后面, 如果可以,已有的递增序列的长度就多了1; 但若不能添加, 那要做些什么事呢? 那就要自己想了. 先看个例子, 还是以1,2,4,3,6为例。假设目前已经发现了如下的几个递增序列:

1,2,4,6(长度为4)

1,2,3(长度为3)

现在新来的元素是5, 因此5可以补在1,2,3后面而得到1,2,3,5(长度为4); 那么5对1,2,4,6的关系又如何? 这就要自己想了。

这个问题的起源可能是组合数学(Combinatoric Mathematics)。组合数学中有一个定理, 它说n ** 2 + 1个数中一定有一个长度至少为n的递增或递降序列。此处不过是要求写一个程序把最长的递增序列的长度找出来而已, 会写这个程序之后, 递降序列也不过是同一回事。

解答见longest_increase_sequence.py

已知两个字符串s与t, 要研究如何把字符串s经由一连串编修动作变成t。能够使用的就是插入一个符号, 以及删除一个符号; 把某个符号换成另一个, 就可以通过先把它删除再在原地插入所需的符号来完成。编写一个程序, 接收s与t, 找出如何才能够在最少步骤之下把s改成t。

说明: 把一个字符串修改成第一个字符串在语汇分析(Lexical Analysis)与拼字分析(Spelling Check)中有很重要的地位。例如, 已知s这个字符串可能有问题, 而在s中应该会出现t[1],t[2]…t[k], 这几个字符串其中之一, 但是用哪一个比较好呢? 通常会选使用最少修动而能够把s改出来的那一个, 这一项技巧在化学中研究分子结构相当有用.

如果已知ABCD这个字符串,想把它改成XBYD,一看就知道可以把A换成X, C成Y就行了, 这就有了4个动作一删除A, 插入X, 删除C, 插入Y; 但也可以把ABCD全部删除,再插入XBYD, 这就要8个动作, 4个删除, 4个插入。当然, 两者相比, 自然是第一个方法好些。这是一个简单的例子, 但当s与t这两个字符串很长时就不那么容易看出结果了, 因此这个题目就是要求编写这样的一个程序.

前面的最长部分序列(Longest Common Sequence)的技巧对本题非常有帮助, 不妨先看看LCS这个程序

a[1]a[2]…a[i]与b[1]b[2]…b[j]相互变换可以分为以下几种情况

1. 如果a[i] = b[j], 于是a[1][2]…a[i]变成b[1]b[2]…b[j]的次数等于a[1]a[2]…a[i-1]变成b[1]b[2]…b[j-1]的次数
2. 如果a[i] != b[j], 分成三种情况讨论: 第一, 检查a[1]a[2]…a[i]变成b[1]…b[j-1]后，再插入一个b[j]; 第二, 检查a[1]…a[i-1]变成b[1]b[2]…b[j]后再插入一个a[i]; 第三: a[1]…a[i-1]变成b[1]b[2]…b[j-1]后，删除a[i], 插入b[j]

解答见string_edit.py

如果A=a[1]a[2]…a[m]是一个长度为m的字符串, 把其中的若干(可能是0个, 也可能是n)个符号去掉, 而得到一个新字符串, 这个新字符串就称为A的子序列(Subsequence). 例如, 若A=abc0123, 那么b02, abcl23, b3, c, ab0123, ab12等都是A的部分序列.

假设给出两个字符串A与B, 长度分别是m与n, 那么A与B就含有若干共同的子序列, 至少虚字符串(或说是空字符串)就是一个共同部分序列; 所谓C是A与B的公共子序列, 指的是C是A的子序列, C也是B的子序列。编写一个程序,把A与B的公共子序列中最长的那一个找出来。

这个同题一般都称为最长公共子序列(Longest Common Subsequence)问题, 简称为LCS

说明: 这是一个非常有名的题目, 而且是一个分支中的主要问题, 这个分支称为字符串匹配
(String Matching), 可以说是计算机科学研究领域中比较早开发的科目, 目前的应用很广, 从语音分析到生化都能看到这一支的踪迹, 参看下面参考文献中各篇文章的介绍. 写程序的熟手或了解算法理论的朋友是不难写这个程序的, 因为它不过是一个动态规划(Dynamic Programming)的应用而已。给一点提示, 如果两个字符串是A=a[1]a[2]…a[m], B=b[1]b[2]…b[n],考虑a[i]与b[j]

如果在a[1]a[2]…a[i-1]与b[1]b[2]…b[j-1]这两个字符串的前段中已经找到了一个长度是k的公共子序列, 那么会有两种可能:

1. 如果a[i] = b[j], 于是把原来长度为k的共同部分序列后面补上ai, 就会得到a[1]a[2]…a[i]与b[1]b[2]…b[j]的一个长度是k+1的公共子序列
2. 如果a[i] != b[j],分成两种情况讨论: 第一, 检查a[1]a[2]…a[i-1]与b[1]…b[j-1]b[j]的最长公共子序列的长度; 第二, 检查a[1]…a[i-1]a[i]与b[1]b[2]…b[j-1]的最长共同部分序列的长度。最后进行适当的处理。

有了这个观点在心中, 找出最长公共子序列应该不会十分困难, 但是要如何把那个序列找出来呢? 这或许要好好想一想。

下面推荐的这本书是论文集有许许多与编修字符串方面的文章可供参考, 自然也包含有最长共同序列这个问题:此外,书中还有不少这些方面的应用与说明。

R.A. Wagner and M.J. Fischer. The String-to-String Correction Problem, Joumal of ACM。Vol.21(1974) p168~173

解答见longest_common_subsequence.py

编写一个程序, 用Gray码(Gray Code)的顺序列出一个集合的所有子集。
说明: 这个问题其实是在看有没有办法把Gray(人名)码用程序编写出来, 有了Gray码，找出对应的集合是件简单的事。

什么是Gray码? nbit的Gray码是一连串共有2 ** n 个元素的数列, 每一个元素都有能nbit, 而且任何相邻的两个元素之间只有1的值不同, 例如,3个bit的Gray码:

000 001 011 010 110 111 101 100

是一组Gray码, 任何相邻两个元素都只有1bit值不同。但是，Gray码却并不是惟一的，把它循环排列或是用反过来的顺序写,也会得到一组Gray码; 比如说, 如果把最后3个素放到最前面去, 就会得到

111 101 100 000 001 011 010 110

也是一组Gray码。

产生Gray码的方法很多，这里这介绍其中一种。
将2bit Gray码列出
00
01
11
10
将3bit Gray码列出
000
001
011
010
110
111
101
100
观察3bit Gray码可以发现，它可以由2bit Gray码来得到。

解答见gray_code.py

8后问题(Eight Queen Problem)是指在一个8 8的西洋棋盘上要如何放置8个皇后棋, 且不会互相吃到对方; 皇后棋可以吃掉任何它所在的那一列、那一行, 以及那两条对角线(米字型)上的任何棋子。请写一个程序, 读入一个值n表示棋盘的大小, 然后求出n n格棋盘上放n个皇后棋且不会相互吃掉对方的所有解答。

说明: 这是广义的N后问题, 因为所要求的是“所有”解答, 而不单是其中的一组, 对大多数会运用递归的人来说,这个题目反而容易做些。这一类型题目的解法通常要用到回溯(Backtrack)的技巧, 不管用递归还是不用递归都是如此, 虽然会浪费时间,但多半会找到解答。

回溯的技巧通常都以下面的面目出现, 如下所示。

1
2
3
4
5
6
7
8
9
10

S = 目前可以用得到的位置;
当S非空: 
    取出S中一个元素, 令为s
    如果s可以安全使用，那么
        定出s已经使用
        如果还可以从S再进一步，那么
            用S调用自己
        如果已经有了答案，那么
           显示答案
        把s定成没有在使用

解答见n_queen.py