【算法&数据结构体系篇class34】资源限制技巧汇总

淡淡的烟草味﹌ 2024-03-22 12:11 39阅读 0赞

### 一、资源限制技巧汇总 ###

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

###  ###

### 二、哈希函数可以把数据按照种类均匀分流 ###

> **题目一：**
> 
> 32位无符号整数的范围是0~4,294,967,295，
> 
> 现在有一个正好包含40亿个无符号整数的文件，
> 
> 可以使用最多1GB的内存，怎么找到出现次数最多的数？

>  **思路开展：**
> 
> 1.如果用int数组，int类型是4个字节大小，取出全部数据再进行排序，有40亿个数，空间就是40\*4=160亿Byte 大小，转换成16G，题意资源限制1G内存，显然是不符合的
> 
> 2.换个思路，我们可以用哈希表来存数，key是数，value是次数， 举个最好情况的例子，40亿个数，都是相同数，那么只需要一条键值对记录，Map<Integer,Integer>, 大小就是4+4=8Byte大小，最差情况，就是每个数都不一样，那么接着再优化，因为无符号整数范围是到42亿多，所以40亿个数可以每个数都不一样，因为都在42亿范围内，如果是40个不同数，需要的空间就是40亿\*8=320亿Byte大小，转换成32G，还不如第一种方式
> 
> 3.接着就是压缩空间思路，我们先考虑 1G能存放多少条数据，哈希表中前面已知一条数据就是4+4=8Byte大小，那么1G=1024\*1024\*1024Byte / 8 约等于 1亿多条记录，那么我们再计算上哈希表还存在的其他的一些消耗内存的数据空间索引等，我们就把这个记录再缩小10倍，这样就肯定不会让哈希表溢出，存放一千万条记录。
> 
> 4.40亿个数，假设1G空间只能处理一千万条数据， 那么我们就把 40亿/1千万 = 400，得到这个400的值，我们就对40亿个数，每个数都先用哈希函数计算出哈希值，哈希值再模400，得到的数就0到399，让这些数，都可以均分的落到0-399这些位置中，相同的一个数，得到的都是相同的输出，所以都是落在同一个值（0-399）中的 ，所以我们分别将值入0-399的位置后，用map先处理0位置的最大值，再清空map,处理1位置的最大值...直到将每个位置的数的value最大值得出，再将400个位置的最大值进行比较，得到最大的数。
> 
> 5.最终就是通过哈希进行将数据压缩，从大文件压缩到小文件，直到能保存在题目要求的1G内的文件，将40亿数拆分开

### **三、位图解决某一范围上数字的出现情况，并可以节省大量空间、利用分段统计思想、并进一步节省大量空间** ###

> **题目二：**
> 
> 32位无符号整数的范围是0~4,294,967,295，
> 
> 现在有一个正好包含40亿个无符号整数的文件，
> 
> 所以在整个范围中必然存在没出现过的数。
> 
> 可以使用最多1GB的内存，怎么找到所有未出现过的数

>  **思路开展：**
> 
> 1.找出没出现过的数，我们可以用HashSet集合，将40亿个数存放后，再依次遍历0-42亿多的数，没有包含在其中的数则为目标数，用Integer类型 整形大小的4B，\*40亿个，就是160亿B，转换成G 就是16G ，不符合题目要求的1G
> 
> 2.换个思路，我们可以用bit数组位图来存数，我们将无符号整数范围42亿多的全部数存放到bit数组中，转换内存 1Byte字节 = 8bit比特 内存就是42亿多/8 = 5亿多B，而1G转换大约10亿B，所以内存是完全足够的，比如int\[\]数组 一个元素整形是4字节B，对应就有32bit，表示一个元素可以存放32个数， arr\[0\] ----- 表示0-31的数 arr\[1\] ----表示32-63的数... 比如数3，存放在3/32=0 ，arr\[0\]位置上，0位置上有32位 ，存放在3%32=3 3位置 1000 二进制第四位赋值1 就表示3的数存在，依次把全部42亿多的数都填充赋值好1
> 
> [这里可以看看之前写的一篇bit位图][bit]

> 【进阶】**内存限制为 3KB，但是只用找到一个没出现过的数即可**
> 
> **【思路】：分成512份 利用分段统计思想、并进一步节省大量空间**
> 
> **1. 3KB 假设是用Int\[\]整形数组存放，一个int是4字节，3000/4 = 750个长度，数组长度不超过750,就不会溢出3KB内存空间，接着我们在取一个离750最近且小于的值，该值是2的某次方 就是512，作为该数组的实际长度，为了后续方面计算所以需要用2的某次方作为长度**
> 
> **2.接着 把42亿多的数据 也就是2的32次方个数 均分成 512份，这样就能整除2的32次方 / 8 = 8388608， 每份就是存放8百万多个数，分别统计全部的数值，而我们目标是40亿个数，而整个512份是存放43亿个数，这样就肯定存在某个份位置是不满8百万多的数，我们找到任意一个，可以在继续对其分512份，直到能找到某个数是不在文件内的 返回题意要求的即可。**

> **【扩展】要求在有限变量个数情况下，得到一个没出现过的数**
> 
> **【思路】： 二分 利用分段统计思想、并进一步节省大量空间**
> 
> **1.范围还是0 到 2的32次方-1 定义L在0位置 R在2的32次方-1 再定义MID中点**
> 
> **2.判断左侧区间 和右侧区间 哪个区间是不够2的31次方个的，就说明不存在的数就在那个区间，接着对其区间进行二分，直到最后找到该数 不在文件内的即可返回**

### 四、布隆过滤器用于集合的建立与查询，并可以节省大量空间、哈希函数可以把数据按照种类均匀分流 ###

> **题目三：**
> 
> 有一个包含100亿个URL的大文件，假设每个URL占用64B，
> 
> 请找出其中所有重复的URL
> 
> 【补充】
> 
> 某搜索公司一天的用户搜索词汇是海量的(百亿数据量)，
> 
> 请设计一种求出每天热门Top100词汇的可行办法

> **思路：** 
> 
> **如果能接受一定的失误率，我们可以采用布隆过滤器来实现，通过布隆过滤器依次将每个URL都对应存放在bit数组中进行描黑标记，后续如果有重复的，就会再次遇到标记位。**
> 
> **不能有失误率，那么我们就依次将大文件每个URL进行哈希函数的分到小文件，如果小文件还不够的话，可以继续哈希到更小文件，检查每个小文件是否有重复的URL,因为同样的URL，都是会进同一个文件的**

### 五、题目四 ###

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

> **思路：**
> 
> **1.将两个bit位作为一个数，比如 数组 0，1下标 表示 数1的次数** 
> 
> **当状态是00 则表示数1 次数0， 01表示 数1 出现次数1， 10表示数1出现次数2， 11表示数1出现次数大于2次。**
> 
> **2.这样将全部42亿多个数都标记好了，在判断 每两个位置 值是 1 0 就表示出现次数2**
> 
> **3.范围是 0 - 2的32次方-1 一共就是2的32次方个数， 每个数需要2bit 那么就是需要2的33次方长度的bit数组， 再除以8 转换成byte字节 2 ^33 / 8 = 1亿多Byte 也即是1G 刚好够内存**

### 六、题目五 ###

> 32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数
> 
> 可以使用最多3K的内存，怎么找到这40亿个整数的中位数？

> **【思路】：分成512份 利用分段统计思想、并进一步节省大量空间**
> 
> **1. 3KB 假设是用Int\[\]整形数组存放，一个int是4字节，3000/4 = 750个长度，数组长度不超过750,就不会溢出3KB内存空间，接着我们在取一个离750最近且小于的值，该值是2的某次方 就是512，作为该数组的实际长度，为了后续方面计算所以需要用2的某次方作为长度**
> 
> **2.接着 把42亿多的数据 也就是2的32次方个数 均分成 512份，这样就能整除2的32次方 / 8 = 8388608， 每份就是存放8百万多个数，分别统计全部的数值，而我们目标是40亿个数，而整个512份是存放43亿个数，这样就肯定存在某个份位置是不满8百万多的数，我们找到任意一个，可以在继续对其分512份，直到能找到某个数是不在文件内的 返回题意要求的即可。**
> 
> **3.依次将0-8388607 的数存放到 第一份； 8388608-16777215 的数存放到 第二份 以此类推**
> 
>  **中位数就是按顺序存放好数之数 在中间位置。也就是40亿数排序后的 第20亿个数，依次从第一份开始看有多少个数，直到某一份 累加起来是到了20亿的 说明中位数就在这份位置中，然后继续接着找对应的位置。 比如第一份存放了1亿个数，第二份存放了18亿个数，第三份存了2亿个数，这里第三份就达到了20亿个数了，就是存在第三份中 第一亿个数 就是整体的中位数值**

###  七、题目六 ###

> 32位无符号整数的范围是0~4294967295，
> 
> 有一个10G大小的文件，每一行都装着这种类型的数字，
> 
> 整个文件是无序的，给你5G的内存空间，
> 
> 请你输出一个10G大小的文件，就是原文件所有数字排序的结果

> **思路： 利用堆、外排序来做多个处理单元的结果合并**
> 
> **1.定义一个大根堆，5G的内存空间，我们假设是 空间容器存放3条记录 ,每条记录有 数值，出现次数， 都是定义Integer类型 4+4=8字节的大小**
> 
> **2.按照数值的大小排序 大根堆，过一遍文件，到了三条记录后，比如存在** 
> 
>  **\[3,10万次\]，\[6,12万次\],\[9,18万次\] 接着来第四个数，是8，小于最大堆顶9 ，就替换9 8入堆，接着来第五个数，10，比堆顶大，不刷新，以此类推，过一遍文件，堆中存放的就是文件前三小的数，依次将小往大 输出到输出文件**
> 
> **3.然后用变量保存堆顶数值 8， 然后清空堆，接着第二遍遍历文件，把大于8 的值再入堆，因为小于等于8的已经处理好入文件了，接着去判断大于8的后面的数，依次再入堆，遍历完之后，再保存当前堆顶 变量值刷新，进行第三遍遍历...直到堆不满3条，就来到最后一次，循环结束**

### 八、题目七 ###

> 在一个大文件中，取出出现次数最多的前100个数

> **思路： 哈希函数可以把数据按照种类均匀分流**
> 
> **1.大文件按照限制条件，进行哈希，哈希分别带入多个小文件，均分在每个小文件，对每个小文件中求 数出现次数最多的前100个数，因为哈希分布，相同数的多个 只会落到同一个小文件中**
> 
> **2.对每个小文件的前100个数，进行外排序，依次取出每次比较多个文件的最大值， 直到取出前100个**
> 
> **3.或者对每个小文件的前100个数 都形成一个大根堆，然后再将每个小文件的堆顶形成一个大根堆A，每次弹出大根堆A,然后记录弹出的值所在的小文件，再将该堆下个值 入大根堆A，排列下个大的值，再弹出堆顶，依次类推，最后取出前100个**

代码演示该堆类：

package class34;
    
    import java.util.HashMap;
    import java.util.PriorityQueue;
    
    public class TestHeap {
    
    
        // 根据课上的说法，小于limit的数字不再接收
        public int limit;
    
        // 根据内存大小决定k的大小
        // k的含义是 : 堆里最多留多少条记录
        public int k;
    
        // 在堆里的元素，建立词频表
        // 只有在堆里的元素才有词频表
        public HashMap<Integer, Integer> cnts = new HashMap<>();
    
        // 建立大根堆，维持最小的K个数
        public PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
    
        public TestHeap(int a, int b) {
            limit = a;
            k = b;
        }
    
        // 核心方法 :
        // 逐行读文件，遇到一个数字num的时候
        // 该怎么处理
        public void add(int num) {
            if (num <= limit) {
                // 如课上所说
                // 遇到 <= limit的数字，忽略
                // 因为这个数字之前一定处理过了，已经写入有序文件了
                return;
            }
            if (cnts.containsKey(num)) {
                // 如果当前数已经在堆里，直接增加词频即可
                cnts.put(num, cnts.get(num) + 1);
            } else {
                // 如果当前数不在堆里
                if (heap.size() < k) {
                    // 如果堆没有满
                    // 那么直接加入即可
                    heap.add(num);
                    cnts.put(num, 1);
                } else {
                    // 如果堆满了
                    // 那么要看能不能入围
                    if (heap.peek() > num) {
                        // 如果num比堆顶小，那么就可以入围
                        // 堆顶被淘汰
                        cnts.remove(heap.peek());
                        heap.poll();
                        // 当前数进来
                        cnts.put(num, 1);
                        heap.add(num);
                    }
                }
            }
        }
    
        // 返回目前堆里维持的最小的K个数字，及其词频表
        // 可以用这个哈希表去生成有序文件
        public HashMap<Integer, Integer> getRecord() {
            return cnts;
        }
    
    }

[bit]: https://blog.csdn.net/studyday1/article/details/128713821?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168327247716800188561689%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=168327247716800188561689&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-128713821-null-null.blog_rank_default&utm_term=%E4%BD%8D%E5%9B%BE&spm=1018.2226.3001.4450