海量数据之随机选取

Oct 25, 2018

问题：

常规情况下，从一个长度为n的数组中等概率选取k个元素的方法：

selectedIdx = []
for i in k:
    idx = random(1, n)
    if not idx in selectIdx:
        selectIdx.append(idx)

当数组长度未知时（如给定一个链表，长度未知），要求只扫描一遍链表的前提下，等概率选取k个数字，此时上述方法就不可用了。

先看一下基本的情况：

一、从长度未知的链表中等概率、随机选择1个数（Random Pick）

第一次直接选取头结点元素作为choice，而后以二分之一的概率决定是否用下一个替换它，以1/3的概率决定是否使用第三个元素替换choice…

int randomSelect(pHead) {
    int select;
    int count = 1;
    ListNode pCurr = pHead;

    while (pCurr != null) {
        randomNum = random(1, count)
            if (randomNum == 1) {
                select = pCurr.val;
            }
        pCurr = pCurr.next;
        count++;
    }

    return select;
}

二、从长度未知的链表中等概率、随机选择k个数

void randomSelect(pHead, k) {
    ListNode pCurr = pHead;
    int[] choice = new int[k];
    i = k + 1;

    while (pCurr != null) {
        r = random(1, i);
        if (1 <= r <= k) {
            choice[r] = pCurr.val;
        }
        pCurr = pCurr.next;
        i++;
    }
}

证明如下：

对于第1个结点，被选中，且未在后续选取中被替换：

p = k/k+1 * k+1/k+2 * k+2/k+3 * … * n-1/n = k/n

对于第2个结点：

p = k/k+2 * k+2/k+3 * … * n-1/n = k/n

…