TopK算法性能对比

jiezi

5 年前

从 arr[1, n] 这 n 个数中，找出最大的 k 个数，这就是经典的 TopK 问题。笔者将使用冒泡算法和小顶堆实现 TopK，对比其时间复杂度。

不需要将数据全部排序，只用排 k 轮即可。

import java.util.Arrays;


// topK 冒泡法 效率 O(kn)
public class TopKBubble {public static int[] topK(int[] arr, int k) {for (int i = 0; i < k; i++)
            for (int j = 0; j < arr.length - 1 - i; j++)
                if (arr[j] > arr[j + 1])
                    swap(arr, j, j + 1);

        return Arrays.copyOfRange(arr, arr.length - k, arr.length);
    }
    
    public static void swap(int[] arr, int index1, int index2) {arr[index1] = arr[index2] ^ arr[index1];
        arr[index2] = arr[index2] ^ arr[index1];
        arr[index1] = arr[index2] ^ arr[index1];
    }
}

可见时间复杂度 O(k*n)

堆：一种数据结构，有最大堆和最小堆两种类型，实质上是一个完全二叉树，如果是最大堆，则父节点上的值比子节点上的值大，反之则是最小堆。而堆排序是一种比较高效的排序方式，时间效率为 N *lgN，它利用最大堆的特性完成排序。

import java.util.Arrays;


//topK 最小堆实现方式 效率 O((n-k)log2(k) )
public class TopKHeap {public static int[] topK(int[] arr, int k) {buildHeap(arr, k);

        for (int i = k; i < arr.length; i++)
            if (arr[0] < arr[i]) {arr[0] = arr[i];
                buildHeap(arr, k);
            }

        return Arrays.copyOfRange(arr, 0, k);
    }

    public static void buildHeap(int[] arr, int size) {for (int i = size - 1; i >= 0; i--)
            reBuildHeap(arr, i, size);
    }

    public static void reBuildHeap(int[] arr, int key, int size) {int leftChild = (key << 1) + 1;
        int rightChild = (key << 1) + 2;
        int small = key;

        if (leftChild < size && arr[leftChild] < arr[small])
            small = leftChild;

        if (rightChild < size && arr[rightChild] < arr[small])
            small = rightChild;

        if (small != key) {swap(arr, small, key);
            reBuildHeap(arr, small, size);
        }
    }

    public static void swap(int[] arr, int index1, int index2) {arr[index1] = arr[index2] ^ arr[index1];
        arr[index2] = arr[index2] ^ arr[index1];
        arr[index1] = arr[index2] ^ arr[index1];
    }
}

时间复杂度（N-k）*logN

public static void main(String[] args) {for(int i=1;i<9;i++){int nums=(int)Math.pow(10,i);
            System.out.println("数据规模:"+nums);

            int[] test1=new int[nums];

            for(int j=0;j<test1.length;j++)
                test1[j]=(int)(Math.random()*test1.length);

            int[] test2= Arrays.copyOfRange(test1,0,test1.length);

            Long time1=System.currentTimeMillis();
            TopKBubble.topK(test1, 5);
            System.out.println("\n 冒泡法用时"+(System.currentTimeMillis()-time1)+"毫秒");

            time1=System.currentTimeMillis();
            TopKHeap.topK(test2, 5);
            System.out.println("小顶堆用时"+(System.currentTimeMillis()-time1)+"毫秒");
            System.out.println("-------------------");
        }

    }

//output

//output

数据规模: 10

冒泡法用时 0 毫秒
小顶堆用时 0 毫秒
-------------------
数据规模: 100

冒泡法用时 0 毫秒
小顶堆用时 0 毫秒
-------------------
数据规模: 1000

冒泡法用时 0 毫秒
小顶堆用时 0 毫秒
-------------------
数据规模: 10000

冒泡法用时 0 毫秒
小顶堆用时 0 毫秒
-------------------
数据规模: 100000

冒泡法用时 15 毫秒
小顶堆用时 16 毫秒
-------------------
数据规模: 1000000

冒泡法用时 16 毫秒
小顶堆用时 0 毫秒
-------------------
数据规模: 10000000

冒泡法用时 141 毫秒
小顶堆用时 31 毫秒
-------------------
数据规模: 100000000

冒泡法用时 1355 毫秒
小顶堆用时 83 毫秒
-------------------

原理参照：传送门

TopK算法性能对比

TopK 算法性能对比

冒泡算法实现

小顶堆实现

测试