关于Top K问题的勘误讨论

冷不防 2022-07-30 19:53 138阅读 0赞

在网上查找了许多Top K算法的问题，发现了几个问题：首先，不管具体实现方式是二叉堆还是快速排序或者别的，其实没有Top K这个算法。在大量数据中求前几位最值问题其实有很多解法，没有一个具体的固定最优算法，网络上所谓的Top K算法，或者是优先队列在实际中的简单应用，或者是别的算法结合。

其次，关于Java的Top K算法的具体实现，网上似乎资料都比较接近，讲解并不全面。这里讨论利用二叉堆的实现方式。

本文考虑找出前k个最大值问题（最小值同理）。

利用二叉堆的性质，很容易的能想到两种实现方式。（后文涉及堆排序，二叉堆的知识，阅读后文请在掌握以上基础之后进行。本文参考清华大学严蔚敏的《数据结构c语言版》，和Mark Allen Weiss的《Data Structures and Algorithm Analysis in Java》）

第一种（后称A）：输入大量的N个源数据每一个值的同时，将这个值插入二叉堆中，输入完成后，二叉堆也构建完成。然后依次进行k次选取二叉堆的根节点，就能得到N中k个值。时间复杂度计算：首先构造含有N个节点的堆平均耗时：O(N)，之后取出k个最大值耗时：k\*O(logN)，该算法的时间复杂度为：O(N+k\*logN)。这个算法适合N较大的情形（本文推荐这种算法）。

第二种（后称B）：先输入前k个值（不管大小），构建一个只含有k个节点的二叉堆。之后在输入剩下N-k个值的同时判断这个新输入的值是否比在二叉堆中的最小值大，如果大，那么将原二叉堆中的较小值替换掉。输入完成后，也就得到了一个只含有N中最大的k个值的堆。时间复杂度计算：构建含有k个节点的堆耗时：O(k)，处理其余每个元素的时间为：O(1)，在必要时需要用新元素更换原堆中的小值，每个替换耗时：O(logk)，因此这个算法的最差时间复杂度（就是说整个输入呈升序，每一个都要替换）：O(k+(N-k)\*logk)。这个算法适合k较大的情形。这个B算法也是网上大量资料提供的算法（后文将分析其缺点）。

从实用性考虑：虽然从理论上说，A算法适用于N较大的情形，B算法适用于k较大的情形，但是实际情况往往是：k总是小于N（一般运用这种算法的情况都是在大量源数据N中查找有限的前k个值。几乎不会碰到在很少的源数据N中查找相对较多的前k个数据，这也没有意义），因此实际情况中几乎永远也不会出现适合算法B的情况。

从时间复杂度的考虑：关于二叉堆的构建，业已证明，平均每次插入需要进行2.607次比较，也就是每次insert方法将元素上移1.607层。因此对于A算法的时间复杂度分析是从“平均”的角度出发的。而对于B算法的时间复杂度，则是从最差情况来分析的。因此尽管从理论上A算法的时间复杂度确实要比B算法的时间复杂度更快，但是由于两者考虑的情形不同，因此严格来说无法比较。既然理论分析参考价值不大，那么我们进行实际测试。下面是我的测试结果。

在Java环境下，写好一个独立的类来代表二叉堆结构，在这个类中完成所有方法的提供。然后编写两个测试类（在代码上尽量保证两个算法的测试情况公平），利用组合模式来调用二叉堆的各项操作。输入数据通过随机数生成(Math.random()\*10000000)。在我的电脑上（注意如果要自己做测试的话一定要考虑编译器优化，第一遍运行会加上编译时间，前几次的测试会明显耗时多于后几次的测试）：

生成五次一千个数据，让A和B算法对每一次生成数据进行一千次排序，也就是A、B各测试5000次。A构建堆的平均时间为5000纳秒，B构建堆的平均时间为7000纳秒，B比A性能上损耗40%。两个算法不管用多大的数据量测试，提取前k（此处k取10）项耗时基本相同，看似A算法取每一个最大值都需要遍历到堆底部，有一定的开销，但是由于其堆序性的保证，其提取时间可以保证为logn，所以真正运行时耗时不大。

生成五次一万个数据，B算法的耗时比A在多出50%。

生成五次十万个数据，测试结果同上。

由此可见，不论是理论讨论，还是实际情况，A算法都明显优于B算法。网络上的参考资料或多或少都没有考虑全面，在此补充。

贴一下测试代码吧。

package com.yhk.test;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.util.ArrayList;
    
    import com.yhk.filewriter.MyReader;
    import com.yhk.sort.BinaryHeap;
    
    public class BinaryHeapTest {
    	String path="e:\\topk_qian.txt";
    	int num=1000;
    	MyReader myReader=new MyReader(path);
    	BufferedReader mReader=myReader.getReader();
    	
    	private void topkA(){
    		BinaryHeap<Integer> bh=new BinaryHeap<Integer>();
    		String value;
    		long total=0;
    		long build=0;
    		
    		for(int i=0;i<1000;i++){
    			long start=System.nanoTime();
    			try {
    				mReader.readLine();
    				while((value=mReader.readLine()) != null) {
    					Integer u=Integer.parseInt(value);
    					bh.insert(u);
    				}
    			} catch (IOException e) {
    				e.printStackTrace();
    			}
    			long mid=System.nanoTime();
    			for(int j=0;j<10;j++){
    				bh.deleteMax();
    			}
    			long end=System.nanoTime();
    			build+=mid-start;
    			total+=end-start;
    		}
    		
    		System.out.println("A:"+build/1000);
    		System.out.println("A:"+(total-build)/1000);
    	}
    	
    	private void topkB(){
    		BinaryHeap<Integer> bh=new BinaryHeap<Integer>();
    		String value;
    		long total=0;
    		long build=0;
    		
    		for(int i=0;i<1000;i++){
    			long start=System.nanoTime();
    			try {
    				mReader.readLine();
    				for(int j=0;j<10;j++){
    					if((value=mReader.readLine())!=null){
    						Integer u=Integer.parseInt(value);
    						bh.insert(u);
    					}else{
    						break;
    					}
    				}
    				while((value=mReader.readLine()) != null) {
    					Integer u=Integer.parseInt(value);
    					if(u.compareTo(bh.findMin())>0){
    						bh.deleteEnd();
    						bh.insert(u);
    					}
    				}
    			} catch (IOException e) {
    				e.printStackTrace();
    			}
    			long mid=System.nanoTime();
    			for(int j=0;j<10;j++){
    				bh.deleteMax();
    			}
    			long end=System.nanoTime();
    			build+=mid-start;
    			total+=end-start;
    		}
    		
    		System.out.println("B:"+build/1000);
    		System.out.println("B:"+(total-build)/1000);
    	}
    }

相关代码地址（该内容提供了相关内容的Java代码实现）：https://github.com/bigbird231/Sort