随机问题与 Top K 问题

随机问题与 Top K 问题

随机问题

问题描述

对于给定的数组 $Q$ ,将其每个元素随机分布在数组中,并且使得之后每个元素被取到的概率相等?

Shuffle 算法

Code

public static void shuffle(int[] q) {
    for (int i = q.length - 1; i >= 0; i--)
        swap(q, i, (int) (Math.random() * (i + 1)));
}

随机性证明

设整个数组长度为 $length$,当前元素下标为 $i\in[0,length-1]$ ,每次从 $[0,i]$ 中选择一个元素进行交换。

在第一次交换中,各个元素被选中的概率为 $\frac{1}{i+1}$

第二次交换中,任一元素被选中的概率为 $\frac{i+1}*\frac{1}=\frac{1}{i+1}$

以此类推,各个元素被选中的概率都为 $\frac{1}{i+1}$ ,可得出概率相等


问题描述

那么现在问题升级了,由于数据集比较大并且在不断增加,我们无法将所有数据全部都放到内存中

那么是否有办法在这个数据流(可设其总数为 $I$ )中选出一个元素,使得在时间复杂度 $O(N)$ 的情况下,该元素被选中的概率为与其他元素被选中的概率相等?

蓄水池抽样算法

Code

public class RandomSelect {
    public static int sampling(int[] q) {
        int t = 0;

        for (int i = 1; i <= q.length; i++) {
            if (Math.random() < 1 / i) t = q[i - 1];
        }

        return t;
    }
}

随机性证明

设整个数组元素个数为 $length$,当前元素下标为 $i\in[1,length]$ 。

  • 当 $i=1$ 时,必然选择第一个元素。

  • 当 $i=2$ 时,选择第一个元素的条件为上次筛选被选中,且本次筛选没有被排除,则有 $1*\frac{1}{2}=\frac{1}{2}$ ,

  • 当 $i=3$ 时,任然选择第一个元素的概率为 $\frac{1}{2}(1-\frac{1}{3})=\frac{1}{2}\frac{2}{3}=\frac{1}{3}$ ,

依此类推,可得选择任一元素(设其下标为 $j$ )的概率为 $\frac{1}(1-\frac{1}{j+1})...(1-\frac{1})(1-\frac{1})=\frac{1}$ 故该算法可以确保选择出的元素的随机性。

升级

数组抽样问题

问题描述

那么如果要选择出 $K$ 个元素,使得选出的元素在整个数据集(可设其总数为 $I$ )中出现的概率相等

Code
public class RandomSelect {
    private static final int N = 5;
    private static final int[] q = new int[N];
 	private static int ptr = 0;
    
    public static int[] sampling(int[] txt, int k) {
       	for (int i = 1; i <= txt.length; i++) {
            if (i <= k) q[idx++] = txt[i - 1];
            else {
                int j = (int) (Math.random() * i) + 1;
                if (j < k) q[j - 1] = txt[i - 1];
            }
        }
        
        return q;
    }
}
随机性证明

设整个数组非空长度为 $N$,当前元素下标为 $i\in[1,length]$ ,要选择的元素个数为 $K$ ,随机数的值为 $R$

  • 当 $i\le K$ 时,每个元素被选中进入数组的概率为 $1$ 。

  • 当 $i>K$ 时

    1. 当 $i=K+1$ 时,第 $i$ 个元素被选中进入数组的前提为随机数的值 $R\in[0,K]$ ,则概率为 $\frac{K+1}*\frac{1}=\frac{1}{K+1}$ ,不进入数组的概率则为 $1-\frac{1}{K+1}=\frac{K+1}$
    2. 由此可得,当 $i=N$ 时,第 $i$ 个元素进入数组的概率为 $\frac*\frac{1}=\frac{1}$,同时不进入数组的概率为 $\frac$

故数组中的每个元素数据不被替换的概率为 $\frac{K+1}\frac{K+1}{K+2}...*\frac=\frac$

分布式抽样问题

问题描述

当数据量规模十分巨大时,单机的内存访问,磁盘 I/O,CPU 频率就会成为数据吞吐量的瓶颈,此时常常采用分布式的结构来分担数据压力,提高吞吐量。

那么如果使用分布式的方式,又要如何保证均匀的取样呢?

算法过程

设分布式架构下有 $N$ 台机器,处理的总数据量为 $S$,取样值为 $M$

  1. 将整个数据流分为 $N$ 个子流,分布到所有机器上,处理的数据量记为 $N_{1},N_{2},N_{3},...,N_$(同时记 $N_0=0$),同时每台机器都运行一个蓄水池抽样模型,取得 $M$ 个数据
  2. 生成一个随机数 $R\in[1, S]$,如果 $R\in[\sum{N_0+N_1+...+N_},\sum{N_0+N_1+...+N_}+N_i]$,则从 $N_i$ 的取样中再次取样加入到最终取样中
  3. 循环第 2 步 M 次
随机性证明
  1. 在第 $K$ 台机器上取样值的概率为 $\frac$
  2. 随机数取值在第 $K$ 个区间的概率为 $\frac$
  3. 在第 $K$ 个取样值中随机取样取到任意元素的概率为 $\frac{1}$,循环取值 $M$ 次

故最后的取样值 $M$ 相对于总数据流数量 $S$ 的概率为 $\frac\frac\frac{1}*M=\frac$,故可以确保随机取样。

Top K 问题

问题描述

在一个数据集中,选择出第 $K$ 大的元素

快速排序

可以将所有数据读取到内存中排序并取下标取值

Code

public class TopK {
    public static int get(int[] q, int k) {
        sort(q, 0, q.length - 1);
        retunr q[k - 1];
    }

    private static void sort(int[] q, int l, int r) {
        if (l >= r) return;
        int i = l - 1, j = r + 1, k = q[l + r >> 1];
        while (i < j) {
            do i++; while (q[i] < k);
            do j--; while (q[j] > k);
            if (i < j) swap(q, i, j);
        }

        sort(q, l, j); sort(q, j + 1, r);
    }
}

时间复杂度

由于每一次调用函数都遍历了整个数组,同时每一次递归调用都会将数组二分,直到区间中只有一个元素

故时间复杂度为 $O(N*logN)$ 即 $O(NlogN)$

堆排序

将所有数据依次读取到堆中,同时维持堆大小为 $K$

Code

public class TopK {
    private static final PriorityQueue<Integer> que = new PriorityQueue<>();
    
    public static void get(int[] q, int k) {
        for (var i : q) {
            if (que.size() < k) que.add(i);
            else if (que.peek() < i) {
                que.poll();
                que.add(i);
            }
        }
        return que.peek();
    }
}

时间复杂度分析

首先需要遍历整个数据集,同时堆进行大小为 $K$ 排序(底层为树的排序,故时间复杂度 $logK$),故时间复杂度为 $O(NlogK)$

快速选择算法

快排思想 + 二分思想,每次选取一半的区间

Code

public class TopK {
    public static int quickSelect(int[] q, int l, int r, int t) {
        if (l == r) return q[l];
        int i = l - 1, j = r + 1, k = q[l + r >> 1];
        while (i < r) {
            do i++; while (q[i] < k);
            do j--; while (q[j] > k);
            if (i < j) swap(q, i, j);
        }

        int cnt = j - l + 1;
        if (cnt <= t) return quickSelect(q, l, j, t);
        else return quickSelect(q, j + 1, r, t - cnt);
    }
}

时间复杂度分析

第一次遍历整个数组 $N$ ,第二次遍历选择出的数组的一半,期望值为 $O(\frac{2})$ ···

依次累计可得,时间复杂度为 $O(\sum{N +\frac{2}+\frac{4}+...})=O(N *\sum{1+\frac{1}{2}+\frac{1}{4}+...})=O(2N)=O(N)$

参考