2017-11-09 21:29:43 wangle965235568 阅读数 214
  • SQL 注入防御在互联网企业中的实践

    SQL注入视频教程,Sql注入是一种流行且危害极大的web攻击手法,长期占据 OWASP TOP10 首位。本课程主要讲解 SQL 注入攻击的原理和技术手法,并讲解在互联网企业中如何有效防御。内容包括SQL注入引发的安全事件回顾、SQL注入定义、SQL注入原理、SQL注入技术手法5、SQL注入危害、SQL注入防御的实践。

    1873 人正在学习 去看看 CSDN讲师


top k 简介:在大量数据中找出重复次数最多的前K个。

问题分析
听起来这个问题十分简单,只需对这些数据进行一次排序即可得到前K个。如果这样的话,首先得定义一个数据结构来保存这些数据,大量的数据会消耗过大的进程资源,甚至“耗尽”进程的资源。还有一个问题是排序的时间复杂度是非常高的,一般来说,较快的排序算法时间复杂度是O(n*log2n)。倘若数据过大,也就是n过大,时间复杂度也会是非常高的。为了提高程序执行效率,我们应该尽快的优化程序,使程序在个个情况下的复杂度达到理想化。

解决办法:1.数据量过大,导致进程资源被耗尽的问题:将大量数据平均写到多个文件当中,再找出每个文件中的top k并记录,再找出记录下来的前top k。则最终找到的就为整个大数据中的top k。
2.时间消耗过大:我们可以先将每个文件中的数据存入到map表中去。first:数据,second:重复的次数。再利用小根堆,先将前10个数据添加到map表中,然后依次比较剩下的数据的second如果大于map表中top的second,则将他更新到map表中。最终只需打印出小根堆所对应的前10个元素即可。

#include <iostream>
#include <map>
#include <string>
#include <string.h>
#include <hash_map>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

struct Value
{
       Value(int key = 0 )
           :_key(key)
           ,_count(1)
       { }
       bool operator>(const Value &src)const                //凡是不修改对象的,一律写成常方法
       {
          return _count > src._count;
       }
      int  _key;
      int _count;
};
int main()
{
   FILE* pf = fopen("data.txt","w");
   for(unsigned int i=0;i<1000000;++i)
   {
       fprintf(pf, "%d ",rand()%500);
   }
   fclose(pf);

    const int FILE_NUM = 200;
    FILE* pfiles[FILE_NUM];
    for(int i=0; i<FILE_NUM; ++i)
    {
        char buffer[50] = "data.txt";
        char index[10] = {0};
        itoa(i, index, 10);
        strcat(buffer, index);
        pfiles[i] = fopen(buffer,"w");
    }
    pf = fopen("data.txt", "r");
    while(!feof(pf))
    {
        int data = 0;
        fscanf(pf,"%d", &data);
        int fileindex = data%FILE_NUM;
        fprintf(pfiles[fileindex], "%d ", data);
    }

    for(int i=0;i<FILE_NUM;i++)
    {
        fclose(pfiles[i]);
    }

    fclose(pf);

    for(int i=0; i<FILE_NUM; ++i)
    {
        char buffer[50] = "data.txt";
        char index[10] = {0};
        itoa(i, index, 10);
        strcat(buffer, index);
        pfiles[i] = fopen(buffer,"r");
    }

      vector<Value> last;//保存最终200个文件中的分别的重复最多的前10个元素
    for(int i=0;i<FILE_NUM;i++)
    {
        vector<int> array;
       while(!feof(pfiles[i]))
       {
           int data;
           fscanf(pfiles[i], "%d", &data);
           array.push_back(data);
       }

        hash_map<int,Value> map2;
        while(!array.empty())
        {
             //map2[array[i]]++;
             hash_map<int,Value>::iterator it = map2.find(array.back());
              if(it == map2.end())
              {
                 map2[array.back()] = Value(array.back());
              }
              else
              {
                it->second._count++;
              }
              array.pop_back();
         }

        priority_queue<Value,vector<Value>,greater<Value>> que;

         hash_map<int,Value>::iterator it2 = map2.begin();
         for(int i=0;it2 != map2.end();++it2,++i)
          {
                 if(i<10)
                {
                  que.push(it2->second);
                }
              else
              {
                if(it2->second > que.top())
                 {
                    que.pop();
                    //que.push(it2->second);
                    que.push(it2->second);
                 }
             }
         }
            while(!que.empty())
            {
                last.push_back(que.top());
                que.pop();
            }
    }


    hash_map<int,Value> map3;
    priority_queue<Value,vector<Value>,greater<Value>> que1;
    int flag = 0;
    while(!last.empty())
    {
        hash_map<int,Value>::iterator it = map3.find(last.back()._key);
        if(it == map3.end())
        {
            map3[last.back()._key] = last.back();
        }
        else
        {
            it->second._count++;
        }
        last.pop_back();
    }

    hash_map<int,Value>::iterator it = map3.begin();
    for(int i=0;it!=map3.end();it++,i++)
    {
       if(i<10)
       {
           que1.push(it->second);
       }
       else
       {
           if(it->second > que1.top())
           {
              que1.pop();
              que1.push(it->second);
           }
       }
    }
    while(!que1.empty())
   {
     cout<<"first:"<<que1.top()._key<<"   second:"<<que1.top()._count<<endl;
      que1.pop();
   }
    for(int i=0;i<FILE_NUM;i++)
    {
        fclose(pfiles[i]);
    }
   return 0;
}
2018-09-04 22:05:09 z_x_m_m_q 阅读数 314
  • SQL 注入防御在互联网企业中的实践

    SQL注入视频教程,Sql注入是一种流行且危害极大的web攻击手法,长期占据 OWASP TOP10 首位。本课程主要讲解 SQL 注入攻击的原理和技术手法,并讲解在互联网企业中如何有效防御。内容包括SQL注入引发的安全事件回顾、SQL注入定义、SQL注入原理、SQL注入技术手法5、SQL注入危害、SQL注入防御的实践。

    1873 人正在学习 去看看 CSDN讲师

提示:这里解决 top K 问题是基于堆数据结构下的,对这块还有问题的可以点以下链接:

https://blog.csdn.net/z_x_m_m_q/article/details/82320357

Top K问题:

Topk问题是一个经典的海量数据处理问题, 在海量数据中找出出现频率最高的前k个数,或者从海量数据中找出最大的前k个数,这类问题通常被称为Top K问题

比如,热搜上每天更新出的排行前10的热门搜索信息,陕西人最爱吃的水果种类等,都可以使用topK问题来解决

海量数据:

海量数据拥有的一大特点就是数据量比较大, 一般情况下内存空间是不足以一次性来存储的,或者处理海量数据是往往有空间上的限制

例如:面试官给你100W个数据,请找出其中最大的前K个数,并且现在仅仅有1M的空间?

在32位操作系统中,默认每个数据为4字节,很显然 1M 的空间是存放不了要处理的目标数据

算法思想:

从大量数据中找出前 K 个最大数为例来说明:

首先以给定数据中的前 K 个数建立小堆,然后从 K+1 个数据开始与堆顶元素作比较,小于或等于堆顶元素时,保持建立的小堆不变;大于堆顶元素时,将该数据与堆顶元素交换,此时有可能破坏了小堆的有序性,需要从堆顶元素开始来一次向下调整使堆恢复成小堆

算法代码:

 这里我提供一个 main 函数开始的完整的代码,还有部分注释,供大家参考

#include"pch.h"
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<time.h>

void Swap(int* x,int* y)  //交换函数,建议使用这种方式交换
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void HeapAdjustDown(int* a,int n,int root)  //堆的向下调整函数
{
	int parent = root;
	int child = 2 * parent + 1;

	while (child < n) {
		if (child+1 < n && a[child+1] < a[child])
			++child;

		if (a[child] < a[parent])
			Swap(&a[child], &a[parent]);
		else
			break;

		parent = child;
		child = 2 * parent + 1;
	}
}

void Top_K(int* a,int n,int k)
{
	int i = 0;

	int* hp = (int*)malloc(sizeof(int)*k);  //用于始终存储堆中的 K 个数,记得释放空间
	for (i = 0;i < k;++i)
		hp[i] = a[i];

	for (i = (k-2)/2;i >= 0;--i)  //建堆
	{
		HeapAdjustDown(hp,k,i);
	}

	for (i = k;i < n;++i)  //从 K+1 个数开始与堆顶元素一一比较
	{
		if (a[i] > hp[0])  //a[0]:堆顶元素
		{
			hp[0] = a[i];
			HeapAdjustDown(hp, k, 0);
		}
	}

	for (i = 0;i < k;++i)  //简单的看下输出结果
	{
		printf("%d ",hp[i]);
	}

	free(hp);
	hp = NULL;
}

int main()
{
	int i = 0;
	int a[1024];

	srand((unsigned)time(NULL));

	for (i = 0;i < 1024;++i)
	{
		a[i] = rand();
	}

	Top_K(a,sizeof(a)/sizeof(a[0]),8);

	return 0;
}

结果展示: 

 

上面从大量数据中找出的最大的 8 个数显然满足小堆的性质。 

时间复杂度: 

基于堆数据结构下的 Top K 问题时间复杂度为:O(N\lg K),这是很显然的 

2017-06-15 23:09:25 sdoyuxuan 阅读数 165
  • SQL 注入防御在互联网企业中的实践

    SQL注入视频教程,Sql注入是一种流行且危害极大的web攻击手法,长期占据 OWASP TOP10 首位。本课程主要讲解 SQL 注入攻击的原理和技术手法,并讲解在互联网企业中如何有效防御。内容包括SQL注入引发的安全事件回顾、SQL注入定义、SQL注入原理、SQL注入技术手法5、SQL注入危害、SQL注入防御的实践。

    1873 人正在学习 去看看 CSDN讲师

所谓的top k 问题,海量数据找最大的或者最小的前K个数据。

最大的这种问题处理方式:

先进行哈希分割,再将这些数据前K个元素建立一个最小堆,如果之后的元素比堆顶大的话,将堆顶元素替换为该元素,这样将剩余的元素依次这样遍历完,这个堆的所有元素就是最大的前K个元素。

最小的这种问题处理方式:

先进行哈希分割,将这些数据,前K个元素建立一个最大堆,如果其后元素,比堆顶小,用该元素完成替换即可。

(哈希分割,即把一个大文件分割成M个小文件,每个大文件中的数据用直接取余法%M,最后把得到的哈希地址作为该数据存放的文件号)

分析:

为什么最大的前K个元素,要用最小堆呢?

因为,如果一个元素比堆顶小,那么它肯定比这个最小堆的所有元素小,那它肯定不是前K个最大的之一。这里把堆顶当一个标准,比它大的才能加入到前K个集合中。

如果这里我们使用最大堆,那么该元素比堆顶小,但是它不一定比堆下面的元素小,所以如果我们直接插入是不正确的。那么如果我们用该元素比堆顶大的话插入,但是这由出问题了,即使该元素被堆顶大可以插入,但出堆的不应该是故堆顶啊,应该是堆内最小的元素。可没法找到堆内最小元素,因为堆只保证父与子有序性。所以在找最大的前K个元素的问题中我们使用最小堆。

2018-10-17 21:44:40 afei__ 阅读数 199
  • SQL 注入防御在互联网企业中的实践

    SQL注入视频教程,Sql注入是一种流行且危害极大的web攻击手法,长期占据 OWASP TOP10 首位。本课程主要讲解 SQL 注入攻击的原理和技术手法,并讲解在互联网企业中如何有效防御。内容包括SQL注入引发的安全事件回顾、SQL注入定义、SQL注入原理、SQL注入技术手法5、SQL注入危害、SQL注入防御的实践。

    1873 人正在学习 去看看 CSDN讲师

一、题目

在一个由 n 个元素组成的集合中,按从小到大顺序排序的话,第 K 个顺序统计位即指第 K 个数,当 K = n 时即最大值,当 K = 1 时即最小值。先给定一个无序的元素集合,求集合中第 K 统计位的值是多少?

同理,若求 top K 的数据的话,即求集合中最大的前 K 个数分别是多少?

例如,给定数组 [ 0, 9, 3, 6, 8, 2, 1, 5, 7, 4 ] ,则第 4 统计位的数字是 3,top 3 大的数是 [ 9, 8, 7 ]。

 

二、最大值和最小值

1. 简介

先说一个很特殊的场景,碰巧 K = 1 或者 K = n 的时候,即我们常说的最小值和最大值。解法很简单,即遍历一遍集合就可以找出最大值和最小值了,遍历一次集合找出最大值或最小值需要比较 n - 1 次,时间复杂度为 O(n)。

假如有种场景我们要同时得到最大值和最小值,最直观的解法就是遍历一次,通过比较 2 * (n - 1) 次就可以得到最大值和最小值了。但是其实我们只需要比较 n * 3 / 2 次就可以了。

2. 代码

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main() {
    int arr[] = { 12, 2, 32, 64, -10, 33, -6, 0, 2, 10 };
    int length = sizeof(arr) / sizeof(arr[0]);
    int max;
    int min;
    int *p = arr;
    if (length & 1) { // 数组长度为奇数
        max = min = arr[0];
        p++;
    }
    else { // 数组长度为偶数
        if (arr[0] > arr[1]) {
            max = arr[0];
            min = arr[1];
        }
        else {
            max = arr[1];
            min = arr[0];
        }
        p += 2;
    }
    while (p < &arr[length]) {
        int first = *(p++);
        int second = *(p++);
        if (first > second) {
            max = std::max(max, first);
            min = std::min(min, second);
        }
        else {
            max = std::max(max, second);
            min = std::min(min, first);
        }
    }
    cout << "max: " << max << ", min: " << min << endl;
    return 0;
}

3. 评价

该方法只适用于求最大值和最小值的情况。我们每次取两个数,先比较一次得到他们的大小关系,然后我们用较大者和当前最大值比较,用较小者和当前最小值比较,这样我们就只需要比较 3 次就可以比较完 2 个新的元素了。

 

三、排序法

1. 简介

回到主题,K 往往并不是 0 或者 n,那么怎么求解呢?很多人最直接的想法就是,我把集合排个序,然后再取第 K 位的数或者 top K 那还不是轻而易举了。

当然,排序也是可以偷懒的,例如我们求第 10 大的元素的话,我们只需要进行 10 次冒泡排序或者选择排序即可,即遍历 10 次集合就可以达到我们的目的。

2. 代码

冒泡排序或选择排序的代码都很简单,这里不做示例了。

3. 评价

值得说明的是,该方法只适合数据集不大或者 K 值很小的情况下使用,假如我们要求海量数据的中位数时,排序法的效率都远不如其它方法了。

 

四、最小堆和最大堆法

1. 简介

最小堆和最大堆的性质还不知道的赶紧去百度了。

假如我们要求集合中最大的前 K 个数的话,我们可以创建一个大小为 K 的最小堆,它的根结点一定是这 K 个元素中的最小值,然后我们只需要遍历 1 遍集合即可。分别和堆中的最小值(即根结点)比较,如果大于它,则我们使用这个新的值替代根结点并刷新堆,使得堆的根结点依旧是这 K 个元素中的最小值。最后遍历完集合后,堆里的这 K 个值就是整个集合中的 top K 了,堆的根结点就是第 K 大的值了。

同理,求最小的前 K 个数的话,就使用一个大小为 K 的最大堆。

2. 代码

public class Main {
 
    public static void main(String[] args) {
        int[] arr = new int[] { 12, 0, 88, -36, 24, 256, 4, -2, 64, 56, 88,
                72, 100, 6, 12, 32, 96, 54, 48, 36 };
        int[] heap = getTopK(arr, 5);
        printArray(heap);
    }
 
    public static int[] getTopK(int[] arr, int k) {
        if (k >= arr.length) {
            return arr;
        }
        int[] heap = new int[k];
        System.arraycopy(arr, 0, heap, 0, heap.length);
        buildMinHeap(heap);
        for (int i = k; i < arr.length; i++) {
            if (arr[i] > heap[0]) {
                heap[0] = arr[i];
                minHeapify(heap, 0, heap.length);
            }
        }
        // 如果需要 Top K 按照从大到小的顺序排序的话
        int heapSize = heap.length;
        for (int i = heap.length - 1; i > 0; i--) {
            int min = heap[0];
            heap[0] = heap[i];
            heap[i] = min;
            minHeapify(heap, 0, --heapSize);
        }
        return heap;
    }
 
    public static void buildMinHeap(int[] heap) {
        // 堆的最后一个分支结点索引为 arr.length / 2 - 1
        for (int i = heap.length / 2 - 1; i >= 0; i--) {
            minHeapify(heap, i, heap.length);
        }
    }
 
    /**
     * 调整堆,使其满足最小堆的性质
     */
    public static void minHeapify(int[] heap, int index, int heapSize) {
        int leftIndex = index * 2 + 1; // 左子节点对应数组中的索引
        int rightIndex = index * 2 + 2; // 右子节点对应数组中的索引
        int minIndex = index;
        // 如果左子结点较小,则将最小值索引设为左子节点
        if (leftIndex < heapSize && heap[leftIndex] < heap[index]) {
            minIndex = leftIndex;
        }
        // 如果右子结点比 min(this, left)还小,则将最小值索引设为右子节点
        if (rightIndex < heapSize && heap[rightIndex] < heap[minIndex]) {
            minIndex = rightIndex;
        }
        // 如果当前结点的值不是最小的,则需要交换最小值,并继续遍历交换后的子结点
        if (minIndex != index) {
            int temp = heap[minIndex];
            heap[minIndex] = heap[index];
            heap[index] = temp;
            minHeapify(heap, minIndex, heapSize);
        }
    }
 
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
 
}

执行结果:

256 100 96 88 88 

3. 评价

由于最小堆或者最大堆的操作时间复杂度均为 O(lg n),n 是堆的大小,大小为 K 的堆即 O(lg K)。且只需要遍历一遍集合,则时间复杂度基本为 O(n * lg K)。可以说该方法的执行效率总是会高于排序法了。

且当 K 值较小时,该算法拥有一个较小的常数系数 lg K ,效率还是很高的。

 

五、快速选择法

1. 简介

快速选择法是一个期望为线性时间的选择算法。它是以快速排序算法为模型修改的。

简单介绍一下原理:首先我们知道快速排序的原理是根据一个 pivot 值,将集合中小于 pivot 的值放置在其左侧,将大于 pivot 的值放置在其右侧,然后再递归地处理左右两侧,最终完成整个集合的排序。快速选择则只处理其中一边,那么根据 pivot 的坐标判断, K 小于 pivot 的话那么我们的数据肯定在左侧,相反则在右侧,等于则直接返回,因为它就是我们要找的数。

如果是求 top K,那我们再以这个第 K 统计位的数为 pivot,划分一次集合即可。

2. 代码

#include <stdio.h>
 
int partition(int *arr, int start, int end) {
    if (start >= end) return arr[start];
    int pivot = arr[start];
    while (end > start) {
        while (end > start && arr[end] >= pivot) {
            end--;
        }
        arr[start] = arr[end]; // 将小于 pivot 的数放在低位
        while (end > start && arr[start] <= pivot) {
            start++;
        }
        arr[end] = arr[start]; // 将大于 pivot 的数放在高位
    }
    arr[start] = pivot;
    return start; // 返回当前轴点位置
}
 
int quickSelect(int *arr, int length, int k) {
    int start = 0;
    int end = length - 1;
    while (end >= start) {
        int p = partition(arr, start, end);
        if (p == k - 1) { // 数组的索引是0开始的,第k大的索引是1开始的
            return arr[p];
        } else if (p < k - 1) {
            start = p + 1;
        } else {
            end = p - 1;
        }
    }
    return 0;
}
 
int main() {
    int arr[] = { 5, 4, 8, 6, 3, 9, 10, 1, 7, 2 };
    printf("第5位的元素为:%d\n", quickSelect(arr, sizeof(arr) / sizeof(arr[0]), 5));
    return 0;
}

3. 评价

快速选择的效率比快速排序已经高了很多,平均时间复杂度通常为 O(n * lg n) 到 O(n)。然后,最坏情况下,它的时间复杂度仍然为 O(n ^ 2)。

即便如此,快速选择及其变种是实际应用中最常使用的高效选择算法,适用于求海量数据的中位数这种 K 也很大的情况。

 

六、BFPRT 算法

1. 简介

BFPRT 算法是一个最坏情况下仍为线性时间的选择算法,它是上述快速选择算法的变种,避免了最坏情况的产生。

BFPRT 算法又称为中位数的中位数算法,是由 5 位大牛 (Blum, Floyd, Pratt, Rivest, Tarjan) 提出,并以他们的名字命名的算法。和选择算法不同的是,它首先将集合以 5 个 5 个元素的划开,先求出每 5 个元素的中位数,再求出这些中位数的中位数,最后以这个中位数的中位数为 pivot 划分集合,以此避免了最坏情况的产生。

2. 代码

#include <stdio.h>
 
int BFPRT(int *arr, int start, int end, int k);
 
void swap(int *a, int *b) {
    if (a != b) {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
}
 
int insertSort(int *arr, int start, int end) {
    for (int i = start + 1; i <= end; i++) {
        for (int j = i; j > start; j--) {
            if (arr[j] < arr[j - 1]) {
                swap(&arr[j], &arr[j - 1]);
            } else {
                break;
            }
        }
    }
    return ((end - start) >> 1) + start; // 返回中位数的下标
}
 
int getMedianIndex(int *arr, int start, int end) {
    int length = end - start + 1;
    if (length <= 5) {
        return insertSort(arr, start, end);
    }
    int subEnd = start; // 中位数的结束位置
    for (int i = start; i + 4 <= end; i += 5) {
        int index = insertSort(arr, i, i + 4);
        swap(&arr[subEnd++], &arr[index]);
    }
    int module = length % 5; // 不能被 5 整除的余数部分
    if (module != 0) {
        int index = insertSort(arr, end - module + 1, end);
        swap(&arr[subEnd++], &arr[index]);
    }
    return getMedianIndex(arr, start, subEnd - 1);
}
 
int partition(int *arr, int start, int end, int pivotIndex) {
    if (start >= end) return arr[start];
    swap(&arr[start], &arr[pivotIndex]);
    int pivot = arr[start];
    while (end > start) {
        while (end > start && arr[end] >= pivot) {
            end--;
        }
        arr[start] = arr[end]; // 将小于 pivot 的数放在低位
        while (end > start && arr[start] <= pivot) {
            start++;
        }
        arr[end] = arr[start]; // 将大于 pivot 的数放在高位
    }
    arr[start] = pivot;
    return start; // 返回当前轴点位置
}
 
int BFPRT(int *arr, int start, int end, int k) {
    if (end - start < 5) {
        insertSort(arr, start, end);
        return arr[k - 1]; // 数组长度太短的话直接处理
    }
    int medianIndex = getMedianIndex(arr, start, end); // 中位数的中位数下标
    int pivotIndex = partition(arr, start, end, medianIndex); // 划分后当前轴点的下标
    if (pivotIndex == k - 1) {
        return arr[pivotIndex];
    } else if (pivotIndex < k - 1) {
        return BFPRT(arr, pivotIndex + 1, end, k);
    } else {
        return BFPRT(arr, start, pivotIndex - 1, k);
    }
    return 0;
}
 
int main() {
    int arr[] = { 5, 4, 8, 6, 3, 9, 0, 1, 7, 2 };
    for (int i = 0; i < 10; i++) {
        printf("第%d位的元素是:%d\n", i + 1, arr[BFPRT(arr, 0, 9, i + 1)]);
    }
    return 0;
}

3. 评价

BFPRT 算法代码比较复杂,但它基本保证了 O(n) 时间下求出结果,只是它的常数系数并不小,所以适合海量数据下,同时 K 也很大的情况,典型的就是求海量数据的中位数了。

2018-03-21 11:12:30 brycegao321 阅读数 3918
  • SQL 注入防御在互联网企业中的实践

    SQL注入视频教程,Sql注入是一种流行且危害极大的web攻击手法,长期占据 OWASP TOP10 首位。本课程主要讲解 SQL 注入攻击的原理和技术手法,并讲解在互联网企业中如何有效防御。内容包括SQL注入引发的安全事件回顾、SQL注入定义、SQL注入原理、SQL注入技术手法5、SQL注入危害、SQL注入防御的实践。

    1873 人正在学习 去看看 CSDN讲师

大数据下的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
    }

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

Top K问题详解

阅读数 69

海量数据top K问题

阅读数 752

没有更多推荐了,返回首页