Shuffle&Sample

近来打算通过自己实现几个常见模型来复习一下之前看过的，顺便练习一下Python语法的熟练度。首先准备搭好除模型外的整个程序的其他部分，比如数据的导入、划分。
在写划分数据集部分的函数时，查了一下random模块中有sample(data, k)和shuffle(data)两个函数，分别实现从一个序列中采样k个数和将数据集内数据打乱的，其中sample函数将采样后数据作为返回值，shuffle函数直接对data操作，无返回值。在这里对两个函数的实现算法探究一下。
######shuffle
shuffle的意思是让序列乱序。在random模块的shuffle函数中，用的是经典的Fisher-Yates shuffle算法。其伪代码如下

for i = 1:N
    temp = random(0, N-i)
    交换 a[temp] 和 a[N-i]
end

易证，对于每个元素，其shuffle后在每个位置的概率都为N1​。同理，也可从前往后实现。
######sample
sample意思是从原序列中随机选择k个元素，不改变原序列。
最简单的自然是每次随机从[0, N-1]中选一个，若该元素已经选出，则重新选择，伪代码为

while length(已抽)<k
    temp = random(0, N-1)
    if temp in 已抽
        continue
    已抽.append(a[temp])
end

该算法需要一块额外的空间，进行存储原序列元素是否已经被抽取的标记。但是，当k较大时，每次random到已经抽到的概率越来越大，此时时间复杂度升高，接近于O(nlogn)。
也可以采用shuffle的思路，到第k个时停止，此时时间复杂度为O(k)。但是，此时原序列已经被改变，或者需要另外复制一个原序列，在此序列上进行处理。
水塘抽样算法(Reservoir sampling)可以适用于N为一很大或者未知数量的情况，尤其是不能将所有N个项目存入内存中时。其伪代码如下

for i in range(1, k)
    reservoir[i] = stream[i]
for i in range(k, N+1)
    p = random(0, i)
    if p < k
        reservoir[p] = stream[i]

时间复杂度为O(N)。