map、reduce、filter、shuffle

map

对指定序列的每一个元素执行指定映射函数，返回映射后的序列

map(function, sequence) -> sequence

reduce

对指定序列的元素进行累积，返回累积的最终结果

reduce(function, sequence) -> value

filter

对指定序列的元素进行过滤，返回过滤后的序列

filter(function, sequence) -> sequence

shuffle

将指定序列中的元素随机排序，时间复杂度O(N)

shuffle(sequence)

具体实现：

import random
def knuth_shuffle(list):
    # no extra space
    for i in range(len(list) - 1, 0, -1):
        p = random.randrange(0, i + 1)
        list[i], list[p] = list[p], list[i]
    return list

r = knuth_shuffle([1, 2, 2, 3, 3, 4, 5, 10])
print(r)

蓄水池抽样

从未知长度(非常大)的序列中随机取k个元素，保证每个元素被取出的概率相等

先把读到的前k个对象放入“水库”，从第k+1个对象开始，以k/(k+1)的概率选择该对象，以k/(k+2)的概率选择第k+2个对象，以此类推，以k/m的概率选择第m个对象（m>k）。如果m被选中，则随机替换水库中的一个对象。最终每个对象被选中的概率均为k/n。

参考：

python中的map、filter、reduce函数

python实现三种洗牌算法

蓄水池抽样——《编程珠玑》读书笔记

Python特殊语法：filter、map、reduce、lambda

三种洗牌算法