文档章节

海量数据处理之top K问题

o
 osc_x4h57ch8
发布于 2018/04/24 09:53
字数 1454
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目:
CVTE笔试题 https://www.1024do.com/?p=3949
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。
假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的10个查询串,要求使用的内存不能超过1G。
 
思路:此题解题步骤可分为两步: 1.统计每个“查询串”(下称为query)出现的次数  2.根据统计结果,找出top 10
 
1.统计query出现次数:
利用hash思想,维护一个Key为Query字串,Value为该Query出现次数的HashTable。每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。
因为hashtable中查询速度非常快,几乎达到O(1)的时间复杂度,所以统计N个记录,时间复杂度能达到O(N),线性的时间复杂度
 
2.根据统计结果,找出topK
借助堆结构,我们可以在log量级的时间内查找和调整/移动。‘
具体做法:维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比。(这道题目因为是找“最大”的10个,所以用小根堆,每次遍历的元素只要和堆中最小的元素——“根”作比较,如果小于根,说明肯定进不了topK;如果大于根,说明它可以淘汰堆中的最小的一个元素,也就是根,然后再调整)
 
堆中最后剩下的K个元素就是top K
 
TOP   K问题

Top k问题的讨论(三种方法的java实现及适用范围)

在很多的笔试和面试中,喜欢考察Top K.下面从自身的经验给出三种实现方式及实用范围。

  1. 合并法

    这种方法适用于几个数组有序的情况,来求Top k。时间复杂度为O(k*m)。(m:为数组的个数).具体实现如下:

复制代码
/**
* 已知几个递减有序的m个数组,求这几个数据前k大的数
*适合采用Merge的方法,时间复杂度(O(k*m);
*/
import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
public class TopKByMerge{
 public int[] getTopK(List<List<Integer>>input,int k){
    int index[]=new int[input.size()];//保存每个数组下标扫描的位置;
    int result[]=new int[k];
    for(int i=0;i<k;i++){
       int max=Integer.MIN_VALUE;
       int maxIndex=0;
       for(int j=0;j<input.size();j++){
           if(index[j]<input.get(j).size()){
                if(max<input.get(j).get(index[j])){
                    max=input.get(j).get(index[j]);
                    maxIndex=j;
                }
           }
       }
       if(max==Integer.MIN_VALUE){
           return result;
       }
       result[i]=max;
       index[maxIndex]+=1;
       
    }
    return result;
 }
复制代码
  1.  快排过程法

    快排过程法利用快速排序的过程来求Top k.平均时间复杂度为(O(n)).适用于无序单个数组。具体java实现如下:

Quick Select的目标是找出第k大元素,所以

选取一个基准元素pivot,将数组切分(partition)为两个子数组,

  • 若切分后的左子数组的长度 > k,则第k大元素必出现在左子数组中;
  • 若切分后的左子数组的长度 = k-1,则第k大元素为pivot;
  • 若上述两个条件均不满足,则第k大元素必出现在右子数组中。
复制代码
/*
*利用快速排序的过程来求最小的k个数
*
*/
public class TopK{
   int partion(int a[],int first,int end){
        int i=first;
        int main=a[end];
        for(int j=first;j<end;j++){
             if(a[j]<main){
                int temp=a[j];
                a[j]=a[i];
                a[i]=temp;
                i++;
             }
        }
        a[end]=a[i];
        a[i]=main;
        return i;    
   }
   void getTopKMinBySort(int a[],int first,int end,int k){
      if(first<end){
          int partionIndex=partion(a,first,end);
          if(partionIndex==k-1)return;
          else if(partionIndex>k-1)getTopKMinBySort(a,first,partionIndex-1,k);
          else getTopKMinBySort(a,partionIndex+1,end,k);
      }
   }
public static void main(String []args){
      int a[]={2,20,3,7,9,1,17,18,0,4};
      int k=6;
      new TopK().getTopKMinBySort(a,0,a.length-1,k);
      for(int i=0;i<k;i++){
         System.out.print(a[i]+" ");
      }
   }
}
复制代码
  1. 采用小根堆或者大根堆

   求最大K个采用小根堆,而求最小K个采用大根堆。

  求最大K个的步奏:

  1.     根据数据前K个建立K个节点的小根堆。
  2.     在后面的N-K的数据的扫描中,
  • 如果数据大于小根堆的根节点,则根节点的值覆为该数据,并调节节点至小根堆。
  • 如果数据小于或等于小根堆的根节点,小根堆无变化。

 求最小K个跟这求最大K个类似。时间复杂度O(nlogK)(n:数据的长度),特别适用于大数据的求Top K。

复制代码
/**
 * 求前面的最大K个 解决方案:小根堆 (数据量比较大(特别是大到内存不可以容纳)时,偏向于采用堆)
 * 
 * 
 */
public class TopK {
    /**
     * 创建k个节点的小根堆
     * 
     * @param a
     * @param k
     * @return
     */
    int[] createHeap(int a[], int k) {
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = a[i];
        }
        for (int i = 1; i < k; i++) {
            int child = i;
            int parent = (i - 1) / 2;
            int temp = a[i];
            while (parent >= 0 &&child!=0&& result[parent] >temp) {
                result[child] = result[parent];
                child = parent;
                parent = (parent - 1) / 2;
            }
            result[child] = temp;
        }
        return result;

    }

    void insert(int a[], int value) {
         a[0]=value;
         int parent=0;
         
         while(parent<a.length){
             int lchild=2*parent+1;
             int rchild=2*parent+2;
             int minIndex=parent;
             if(lchild<a.length&&a[parent]>a[lchild]){
                 minIndex=lchild;
             }
             if(rchild<a.length&&a[minIndex]>a[rchild]){
                 minIndex=rchild;
             }
             if(minIndex==parent){
                 break;
             }else{
                 int temp=a[parent];
                 a[parent]=a[minIndex];
                 a[minIndex]=temp;
                 parent=minIndex;
             }
         }
         
    }

    int[] getTopKByHeap(int input[], int k) {
        int heap[] = this.createHeap(input, k);
        for(int i=k;i<input.length;i++){
            if(input[i]>heap[0]){
                this.insert(heap, input[i]);
            }
        
            
        }
        return heap;

    }

    public static void main(String[] args) {
        int a[] = { 4, 3, 5, 1, 2,8,9,10};
        int result[] = new TopK().getTopKByHeap(a, 3);
        for (int temp : result) {
            System.out.println(temp);
        }
    }
}
复制代码
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

2020最新微信域名防封技术 微信域名防封系统是如何操作的

相信很多朋友在运营自己产品的网站或者是推广链接的时候,经常会发现运行的好好的网站链接突然就被封了,有一部分因为可能是网站的内容触犯了微信的规则,但是还有很大的一部分被同行恶意投诉...

戚馨逸
26分钟前
11
0
mysql 为什么 SQL 语句不要过多的 join?

第一部分 Linux上查看内存的使用情况该用什么命令 free -mh 可以看到内存或者缓存情况 total 总内存 used 已用内存 free 空闲内存 buff/cache 已使用的缓存 avaiable 可用内存 怎么清理已使...

edison_kwok
27分钟前
17
0
芒果TV的金融野心从未停止

来源|WEMONEY研究室 作者|林小林 芒果TV是真的会讲故事,《乘风破浪的姐姐》不仅是生活的故事更是资本的故事,30位姐姐让一款节目累计播放量飙升10亿,同时让背后的上市公司芒果超媒市值站...

镭射财经
38分钟前
4
0
找到的程序集的清单定义与程序集引用不匹配

问题: I am trying to run some unit tests in a C# Windows Forms application (Visual Studio 2005), and I get the following error: 我试图在C#Windows窗体应用程序(Visual Studio 2......

法国红酒甜
40分钟前
16
0
渗透测试的概念和实战

目录 1. 前言 2. 常见web安全漏洞 3. 思路 3.1渗透测试思路 3.2黑客攻击思路 4. 暴力破解 4.1谷歌黑语法 4.1.1 黑语法inurl:搜索url包含指定字符串 4.1.2 黑语法intitle:搜索网页中的标题名...

六道木
55分钟前
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部