top K 问题

  在海量数据中找出出现频率最高的前K个数,或者从海量数据中找出最大的前K个数,这类问题被称为top K问题,例如搜索引擎中,同济最热门的10个查询词,在歌曲库中统计下载量频率最高的前10个数据。

  针对这类问题,通常比较好的方案是分治+Trie树/hash+小顶堆,即将数据集按照hash方法分解成多个小数据集,然后使用Trie树或者hash统计每个小数据集中的query词频,之后用小顶堆求出每个数据集中出现频率最高的前K个数,最后在所有的top K中求出最终的top K。

  例如,1亿个浮点数,如何找出最大的10000个?

1.快速排序

最容易想到的方法是将数据全部排序,然后在排序后的集合中进行查找,最快的排序算法的时间复杂度一般为O(nlogn),如快速排序。但是在32位的机器上,每个float类型占4个字节,1亿个浮点数就要占用400MB的存储空间,对于一些可用内存小于400M的计算机而言,很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求,该方法也并不高效,因为题目的目的是寻找出最大的10000个数即可,而排序却是将所有的元素都排序了,做了很多的无用功。

2.局部淘汰法

  该方法与排序方法类似,用一个容器保存前10000个数,然后将剩余的所有数字——与容器内的最小数字相比,如果所有后续的元素都比容器内的10000个数还小,那么容器内这个10000个数就是最大10000个数。如果某一后续元素比容器内最小数字大,则删掉容器内最小元素,并将该元素插入容器,最后遍历完这1亿个数,得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O(n+m*m),其中m为容器的大小,即10000。

3.分治法

将1亿个数据分为100份,每一份包含100万个数据,找出每份数据中最大的10000个,最后在剩下的100*10000个数据中找出最大的10000个。如果100万数据选取的足够理想,那么可以过来掉99%的数据。

  100万个数据中找出最大的10000个,继续对大堆快速排序一次分成两堆,如果大堆个数N大于10000,继续对大堆快排一次分成两堆,如果大堆的个数N小于10000,就在小的那堆里快速排序一次,找到第10000-n大的数字,递归进行上述的过程,就可以找到第10000大的数字。这种方法每次需要的内存空间是100万*4 = 4M,一共需要101次比较。

4.hash法

如果1亿个数里面有很多重复的数,先通过hash法,把这1亿个数字去重复,如果重复率高的话,会减少很大的内存用量,从而缩小运算空间,然后通过分治或者最小堆法进行。

5.最小堆

先读入前10000个数来创建大小为10000的小顶堆,建堆的时间复杂度为O(mlogm)(m是数组的大小,即为10000),然后遍历后续的数字,并与堆顶(堆顶的数值最小)进行比较,如果比堆顶小,则继续读取后续的数字,如果比堆顶大,则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿的数全部变量完为止,然后按照中序遍历的方式输出当前堆中所有10000个数字,该算法的时间复杂度为O(nmlogm),空间复杂度是10000。

重复问题

使用位图法对8位电话号码进行统计和排序。

package _9_3;

import java.util.Random;

public class Test
{
	int ARRNUM = 10000;
	int mmin = 10000000;
	int mmax = 99999999;
	int N = mmax - mmin + 1;
	int BITS_PER_WORD = 32;
	
	//找出放在第几个bit
	int WORD_OFFSET(int b)
	{
		return b/BITS_PER_WORD;
	}
	
	//计算出应该存在第几位
	int BIT_OFFSET(int b)
	{
		return b%BITS_PER_WORD;
	}
	
	//置为1
	void SetBit(int[] words, int n)
	{
		n -= mmin;
		words[WORD_OFFSET(n)] |= (1<<BIT_OFFSET(n));
	}
	
	//清零
	void ClearBit(int[] words, int n)
	{
		words[WORD_OFFSET(n)] &= ~(1<<BIT_OFFSET(n));
	}
	
	//获得对应的值
	boolean GetBit(int[] words, int n)
	{
		int bit = words[WORD_OFFSET(n)]&(1<<BIT_OFFSET(n));
		return bit != 0;
	}
	
	public void sort()
	{
		int i,j;
		int arr[] = new int[ARRNUM];
		System.out.println("数组大小:" + ARRNUM);
		//用来存放位图,每一位对应mmin到mmax范围内的一个数
		int[] words = new int[1 + N/BITS_PER_WORD];
		int count = 0;
		Random r = new Random();
		
		//生成100个随机数存放在数组arr中
		for(j = 0; j < ARRNUM; j++)
		{
			arr[j] = r.nextInt(N);
			arr[j] += mmin;
			System.out.println(arr[j] + " ");
		}
		System.out.println();
		
		for(j = 0; j < ARRNUM; j++)
		{
			SetBit(words, arr[j]);
		}
		System.out.println("排序后的a为:");
		
		for(i = 0; i < N; i++)
		{
			if(GetBit(words, i))
			{
				System.out.println(i + mmin + " ");
				count++;
			}
		}
		System.out.println();
		System.out.println("总个数为:" + count);
	}

	public static void main(String[] args)
	{
		new Test().sort();
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • dubbo源码分析1——负载均衡

    Mister24
  • dubbo源码分析1——负载均衡

    Mister24
  • unix网络编程——I/O多路复用之epoll

      当程序进行IO时,如果数据尚未准备好,那么IO将处于阻塞状态。当某个进程有多个打开的文件,比如socket,那么其后的所有准备好读写的文件将受到阻塞的影响而...

    Mister24
  • loj#2542. 「PKUWC2018」随机游走(MinMax容斥 期望dp)

    设\(f[i][sta]\)表示从\(i\)到集合\(sta\)中任意一点的最小期望步数

    attack
  • 带分数 第四届蓝桥杯省赛C++B组

    输入样例1: 100 输出样例1: 11 输入样例2: 105 输出样例2: 6

    dejavu1zz
  • 洛谷P3248 [HNOI2016]树(主席树 倍增 )

    attack
  • 2007北京市小学生程序设计友谊赛详细答案

    注意:网络上有些人说round()不是四舍五入,而是四舍六入五成双,即round(5.5) = 6, round(6.5) = 6。 我通过在Dev C++, ...

    海天一树
  • 洛谷P4781 【模板】拉格朗日插值(拉格朗日插值)

    \[f(x) = \sum_{i = 1}^n y_i \prod_{j \not = i} \frac{k - x[j]}{x[i] - x[j]}\]

    attack
  • java基础知识01

    正所谓万丈高楼平地起,有了扎实的基础才能进阶更深奥的课程,才能让你后面的走得更轻松,学Java亦是如此!所以千万不能忽略基础的重要性,下面一起来温习一下那些容易...

    贪挽懒月
  • BZOJ3624: [Apio2008]免费道路(最小生成树)

    这棵树上有一些0边是必须要选的,我们先把他们找出来,如果数量$\geqslant k$显然无解

    attack

扫码关注云+社区

领取腾讯云代金券