datetime:2024/2/29 17:38
author:nzb

大数据题目(资源限制类)

大数据题目的解题技巧

  • 1）哈希函数可以把数据按照种类均匀分流
  • 2）布隆过滤器用于集合的建立与查询，并可以节省大量空间
  • 3）一致性哈希解决数据服务器的负载管理问题
  • 4）利用并查集结构做岛问题的并行计算
  • 5）位图解决某一范围上数字的出现情况，并可以节省大量空间
  • 6）利用分段统计思想、并进一步节省大量空间
  • 7）利用堆、外排序来做多个处理单元的结果合并

之前的课已经介绍过前4个内容，本节内容为介绍解决大数据题目的后3个技巧

在面试时需要咨询面试官是否接受失误率，有没有空间限制等，这一点很重要

题目一

32位无符号整数的范围是0~4,294,967,295(0~2^32-1, 即42.9亿)，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，怎么找到所有未出现过的数？

  • 【进阶】内存限制为 10MB(或3KB)，但是只用找到一个没出现过的数即可
  • 解决方法
    • 用哈希分流，但是需要内存很大
    • 用位图(bitmap), 区间统计(分段统计思想)
  • 基础解决思路
    • 0-2^32-1这个数中只出现40亿个。一个字节8bit，也就是一个字节可以表示8个数。用01表示出现过没有就行。如果我们准备一个2的32次方的bit的数组需要多少空间，2^32 / 8 byte ≈ 512MB，一位表示一个数出现没出现过

  • 进阶解决思路(不管给多少空间，用此办法都可以)

    • 首先3000B // 4 =700，也就是能申请长度700的无符号整型(一个整型4B)数组 ）上找到一个离2的次方最接近的一个数，也就是 2^9 = 512 离得最近 （为什么要2的次方，因为0~2^32 次方个数能够按照这个数整除分割。也就是2^32 / 2^9 = 8388608）。
    • 申请一个数组长度为512的数组。然后每一个位置上表示的含义是：40亿的数字按照512的大小均分，分成了8388608份，
    • 那么0~8388608 这些数就放在第一个位置上
    • 8388608 ~ 8388608x2是第二个位置表示的值
    • 怎么统计这个范围的数出现了几次？用这个数除以8388608，比如 1 // 8388608 = 0，那么1这个数就是属于这个数组中的0号位置，就把0号位置的次数加1
      • 然后统计第一个位置上这个数出现的次数是不是8388608个。如果不是，说明一定在这个范围内有一个数字没有出现，然后再把8388608按照512的大小继续进行均分，
      • 重复上面的操作，一定可以找出那个没有出现的数字。

  • 如果只给3个变量(有限几个变量)，怎么找出？把40亿进行二分，少数字那边继续二分找，最多过32次文件。同样的原理。

题目二

  • 有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL
    • 首先可以使用布隆过滤器，但是利用它会有失误率。
    • 如果不能有失误率，则用哈希函数进行分流的方法。
      • 先对大文件中的数据用哈希函数求出哈希值，分配到小文件当中。如果该小文件不能满足题目的内存限制要求，就对小文件中的数据再次进行哈希，放入到直到满足题目要求的文件中即可。主要的就是利用多次哈希。
  • 【补充】某搜索公司一天的用户搜索词汇是海量的(百亿数据量)，请设计一种求出每天热门Top100词汇的可行办法
    • ①哈希分流。首先把包含百亿数据量的词汇文件分流到不同机器上；如果每一台机器上分到的数据量依然很大，再用哈希函数把每台机器的分流文件拆成更小文件处理；
    • ②处理每一个小文件时，通过哈希表做一个词频统计，哈希表记录完成后，再遍历哈希表，每个小文件都有一个大根堆，维持排名
    • ③把每个小文件大根堆堆顶拿出来，单独组装放到一个100的大根堆(总堆)，然后一次弹出，然后看来自于哪，删除，把下一个元素放到总堆里面
    • ④不同机器之间使用总堆进行外排序，最终求出整个百亿数据量中的Top 100。

题目三

32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数，可以使用最多1GB的内存，找出所有出现了两次的数。

  • 1）用哈希函数再取模分类到小文件的方式

  • 2）可以利用位图，建立一个bit数组。每两个bit代表一个数字的出现次数的情况。

    • 如果是00，代表1一次都没有出现；
    • 如果是01，代表出现了1次；
    • 如果是10，代表出现了两次；
    • 如果是11，代表出现了三次或三次以上。
    • 最后遍历数组，找出哪个数对应的bit位是10的，那么就说明它出现了两次。
    • 但是，因为我们是用两个bit位代表一个数字的出现次数，假设用一个bit位的时候，数组的大小为：2^32 / 8 / 1024 = 524288KB = 512MB，因为是两bit位，则再乘2，超过了1G。那么如何解决？

  • 【补充】可以使用最多10MB(3KB)的内存，怎么找到这40亿个整数的中位数？

    • 分段统计思想，将数分为各个区间，然后区间内统计词频，可以知道中位数在哪个区间中，然后再将该区间在分段求解。
    • 同样地，因为是最多3K内存，可以设置一个长度512的数组对2的32次方个数进行划分。在数组中对每个下标代表的数进行统计。如：下标0代表的数是0~8388608。
    • 因为要找出40亿个数的中位数，那么要找出第20亿个数是哪个。如果下标0中出现的数有1亿个，那么中位数绝对不可能出现在下标0代表的某个数中。
    • 假设统计0到170下标的数有19亿个，到171下标的数有23亿个，那么中位数肯定就是在171下标代表的某个数中。找到171下标中第一亿个数就是中位数。

题目四

有10GB大文件里面存放着无序有符号的整数，给你5GB空间，如何把这个无序变成有序。（腾讯面试题）

  • 思路：（先分桶再排序）
    • 1）用小根堆（每一个元素有数值，频次两个属性）来作为媒介遍历每一个文件段（5GB可以申请可以存储多大的小根堆），每一个小段进入小根堆后，输出小根堆到文件就可以了，然后总结果就是依次排序。
      • 可以申请多大的小根堆, 一个整型4字节，一条数据8字节(包括数据和频次)，假设堆还有其他占用，就位16字节，则堆长度为5 * 2 ^ 30 / 16 = 5 * 2 ^ 26向下取整2^27
      • 无符号数的范围是-2^31 ~ 2^31-1，假设一个范围是2^27, 则2^32 // 2^27 =等分成2^5份小范围
      • 利用小根堆统计最低范围出现的状况，比如第一个范围是-2^31 ~ -2^31+2^27-1, 第二个范围是-2^31+2^27 ~ -2^31+2^27 * 2 -1...
      • 每次过完一个范围的数，根据频次输出到文件，再搞定下一个范围的数，因为范围是小到大，并且利用了小根堆，所以总体有序
    • 2）最优解：用大根堆(数值，频次)
      • 大根堆的长度用5GB算出，并且定义一个Y值
      • 简单例子
        • 总共有10个数，创建一个只存放3个数的大根堆。然后依次遍历这十个数，比堆顶小进堆，比堆顶大就忽略，这个大根堆里面存放的是10个数中最小的3个数。
        • 然后输出有序的最小的3个数。此时记录排完序的3个数中最大的那个数Y
        • 清空大根堆后，继续去遍历这10个数，但是小于Y的就不要遍历了， 然后找出最小的3个数，然后输出
        • 一直重复就可以了。

results matching ""

    No results matching ""