《Design of Computer Programs》学习笔记（1 - 2）Winning Poker Hands - Bonus:Shuffling

Winning Poker Hands

Bonus:Shuffling

视频链接：
Bonus:Shuffling

1. Bad Shuffle

import random

def deal(numhands, n=5, deck=[r+s for r in '23456789TQKA' for s in 'SHDC']):
    "Shuffle the deck and deal out numhands n-card hands."
    random.shuffle(deck)
    return [deck[n*i:n*(i+1)] for i inrange(numhands)]

print deal(2, 7)

对后面代码中all()函数的备注：

Help on built-in function all in module __builtin__:

all(...)
    all(iterable) -> bool

    Return True if bool(x) is True for all values x in the iterable.
    迭代iterable中的每一个值x，如果每1个bool(x)，都是True，则返回True。
    例如，all([True, True])，返回True。
    If the iterable is empty, return True.
    如果iterable是空的，则返回True。
    例如，all([]),返回True。
返回False的例子：
>>> all([False])
False
>>> all([False, False])
False
>>> all([True, False])
False

Peter提供了一个完全错误的算法

def shuffle(deck):
    "My teacher's algorithm."
    N = len(deck)
    swapped = [False] * N
    # swapped = [False, False, ..., False] 共有N个False。
    while not all(swapped):
        i, j = random.randrange(N), random.randrange(N)
        # i, j是deck的随机的索引下标
        swapped[i] = swapped[j] = True
        # 将swapped列表中的i、j位置的False置为True。
        swap(deck, i, j)
        # 将deck列表中的i、j位置的元素互换位置。
    # 再去看前面的while循环条件：
    # 如果swapped列表中的元素全为True
    # 即，deck中的元素全都互换了至少一次
    # 则not all(swapped)为False，

def swap(deck, i, j):
    "Swap elements i and j of a collection."
    print 'swap', i, j
    deck[i], deck[j] = deck[j], deck[i]

视频 Bad Shuffle - YouTube

可行的方法：Algorithm P for permutation(序列；排列)

2. 练习：Shuffle Runtime

3. 练习：Good Shuffle

Peter的代码(高德纳的P算法)：

def shuffle(deck):
    "Knuth's Algorithm P"
    N = len(deck)
    for i in range(N-1):
        swap(deck, i, random.ranrange(i, N))
        # 遍历deck，为索引为i的元素做1次交换。
        # 对于任何未在索引i位置出现的元素，
        # 我们以同等的机会交换它。

def swap(deck, i, j):
    "Swap elements i and j of a collection."
    "交换一个collection中的索引为i和j的元素。"
    print 'swap', i, j
    deck[i], deck[j] = deck[j], deck[i]

解释：
对于位置i的元素，我们交换【位置i的元素】与【从i排列到尾部N的元素】；
然后继续下一个位置i的元素。
对于第0、1、2。。。和N-2的位置的元素，都是这样。
最后这个原始排列中的所有元素，都有一个同等的机会出现在每个位置。

QUIZ
for i in range(N-1)如果把N-1换成N，会有什么问题？

□ IndexError
□ ValueError
□ no error, unfair
■ no error, fair

答案
如果换成N，花费的时间会稍微长一点。
具体发生的事情：
先考虑i等于倒数第2个的情况，此时，最后的2个元素互换；
最后一轮的交换是最后1个元素与自身的交换，不起任何作用。
为了避免这种多余的开销，我们使用N-1，而不是N。

4. 练习：Is It Random

teachers shuffle，每一轮排列，是否有一个均等的机会(是否概率相同)？：

□ yes
■ no, some different probability.
□ no, some 0 probability.

这个问题有点难，你可能需要阅读这个算法来分析，你可能需要写一些代码来分析位置。

答案：
Peter写了一些测试代码，来生成这个输出：

5. Testing Shuffles

Peter的一段代码

def test_shuffler(shuffler, deck='abcd', n=10000):
    counts = defaultdict(int)
    # 首先，保持对(来自shuffler的)每一个结果的数量(counts)的跟踪。
    # 第一，初始化counts为1个defaultdict，
    # 它的默认值是int的默认值，为0。
    # 所以所有的counts从0开始。
    for _ in range(n):
    # 然后，我从range(n)开始，n次，默认值是10000，
    # 我们将洗牌10000次。
        input = list(deck)
        # 我们将传入deck，构造一个deck的列表list
        # deck是字母的字符串'abcd'。这是最简单的情况。
        shuffler(input)
        # 然后我们将输入input，进行洗牌shuffler，
        counts[''.join(input)] += 1
        # 然后统计结果。这里的结果是项的列表。
        # 我们将把项的列表添加进1个单独的字符串，
        # 让它们更小、也容易处理，
        # 然后我们只是增加计数。
    '''
    所以abcd进来，我们制造一个列表，制造列表abcd，
    我们洗牌shuffle，可能我们的得到bcad，
    然后我们为那种结果，增加计数count。
    '''
    e = n*1./factorial(len(deck)) ## expected count
    # 现在我们就算期望的计数count，
    # 分子是1，分母是deck中的项的数量的阶乘，
    # 因为所有的n阶乘，n是deck中的项的长度。
    # 所以，期望的数量应该是n次那个东西that。
    ok = all((0.9 <= counts[item]/e <= 1.1)
             for item in counts)
    # 然后，我们会说，结果是ok的，
    # 如果(期望值的)每个项的数量的比例，应该大约是1。
    # 如果它在0.9和1.1之间，那就是ok的。
    name = shuffler.__name__
    print '%s(%s) %s' % (name, deck, ('ok' if ok else '*** BAD ***'))
    print '   ',
    for item, count in sorted(counts.items()):
        print "%s:%4.1f" % (item, count*100./n),
    print

# 下面这个函数，测试一个列表的shufflers洗牌函数和一个列表decks纸牌
def test_shufflers(shufflers=[shuffle, shuffle1], decks=['abc', 'ab']):
    for deck in decks:
        print
        for f in shufflers:
            test_shuffler(f, deck)

def factorial(n): return 1 if (n <= 1) else n*factorial(n-1)

test_shuffler函数，用来检查shuffle程序是不是准确的，如果产生了均衡的结果(就是正确的)。

shuffle1不是个好的函数，Peter修理了它，搞了2个新的函数

def shuffle2(deck):
    "A modification of my teacher's algorithm."
    N = len(deck)
    swapped = [False] * N
    while not all(swapped):
        i, j = randrange(N), randrange(N)
        swapped[i] = True
        swap(deck, i, j)

def shuffle3(deck):
    "An easier modification of my teacher's algorithm."
    N = len(deck)
    for i in range(N):
        swap(deck, i, ranrange(N))

6. 练习：Comparing Shuffles

QUIZ
考虑每种shuffle程序

                O(N)    O(N平方)    correct
shuffle           ■                   ■         Knuth 的 P算法
shuffle1                   ■          错的       Teacher's
shuffle2                   ■          ■
shuffle3          ■                   错的

7. Computing Or Doing

注意到，shuffle程序——我们写的和标准库中的random.shuffle，返回None。
shuffle程序的想法是改变输入input。

在计算一个结果(computing a result)和做点什么(doing something)之间，有永恒的张力。
computing： sqrt函数、sin函数等等，获取一个输入，返回一个结果。它们不修改输入input，并且他们创建一个新的值，作为结果。我们把计算出一个结果的函数，称为纯函数。
doing： 但是像shuffle的函数或者子程序或者方法，是不同的。它们获取一个输入input，修改那个结果。它们获取输入的状态，并且对输入input的状态做了什么，而不是仅仅计算一个结果。这些做了一些事的，称为不纯的，我喜欢称之为子程序、而不是函数。因为他们在数学意义上不是函数；它们对输入有一个影响。

本课程中，我展示的、大多数的代码，是computing type，而不是doing type。主要的原因是，computing code更容易测试。
如果我想为一个computing函数、一个纯函数写一个测试，我可以做类似的事情：

assert sorted([3, 2, 1]) == [1, 2, 3]

另一方面，如果我想测试一个子程序，这个子程序does something，影响了输入的状态，我将不得不首先设置一些状态。

input = [3, 2, 1]
input.sort()
assert input == [1, 2, 3]

上面的例子看起来很简单，但是，通常来说，随着我们增加更多的状态，我们有了更多的do的函数，而不是compute函数，会有更多的工作，要设置状态、调用方法、然后测试它。对于纯函数，测试更容易。

如果不是不得已，尽量用纯函数(compute)。

参考文献：

1. Design of Computer Programs - 英文介绍 - Udacity；
2. Design of Computer Programs - 中文介绍 - 果壳；
3. Design of Computer Programs - 视频列表 - Udacity；
4. Design of Computer Programs - 视频列表 - YouTube。