k top 大数据_大数据top k - CSDN
  • 大数据Top K问题

    2018-03-21 11:29:35
    大数据的套路就是分治,将大问题分解为若干个小问题, 计算小问题后并合并结果。

    大数据下的2个Top K场景:

    1、 1亿个数字中找出最大或最小的前100个数字(考虑判重和内存空间限制)?

    思路: 考虑将数字分散存储在不同文件中, 然后依次读取各个文件, 例如1~10000存到1.txt、 2~20000存到2.tx、以此类推;

            如果不判重,可以将前100个数字做成最大堆或最小堆的数据结构(找最大的Top100用最小堆, 找最小的Top100用最大堆), 然后依次遍历所有数字, 符合条件时替换根节点后并重新构建堆。堆的缺点是允许有重复数字!!!

            如果要判重,则创建一个100个空间的空数组, 遍历1亿个数字依次插入值(按照升序), 使用二分查找算法判断新值在数组中的位置并插入, 该数组最多容纳100个值。 当有101个值时先判重, 如果重复继续向后遍历, 如果值大于数组最小值则插入到指定位置,数组第一个元素移出数组, 因为数组是连续的,所有可以用内存拷贝方式赋值,只有新插入的值要单独赋值到对应的下标(原理类似于android.util.SparseArray)。   因内存拷贝可认为不占用时间, 该思路的总会时间复杂度是O(1亿*log100), log100是二分查找的复杂度。

      

    2、 1亿个搜索关键词找出次数最多的前100个搜索词(考虑内存空间限制)? 

    思路: 核心是“分治”、“归并”和哈希,  第一次遍历将关键词散列到不同的文件中(散列算法是性能关键,哈希函数的性能直接影响散列的结果, 尽量避免数据倾斜), 同一个关键词一定会散列到同一个文件, 理想情况是所有关键词均匀散列到不同的文件中(即分治思想,将大文件分解为小问题)。

           读取每个文件并记录各关键词的次数, 做个冒泡排序, 从每个文件中排序出前100的关键词;

           取第一个文件的记录结果, 和第二个文件做合并, 即200个结果中排序出前100个关键词, 然后依次合并第三个、第四个。。。。第N个文件(将子结果合并为总结果)。


    PS:   大道同源, 我想到2个类似的场景。

    1、 电脑里有众多的文件,但我们还是能从众多文件中找到你想要的。 这是为什么呢?  因为使用了文件夹, 按照文件类型保存在各个层级的目录里。 这个目录层级跟”在1亿个搜索词中找出频率最高的100个“的解决思路是一样的, 即将关键词分散存储到不同的文件里(也可以使用层级目录, 目录越深分散的粒度越细, 到底分几个文件/目录层级其实是时间空间的权衡)

    2、 数据库用户表里要存储几亿个记录,该怎么办? 跟上面管理电脑文件的问题类似, 可以按地域、年龄、姓名等等因素将数据存储到N张表里, 术语叫做”横向切割“


    名词解释:

    1、”数据倾斜“是大数据里的一个概念,就是数据集中到几个文件、处理器, 没均匀分散到各个处理单元。说白了就是忙的忙死,闲的闲死。

    2、”分治“就是将大问题分解为小问题, 处理每个小问题并得到结果, 然后将所有子结果汇总成最终结果。

    3、”横向切割“是数据库的一个概念, 就是将表记录分散存储到不同的表里,每个表里的记录都是完整的。 还有个“纵向切割”,就是将分拆表的列为多个表, 即一条记录要存到多张表里且每个表只存几个属性。 

    4、“哈希”即散列, 就是通过哈希值找到存储位置, 理想情况下时间复杂度O(1)。 


    下面开撸堆排序算法和代码:

           堆是个完全二叉树, 节点先从上到下后从左到右都是满的, 说白了叶子节点可以不满且非叶节点都有。 用Java数组形容的话, 数组下标从0到N-1。 如果节点i有左子树,那么左子树的下标是2i+1;如果节点i有右子树,那么右子树的下标是2i+2;如果有父节点,对应下标是(i-1)/2取整。

           堆分为最大堆和最小堆,也可以叫大根堆和小根堆; 最大堆的定义是任意子树根节点大于或等于子节点,所以根节点是最大值; 最小堆的定义是任意子树根节点小于或等于子节点, 所以根节点是最小值。

           堆排序思想是先构造堆,然后做N次循环, 每次交互根节点和最后一个值(最后节点是递减的)重新构建堆。

           构造堆是堆排序的核心, 算法是从最后一个非叶节点(即N/2)开始,先从右到左后从下到上依次判断交换值。详见堆排序动画: http://www.benfrederickson.com/heap-visualization/


     使用最小堆找出最大的前10个数字:

     //得到最大的前length个数字, 使用最小堆数据结果,理论上可能有重复数字
        public static void topNums(final int length)throws Exception{
            Scanner scanner=new Scanner(new FileInputStream("input.txt"));
    
            long array[]=new long[length];
            for(int i=0; i<array.length; i++){
                array[i]=scanner.nextLong();
            }
    
            buildMinHeap(array); //构造小顶堆
    
            while (scanner.hasNextLong()){
                long value = scanner.nextLong();
    
                if(value < array[0]) {
                    continue;   //根节点是数组最小值, 如果当前值比最小值还小就跳过
                }
    
                array[0] = value;   //丢掉根节点,即替换array[0]
                ajustHeap(array, length,0);  //重新构造小根堆
            }
    
            //将一个小根堆进行排序,用堆排序思想
            heapSort(array);
    
            for(int i=0; i<length; i++)
                System.out.println(array[i]);
    
            scanner.close();
        }
    
    
    
        public static void main(String[]args)throws Exception{
            randomData();  //生成随机数并保持到文件里
            long start=System.currentTimeMillis();
            topNums(10);   //从文件中找出最大的前10个数字
            long end=System.currentTimeMillis();
            System.out.println(end-start);
    
    
            //验证堆排序是否正确的测试数据
            long[] array = {1, 3, -1, -5, 5, 10, 20, -10, 100, 30, 11, 16};
            System.out.println("原始数组:");
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
            heapSort(array);
            System.out.println("排序后:");
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
    
        }
    
        //得到从大到小的降序
        public static void heapSort(long[] array) {
            if (array == null || array.length <= 1) {
                return;
            }
    
            buildMinHeap(array);  //构造堆
    
            for (int i = array.length - 1; i >= 1; i--) {
                long temp = array[i];
                array[i] = array[0];
                array[0] = temp;
    
                ajustHeap(array, i, 0);  //重新调整第0个下标节点
            }
        }
    
        //构造小根堆
        private static void buildMinHeap(long[] array) {
            if (array == null || array.length <= 1) {
                return;
            }
    
            int half = array.length / 2;
            for (int i = half; i >= 0; i--) {
                ajustHeap(array, array.length, i);
            }
        }
    
        //构造小顶堆, 按照分治的思想递归
        private static void ajustHeap(long[] array, int heapSize, int index) {
            int left = index * 2 + 1;
            int right = index * 2 + 2;
    
            int smallest = index;
            if (left < heapSize && array[left] < array[index]) {
                smallest = left;
            }
    
            if (right < heapSize && array[right] < array[smallest]) {
                smallest = right;
            }
    
            if (index != smallest) {
                long temp = array[smallest];
                array[smallest] = array[index];
                array[index] = temp;
    
                ajustHeap(array, heapSize, smallest);
            }
        }
    
        //随机生成100000个数字并保存到文件里
        public static void randomData()throws Exception{//随机100万数据
    
            File file=new File("input.txt");
            if(!file.exists())
                file.createNewFile();
    
            PrintStream printStream=new PrintStream(new FileOutputStream(file));
    
            Random random=new Random(System.currentTimeMillis());
    
            for(int i=0;i<1000000;i++){
                long k=Math.abs(random.nextLong());
                printStream.println(k);
                //printStream.println(k);  //连续写2个相同值, 验证使用堆得到的top k结果有重复数字
            }
            printStream.close();
        }

           其中adjustHeap函数是核心函数, 思想是找出当前节点、左子节点、右子节点的最大或最小值, 如果当前节点已经是最大或最小则退出, 否则交换当前节点和子节点的值,然后递归处理子节点, 这是“分治法“的体现。

    构造堆结果也可以使用非递归的方式实现:

        //构造最大堆的非递归实现
        public void adjustHeapExt(long[] array, int parent, int length) {
            long temp = array[parent];
            int child = 2 * parent + 1;  //左子节点
    
            while (child < length) {
                if (child + 1 < length && array[child] < array[child + 1]) {
                    child++;   //右子节点比左子节点更大
                }
                
                if (temp >= array[child]) {
                    break;  //当前节点最大则退出
                }
                
                array[parent] = array[child];  //替换根节点的值
                
                parent = child;  //向下遍历
                child = 2 * child + 1;  //从左子节点开始比较
            }
            array[parent] = temp;   //存储原根节点值
        }

      补充一下: 1亿个数字找出top 100的二分查找原理, 对于有序数组先比较array[0], 然后二分查找并数组前移、后移加上赋值。  


    摘自SparsArray.java

     /**
         * 二分查找数据中是否存在值
         * @param array,数组,升序数组
         * @param value,要查找的值
         * @return  找到就返回数组下标, 找不到就返回负数(需要插入的位置)
         */
        static int binarySearch(long[] array, long value) {
            int lo = 0;
            int hi = array.length - 1;
    
            while (lo <= hi) {
                final int mid = (lo + hi) >>> 1;
                final long midVal = array[mid];
    
                if (midVal < value) {
                    lo = mid + 1;
                } else if (midVal > value) {
                    hi = mid - 1;
                } else {
                    return mid;  // value found
                }
            }
            return ~lo;  // value not present
        }

         小结, 对于大数据第一步是要"分治”,  “分治”算法是影响性能的关键。

    展开全文
  • 大数据下的TOPK问题

    2018-08-20 22:49:38
    top K问题  在大规模数据处理中,经常会遇到的一类问题:在海量数据中找出出现频率最好的前k个数,或者从海量数据中找出最大的前k个数,这类问题通常被称为top K问题。例如,在搜索引擎中,统计搜索最热门的10个...

    top K问题

            在大规模数据处理中,经常会遇到的一类问题:在海量数据中找出出现频率最好的前k个数,或者从海量数据中找出最大的前k个数,这类问题通常被称为top K问题。例如,在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载最高的前10首歌等。

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

    eg:有1亿个浮点数,如果找出期中最大的10000个?

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

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

            第三种方法是分治法,将1亿个数据分成100份,每份100万个数据,找到每份数据中最大的10000个,最后在剩下的100*10000个数据里面找出最大的10000个。如果100万数据选择足够理想,那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下:用快速排序的方法,将数据分为2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大堆个数N小于10000个,就在小的那堆里面快速排序一次,找第10000-n大的数字;递归以上过程,就可以找到第1w大的数。参考上面的找出第1w大数字,就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^6*4=4MB,一共需要101次这样的比较。

            第四种方法是Hash法。如果这1亿个书里面有很多重复的数,先通过Hash法,把这1亿个数字去重复,这样如果重复率很高的话,会减少很大的内存用量,从而缩小运算空间,然后通过分治法或最小堆法查找最大的10000个数。

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

    实际运行:

            实际上,最优的解决方案应该是最符合实际设计需求的方案,在时间应用中,可能有足够大的内存,那么直接将数据扔到内存中一次性处理即可,也可能机器有多个核,这样可以采用多线程处理整个数据集。

           下面针对不容的应用场景,分析了适合相应应用场景的解决方案。

    (1)单机+单核+足够大内存

            如果需要查找10亿个查询次(每个占8B)中出现频率最高的10个,考虑到每个查询词占8B,则10亿个查询次所需的内存大约是10^9 * 8B=8GB内存。如果有这么大内存,直接在内存中对查询次进行排序,顺序遍历找出10个出现频率最大的即可。这种方法简单快速,使用。然后,也可以先用HashMap求出每个词出现的频率,然后求出频率最大的10个词。

    (2)单机+多核+足够大内存

            这时可以直接在内存总使用Hash方法将数据划分成n个partition,每个partition交给一个线程处理,线程的处理逻辑同(1)类似,最后一个线程将结果归并。

            该方法存在一个瓶颈会明显影响效率,即数据倾斜。每个线程的处理速度可能不同,快的线程需要等待慢的线程,最终的处理速度取决于慢的线程。而针对此问题,解决的方法是,将数据划分成c×n个partition(c>1),每个线程处理完当前partition后主动取下一个partition继续处理,知道所有数据处理完毕,最后由一个线程进行归并。

    (3)单机+单核+受限内存

            这种情况下,需要将原数据文件切割成一个一个小文件,如次啊用hash(x)%M,将原文件中的数据切割成M小文件,如果小文件仍大于内存大小,继续采用Hash的方法对数据文件进行分割,知道每个小文件小于内存大小,这样每个文件可放到内存中处理。采用(1)的方法依次处理每个小文件。

    (4)多机+受限内存

            这种情况,为了合理利用多台机器的资源,可将数据分发到多台机器上,每台机器采用(3)中的策略解决本地的数据。可采用hash+socket方法进行数据分发。

     

            从实际应用的角度考虑,(1)(2)(3)(4)方案并不可行,因为在大规模数据处理环境下,作业效率并不是首要考虑的问题,算法的扩展性和容错性才是首要考虑的。算法应该具有良好的扩展性,以便数据量进一步加大(随着业务的发展,数据量加大是必然的)时,在不修改算法框架的前提下,可达到近似的线性比;算法应该具有容错性,即当前某个文件处理失败后,能自动将其交给另外一个线程继续处理,而不是从头开始处理。

            top K问题很适合采用MapReduce框架解决,用户只需编写一个Map函数和两个Reduce 函数,然后提交到Hadoop(采用Mapchain和Reducechain)上即可解决该问题。具体而言,就是首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上,最好可以让数据划分后一次读入内存,这样不同的机器负责处理不同的数值范围,实际上就是Map。得到结果后,各个机器只需拿出各自出现次数最多的前N个数据,然后汇总,选出所有的数据中出现次数最多的前N个数据,这实际上就是Reduce过程。对于Map函数,采用Hash算法,将Hash值相同的数据交给同一个Reduce task;对于第一个Reduce函数,采用HashMap统计出每个词出现的频率,对于第二个Reduce 函数,统计所有Reduce task,输出数据中的top K即可。

            直接将数据均分到不同的机器上进行处理是无法得到正确的结果的。因为一个数据可能被均分到不同的机器上,而另一个则可能完全聚集到一个机器上,同时还可能存在具有相同数目的数据。

     

    以下是一些经常被提及的该类问题。

    (1)有10000000个记录,这些查询串的重复度比较高,如果除去重复后,不超过3000000个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。请统计最热门的10个查询串,要求使用的内存不能超过1GB。

    (2)有10个文件,每个文件1GB,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。按照query的频度排序。

    (3)有一个1GB大小的文件,里面的每一行是一个词,词的大小不超过16个字节,内存限制大小是1MB。返回频数最高的100个词。

    (4)提取某日访问网站次数最多的那个IP。

    (5)10亿个整数找出重复次数最多的100个整数。

    (6)搜索的输入信息是一个字符串,统计300万条输入信息中最热门的前10条,每次输入的一个字符串为不超过255B,内存使用只有1GB。

    (7)有1000万个身份证号以及他们对应的数据,身份证号可能重复,找出出现次数最多的身份证号。

     

    重复问题

            在海量数据中查找出重复出现的元素或者去除重复出现的元素也是常考的问题。针对此类问题,一般可以通过位图法实现。例如,已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。
     

            本题最好的解决方法是通过使用位图法来实现。8位整数可以表示的最大十进制数值为99999999。如果每个数字对应于位图中一个bit位,那么存储8位整数大约需要99MB。因为1B=8bit,所以99Mbit折合成内存为99/8=12.375MB的内存,即可以只用12.375MB的内存表示所有的8位数电话号码的内容。

    转载:https://blog.csdn.net/zyq522376829/article/details/47686867

    展开全文
  • 大数据Top K算法思路

    2016-12-19 20:12:58
    大数据排序处理问题

    Top K 算法详解
    应用场景:

            搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。
            假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的10个查询串,要求使用的内存不能超过1G

    必备知识:
    什么是哈希表?

            哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。

            也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    哈希表的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。
           而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。
    问题解析:

    要统计最热门查询,首先就是要统计每个Query出现的次数,然后根据统计结果,找出Top 10。所以我们可以基于这个思路分两步来设计该算法。

    即,此问题的解决分为以下俩个步骤:

    第一步:Query统计              (统计出每个Query出现的次数)
            Query统计有以下俩个方法,可供选择:
            1、直接排序法                  (经常在日志文件中统计时,使用cat file|format key|sort | uniq -c | sort -nr | head -n 10,就是这种方法)
            首先我们最先想到的的算法就是排序了,首先对这个日志里面的所有Query都进行排序,然后再遍历排好序的Query,统计每个Query出现的次数了。

    但是题目中有明确要求,那就是内存不能超过1G,一千万条记录,每条记录是255Byte,很显然要占据2.375G内存,这个条件就不满足要求了。

    让我们回忆一下数据结构课程上的内容,当数据量比较大而且内存无法装下的时候,我们可以采用外排序的方法来进行排序,这里我们可以采用归并排序,因为归并排序有一个比较好的时间复杂度O(NlgN)。

    排完序之后我们再对已经有序的Query文件进行遍历,统计每个Query出现的次数,再次写入文件中。

    综合分析一下,排序的时间复杂度是O(NlgN),而遍历的时间复杂度是O(N),因此该算法的总体时间复杂度就是O(N+NlgN)=O(NlgN)。

           2、Hash Table法                (这种方法统计字符串出现的次数非常好)
           在第1个方法中,我们采用了排序的办法来统计每个Query出现的次数,时间复杂度是NlgN,那么能不能有更好的方法来存储,而时间复杂度更低呢?

           题目中说明了,虽然有一千万个Query,但是由于重复度比较高,因此事实上只有300万的Query,每个Query 255Byte,因此我们可以考虑把他们都放进内存中去,而现在只是需要一个合适的数据结构,在这里,Hash Table绝对是我们优先的选择,因为Hash Table的查询速度非常的快,几乎是O(1)的时间复杂度。

           那么,我们的算法就有了:

                   维护一个Key为Query字串,Value为该Query出现次数的HashTable,每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内完成了对该海量数据的处理。

                    本方法相比算法1:在时间复杂度上提高了一个数量级,为O(N),但不仅仅是时间复杂度上的优化,该方法只需要IO数据文件一次,而算法1的IO次数较多的,因此该算法2比算法1在工程上有更好的可操作性。

         第二步:找出Top 10          (找出出现次数最多的10个)
         算法一:普通排序             (我们只用找出top10,所以全部排序有冗余)
         我想对于排序算法大家都已经不陌生了,这里不在赘述,我们要注意的是排序算法的时间复杂度是NlgN,在本题目中,三百万条记录,用1G内存是可以存下的。

         算法二:部分排序         
         题目要求是求出Top 10,因此我们没有必要对所有的Query都进行排序,我们只需要维护一个10个大小的数组,初始化放入10个Query,按照每个Query的统计次数由大到小排序,然后遍历这300万条记录,每读一条记录就和数组最后一个Query对比,如果小于这个Query,那么继续遍历,否则,将数组中最后一条数据淘汰(还是要放在合适的位置,保持有序),加入当前的Query。最后当所有的数据都遍历完毕之后,那么这个数组中的10个Query便是我们要找的Top10了。

          不难分析出,这样,算法的最坏时间复杂度是N*K, 其中K是指top多少。

           算法三:堆
           在算法二中,我们已经将时间复杂度由NlogN优化到N*K,不得不说这是一个比较大的改进了,可是有没有更好的办法呢

           分析一下,在算法二中,每次比较完成之后,需要的操作复杂度都是K,因为要把元素插入到一个线性表之中,而且采用的是顺序比较。这里我们注意一下,该数组是有序的,一次我们每次查找的时候可以采用二分的方法查找,这样操作的复杂度就降到了logK,可是,随之而来的问题就是数据移动,因为移动数据次数增多了。不过,这个算法还是比算法二有了改进。

           基于以上的分析,我们想想,有没有一种既能快速查找,又能快速移动元素的数据结构呢?

           回答是肯定的,那就是堆。
           借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此到这里,我们的算法可以改进为这样,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比。

    思想与上述算法二一致,只是在算法三,我们采用了最小堆这种数据结构代替数组,把查找目标元素的时间复杂度有O(K)降到了O(logK)。
           那么这样,采用堆数据结构,算法三,最终的时间复杂度就降到了N*logK,和算法二相比,又有了比较大的改进。

    总结:

    至此,算法就完全结束了,经过上述第一步、先用Hash表统计每个Query出现的次数,O(N);然后第二步、采用堆数据结构找出Top 10,N*O(logK)。所以,我们最终的时间复杂度是:O(N) + N'*O(logK)。(N为1000万,N’为300万)。 

     

    /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

     

    问题一:

            找出一个无序数组里面前K个最大数

    算法思想1

           对数组进行降序全排序,然后返回前K个元素,即是需要的K个最大数。

           排序算法的选择有很多,考虑数组的无序性,可以考虑选择快速排序算法,其平均时间复杂度为O(NLogN)。具体代码实现可以参见相关数据结构与算法书籍。


    算法思想2(比较好):

             观察第一种算法,问题只需要找出一个数组里面前K个最大数,而第一种算法对数组进行全排序,不单单找出了前K个最大数,更找出了前N(N为数组大小)个最大数,显然该算法存在“冗余”,因此基于这样一个原因,提出了改进的算法二。 

             首先建立一个临时数组,数组大小为K,从N中读取K个数,降序全排序(排序算法可以自行选择,考虑数组的无序性,可以考虑选择快速排序算法),然后依读入其余N - K个数进来和第K名元素比较,大于第K名元素的值则插入到合适位置,数组最后一个元素溢出,反之小于等于第K名元素的值不进行插入操作。只待循环完毕返回临时数组的K个元素,即是需要的K个最大数。同算法一其平均时间复杂度为O(KLogK + (N - K))。具体代码实现可以自行完成。


    原文:

    问题二:
           有1亿个浮点数,请找出其中最大的10000个。
           提示:假设每个浮点数占4个字节,1亿个浮点数就要站到相当大的空间,因此不能一次将全部读入内存进行排序。

           可以发现如果一次读入那么机器的内存肯定是受不了的,因此我们只有想其他方法解决,解决方式为了高效还是得符合一定的该概率解决,结果并不一定准确,但是应该可以作对大部分的数据。

    算法思想1、
           1、我们可以把1亿个浮点数利用哈希分为了1000个组
    (将相同的数字哈希到同一个数组中)

           2、第一次在每个组中找出最大的1W个数,共有1000个;

           3、第二次查询的时候就是100W个数中再找出最大的1W个数。
           PS:100W个数中再找出最大的1W个数用类似快排的思想搞定。
    算法思想2(比较好)、
          1、读入的头10000个数,直接创建二叉排序树。O(1)

          2、对以后每个读入的数,比较是否比前10000个数中最小的大。(N次比较)如果小的话接着读下面的数。O(N)
          3、如果大,查找二叉排序树,找到应当插入的位置。
           4、删除当前最小的结点。
           5、重复步骤2,直到10亿个数全都读完。
           6、按照中序遍历输出当前二叉排序树中的所有10000个数字。
           基本上算法的时间复杂度是O(N)次比较
           算法的空间复杂度是10000(常数)

           基于上面的想法,可以用最小堆来实现,这样没加入一个比10000个树中最小的数大时的复杂度为log10000.

     

    相关类似问题:

    1、一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。

         方案1:这题是考虑时间效率。用trie树(前缀树)统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度)。然后是找出出现最频繁的前10个词,可以用堆来实现,前面的题中已经讲到了,时间复杂度是O(n*lg10)。所以总的时间复杂度,是O(n*le)与O(n*lg10)中较大的哪一个。

     

    2、 一个文本文件,找出前10个经常出现的词,但这次文件比较长,说是上亿行或十亿行,总之无法一次读入内存,问最优解。

         方案1:首先根据用hash并求模,将文件分解为多个小文件,对于单个文件利用上题的方法求出每个文件件中10个最常出现的词。然后再进行归并处理,找出最终的10个最常出现的词。

     

    3、 100w个数中找出最大的100个数。

    • 方案1:采用局部淘汰法。选取前100个元素,并排序,记为序列L。然后一次扫描剩余的元素x,与排好序的100个元素中最小的元素比,如果比这个最小的要大,那么把这个最小的元素删除,并把x利用插入排序的思想,插入到序列L中。依次循环,知道扫描了所有的元素。复杂度为O(100w*100)。
    • 方案2:采用快速排序的思想,每次分割之后只考虑比轴大的一部分,知道比轴大的一部分在比100多的时候,采用传统排序算法排序,取前100个。复杂度为O(100w*100)。
    • 方案3:在前面的题中,我们已经提到了,用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。

    展开全文
  • 大数据下的TopK算法

    2019-09-25 10:59:43
    大数据背景下,TopK问题是一个很常见的问题。常见到这类问题基本在任何从事大数据相关的工作中都会用到。而我以前面试和大数据相关的岗位时也基本每次都会被问及这一问题或者这一问题的简单变种。因此,写本文详细...

           在大数据背景下,TopK问题是一个很常见的问题。常见到这类问题基本在任何从事大数据相关的工作中都会用到。而我以前面试和大数据相关的岗位时也基本每次都会被问及这一问题或者这一问题的简单变种。因此,写本文详细介绍一下在大数据背景下TopK问题的解决方法,供大伙学习学习,尤其是让即将面临找工作面试的同学在面对这类问题时心里有个底。

           该问题的求解目标很简单,即从一堆数据中挑出权值最大的K个数据。不同的是,在大数据背景下,这堆数据非常庞大,无法将这些数据装入内存中。因此,一部分方法就无法使用,比如基于冒泡排序的方法从逐个挑出个最大值,该方法由于复杂度太高无法被采用;而基于快排TopK算法寻找第大的权值虽然方法十分巧妙,而且达到了最快的线性复杂度,但该算法要求加载所有数据到内存,这在大数据背景下并不现实。

           在大数据背景下,最适合用来处理TopK问题的方法是采用基于最小堆实现的方法。因此,本文将就该方法展开介绍。

           更多信息,参见作者个人主页Jianping Cai's Research Page

    展开全文
  •  生活中经常会遇到求TopK的问题,在小数据量的情况下可以先将所有数据排序,最后进行遍历。但是在大数据量情况下,这种的时间复杂度最低的也就是O(NlogN)此处的N可能为10亿这么大的数字,时间复杂度过高,那么什么...
  • top k 简介:在大量数据中找出重复次数最多的前K个。 问题分析: 听起来这个问题十分简单,只需对这些数据进行一次排序即可得到前K个。如果这样的话,首先得定义一个数据结构来保存这些数据,大量的数据会消耗过...
  • 核心解题要领 1. 使用堆 2. 分文件处理,topK,每个文件取M个,在M个取K个 3. 读数据的时候,不用一次全部读取内存,分开处理。
  • 大数据Top K 总结

    2020-06-17 16:43:54
    TOP k 问题 1亿个数字中找出最大或最小的前100个数字 方法1:全部排序 方法2:局部淘汰法 插入容器后的操作 局部淘汰法的去重 方法3:分治法 分治-快排划分 分治-排序 分治-堆排序 合并结果 方法4:Hash...
  • 在数周前所发表的博文《大数据下的TopK算法》中介绍了求解大数据时代中几乎是最为经典的TopK的过程。虽然大数据技术使得大规模数据下的TopK问题得到了有效的解决,但是对于一些该问题的拓展,单单靠大数据技术是无法...
  • 词频统计与取前k内容   比如百度搜索如何取前k条符合的内容呢,最基础的方法是先算出每个内容的匹配值然后取前k位。词频类似,统计词对应频率然后取前k位   Topk 求取算法 TopK Elements 问题用于找出一组数...
  • Top K问题详解

    2018-10-14 22:40:07
    一、Top K问题的概述  在大规模数据处理中,经常会遇到的一类问题:在海量数据中找出出现频率最好的前k个数,或者从海量数据中找出最大的前k个数,这类问题通常被称为top K问题。例如在搜索引擎中,统计搜索最热门...
  • 大数据小内存TOPK,排序问题。
  • 前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些。 先拿10000个数建堆,然后一次...
  • TopK问题 给定一个集合(元素个数很多N),想找到最大的或者最小的k个元素。 以找k个最大为例的俩种TopK方法: 之前讲过一次利用库函数里的普通优先级队列完成。 ...建立大小为k的小堆,堆顶元素一定是这k个里最小的,...
  • TopK问题,即寻找最大的K个数,这个问题非常常见,比如从1千万搜索记录中找出最热门的10个关键词. 方法一: 先排序,然后截取前k个数. 时间复杂度:O(n*logn)+O(k)=O(n*logn)。 方法二: 最小堆. 维护容量为k的...
  • public static void main(String[]args){ Heap heap = new Heap(10); Random r = new Random(); for (int i = 0;i<10000000;i++){ heap.add(r.nextInt(1000000000)); ...
  • topK问题:假如需要从十亿个数据中找出最大的前k个数,也就是海量数据处理问题。一般遇见这种问题,我们肯定会想到先排序,再取前K个数据就可以了。但是海量数据如果这样处理,那就会大大提高时间复杂度了。那么我们...
  • 海量数据中的TopK问题

    2018-10-12 13:25:40
     在大规模数据处理中,经常会遇到的一类问题:在海量数据中找出出现频率最好的前k个数,或者从海量数据中找出最大的前k个数,这类问题通常被称为top K问题。例如,在搜索引擎中,统计搜索最热门的10个查询词;在...
  • 海量数据取top K问题

    2018-02-26 16:12:00
    一个列表中有1亿个数据,需要取出其中最大的前100个数据,如何尽可能的降低时间复杂度?最容易想到的方法是先对这1亿个数据排序,然后取出最大的100个数据,这样的话时间复杂度就是O(nlogn),显然方法不合适。...
1 2 3 4 5 ... 20
收藏数 10,006
精华内容 4,002
关键字:

k top 大数据