2019-11-25

算法 TopK问题

words: 1.2k views: time: 5min

这里考虑一个具体问题：有大约40万个数字(数字范围：0～200000000000000），数字没有重复，求这些数字中，最大的100个数字之和

思路一

最简单的思路就是进行排序然后选取最大的100个数，具体可以设定一个容量为100的数组，然后对输入的数据进行插入排序，并且在排序之后如果超过100那么就丢弃超过的部分，不过我们可以利用二分法对插入进行优化一下

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/issue/issue2/_Main.java

private static void top1(Long[] array){
    long stime = System.currentTimeMillis();
    long[] result = new long[K];
    int size = 0;
    for(int i = 0; i < array.length; i++){
        binaryInsert(result, array[i], size);
        if(++size >= K){
            size = K;
        }
    }

    System.out.println(System.currentTimeMillis() - stime + "ms,  " + comp_times);
    System.out.println(Arrays.toString(result)); 
}

private static void binaryInsert(long[] result, long e, int size){
    // 空数组，直接插入
    if(size == 0){
        result[0] = e;
        return;
    }

    //大于头节点，直接插入到头节点
    if(e >= result[0]){ 
        System.arraycopy(result, 0, result, 1, size - 1);
        result[0] = e;
        return;
    }

    //小于尾节点，如果数组还没满则直接插入队尾，否则直接丢弃
    if(e < result[size - 1]){ 
        if(size < K){
            result[size] = e;
        }
        return;
    }

    // 二分法从中间插入
    int middle = 0, left = 0, right = size - 1;
    middle = (left + right) / 2;
    while(middle > left && middle < right){
        if(comp(e, result[middle]) < 0){ 
            left = middle; 
        }else if(comp(e, result[middle]) >= 0){
            right = middle;
        }
        middle = (left + right) / 2;
    }

    int move = K - (middle + 1) -1;
    if(move > 0){
        System.arraycopy(result, middle + 1, result, middle + 2, move);
        result[middle + 1] = e;
    }
}

private static long comp(long o1, long o2){
    comp_times++;
    return o1 - o2;
}

思路二

借助堆排序，具体可以通过小顶堆，每次插入后将最小值弹出即可，不过这里可以直接利用前面笔记[算法堆排序]中的工具类TopHeap

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/issue/issue2/_Main.java

private static void top2(Long[] array){
    TopHeap<Long> queue = new TopHeap<>(100, new Comparator<Long>(){
        @Override
        public int compare(Long o1, Long o2) {
            return o2.compareTo(o1); 
        }
    });

    long stime = System.currentTimeMillis();
    for(int i = 0; i < array.length; i++){
        queue.put(array[i]);
    }

    System.out.println(System.currentTimeMillis() - stime + "ms,  " + queue.getCompTimes());
    System.out.println(queue.getTop());
}

思路三

如果理解快速排序，那么可以递归进行切分操作，每次切分将小于元素放到右边，而大于等于元素放到左边，这样当前切分位置在100时，左手边自然是最大的100个元素。

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/issue/issue2/_Main.java

private static void top3(Long[] array){
    long stime = System.currentTimeMillis();
    recursion_partition(array, 0, array.length - 1, null);
    System.out.println(System.currentTimeMillis() - stime + "ms,  " + comp_times);

    List<Long> list = new ArrayList<>();
    for(int i = 0; i < K; i++){
        if(array[i] == null){
            break;
        }
        list.add(array[i]);
    }
    list.sort(new Comparator<Long>(){
        @Override
        public int compare(Long o1, Long o2) {
            return o2.compareTo(o1); // 这里不要用 o2 - o1，存在溢出问题
    }); 
    System.out.println(list);
}

private static void recursion_partition(Object[] array, int low, int high, Comparator comp) {
    int partition = partition(array, low, high, comp);
    if(K < partition){
        recursion_partition(array, low, partition - 1, comp);
    }else if(K  > partition){
        recursion_partition(array, partition + 1, high, comp);
    }else{
        return;
    }
}

private static int partition(Object[] array, int low, int high, Comparator comp) {
    int i = low, j = high + 1; // 左右扫描指针
    while(true){ 
        while(++i < high && comp(array, low, i, comp) <= 0){}
        while(--j > low && comp(array, low, j, comp) > 0){}
        if(i >= j){
            break;
        }
        swap(array, i, j);
    }

    if(low != j){
        swap(array, low, j); // 将切分元素放入正确的位置 
    }
    return j;
}

private static int comp(Object[] array, int a, int b, Comparator comp) {
    comp_times++;
    if(comp != null){
        return comp.compare(array[a], array[b]);
    }else{
        return ((Comparable)array[a]).compareTo(array[b]);
    }
}

private static void swap(Object[] array, int a, int b) {
    Object t = array[a];
    array[a] = array[b];
    array[b] = t;
}

比较

单从耗时角度有点难以体现复杂度的高低，所以这里记录了一下具体的比较次数

1
2
3

16ms,  808582
31ms,  7194427
16ms,  625797

简单做个分析：

在插入排序中，每次插入操作最多需要 $\log_{2} {k}$ 次比较，如果运气好刚好在两端，则只需要一次比较，而额外的代价就是 1 数组移动操作；

在堆排序中，最差的情况是插入时上浮到顶，然后弹出时又下沉到树叶，而每次上浮或下沉最多2次比较，所以最多需要 $4\log_{2} {k}$ 次比较，以及 $2\log_{2} {k}$ 次交换操作

在快速排序则直接取决于给定数组的初始顺序，有点运气成份，不过其比较次数应该与插入排序相差不大，但是需要更多的交换次数；

另外，快速排序的优势是可以原地排序，而不需要借助额外空间，所以它比较适合对一下子给定所有数据的排序，而对于持续的大量的输入，利用插入排序或堆排序则比较合适。

参考：

《算法》