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 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-633-Sum of Square Numbers

1452
来自专栏数说工作室

【SAS Says】基础篇:5. 开发数据(一)

本节目录: 开发数据 5.1 创建并重新定义变量 5.2 使用SAS函数 5.3 使用IF-THEN语句 5.4 用IF-THEN语句将观测值分组 5.5 构造...

3264
来自专栏TensorFlow从0到N

讨厌算法的程序员 1 - 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生...

3434
来自专栏人工智能LeadAI

讨厌算法的程序员 1 | 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生出一...

3017
来自专栏ml

向前字典排序

          next_permutation算法对区间元素进行一次组合排序,使之字典顺序大于原来的排序,有如下两个使用原形,对迭代器区间[first,l...

2749
来自专栏ACM算法日常

独角兽与数列(置换群循环)- HDU 4985

群论是法国数学家伽罗瓦(Galois)的发明。伽罗瓦是一个极具传奇性的人物,年仅21岁就英年早逝于一场近乎自杀的决斗中。他用该理论,具体来说是伽罗瓦群,解决了五...

863
来自专栏TensorFlow从0到N

讨厌算法的程序员 5 - 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦...

3515
来自专栏aCloudDeveloper

LeetCode:5_Longest Palindromic Substring | 最长的回文子串 | Medium

题目: Given a string S, find the longest palindromic substring in S. You may assum...

22810
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

2062
来自专栏前端说吧

JS-用js的for循环实现九九乘法表以及其他算数题等

5186

扫码关注云+社区

领取腾讯云代金券