海量数据相关题目

我不是女神ヾ 2023-06-22 13:59 6阅读 0赞

## 海量数据相关题目 ##

**1.100亿条数据，让找出出现次数最多的前k条记录？**

● 直接遍历统计比较

● 排序

● 将大文件分割

*  分割份数---->基准：内存要求
 *  平均分割----对每个分割后的小文件单独处理，基于每个小文件去统计每条记录出现的次数。
 *  **哈希切割**  
    文件编号：记录%文件总份数  
    **好处**：相同的记录将来都在一个小文件中  
    `Priority_queue`:找 top K

**2.有40亿个不重复的整数，快速检测一个数据是否在该集合中**

● 直接遍历

*  **缺点：多次I/O，效率低下。**

● 排序

● **切割-----哈希切割**

*  40亿个数据（不超过16G---->8份---->2G）
 *  可以通过**增加切割份数**来保证**内存不超过内存上限**

● 位图：用一个**比特位**的状态表示**数据存在与否的状态信息**（0，1）  
`(2^32)bit = (2^32/8)byte = (2^29)byte/（2^10(变成T)×2^10(变成兆)）=512兆`

*  **到底需要多少个比特位**：至少应该将所有的数据表示起来，根据数据的范围来确定需要比特位的个数
 *  **将数据向位图中映射**
    
     *  先计算该数据在位图的**哪个字节**（比如：在第n个字节）
     *  计算该数据在该字节的**哪个比特位**（比如：第m个比特位）
     *  **将第n个字节的第m个比特位置为1：字节(n)|(1<<m)**
 *  映射：数据范围不一定是从0开始的；若从0开始，直接映射；否则需要将数据范围中的每个数据-100再映射；比如数据范围\[100,200)。
 *  查找：直接到位置中**检测对应比特位是否为1** \------> O(1)

**置一**：0010 1101  
综合可得：将其与0001 0000（对0进行左移操作）进行或操作

位操作：
    |   或          ||  或
    &   与          &&  且
    ^  （异或）
    <<  左移        >>  右移
    ~   取反

**置零**：0011 1101  
综合可得：将其与1110 1111 进行与操作

**Tip：求五个字节数据的二进制格式中总共有多少个1 ？**

*  Vector : 18 45 78 21 33 快速-----哈希思想
 *  **最快速的方式：将0到255每个数字有多少个1全部罗列到一个bitCnttable\[256\]数组中，直接进行数据下标查找即可。** O(1) 计算出的数组可以直接在网上搜索得到

#include<iostream>
    #include<stdlib.h>
    #include <bitset>
    using namespace std; 
    void TestBitset()
    { 
    	std::bitset<100> t;	
    	t.set(1);	
    	t.set(50);	
    	//第50个比特位置1 
    	cout << t.size() << endl;	
    	//count ----- 可以计算数据中比特位为1的数字个数
    	cout << t.count() << endl;	
    	if (t.test(50))		
    		cout << "是1" << endl;	
    	else		
    		cout << "是0" << endl;	
    	//将50个比特位进行清零
    	t.reset(50);	
    	cout << t.count() << endl;	
    	if (t.test(50))
    			cout << "是1" << endl;	
    	else
    			cout << "是0" << endl;
    } 
    int main()
    { 
    	TestBitset();
    	system("pause");	
    	return 0;
    	}

**位图缺点**：无法处理重复的数字，只能处理存不存在之类的问题----对其进行变形操作。

## 位图应用 ##

#### **1. 给定100亿个整数，设计算法找到只出现一次的整数？** ####

*  数据有重复------找date是否存在---->可以直接应用位图
 *  找只出现一次的数据 **三种状态**
    
     *  没有出现 ；只出现一次；出现多次
 *  **位图：用1个比特位表示数据状态**
    
     *  **对位图进行变形----->可以用两个比特位表示一个数据状态 00 ,01,10,11**
     *  512×2 1G 的空间就可以表示所有整数集
     *  date/8:字节 -----> （两个比特位表示一个状态） date/4  
        date%8:对应相应的比特位 -----> date%4

**1.将数据映射到位图（2个比特位代表数据的状态）中**

*  Data对应的是那个字节的哪两个比特位

if(00)  
       01
    else if(01)
    	10

**2.从改变之后的位图中找只出现一次的数据从前往后两个两个比特位检测**

if（01）
       Cout<<”是只出现一次的数据”<<endl;

**eg** : 1 2 2 7 4 3 5 4 6 1  
从最高比特位开始，按照每个比特位进行划分，直到划分到不能再划分（只有一个比特位时）结束划分；找到存在一个数字的位置。

*  具体思路： 相册保存
 *  **总最高位开始，递归划分求解，直到比特位划分到最低位停止划分**

#### 2.给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？ ####

**法一：**

*  左边二进制位代表文件1； 右边二进制位代表文件2
 *  00 11 00 00
 *  文件1：将文件1中的数据向位图中进行映射
    
     *  **只映射第一次出现的**：2 2 （当第二次出现同一数字时，查询到已经赋过值，就不再修改）
     *  再映射到第二个文件
     *  如果**两个比特位同时为一**，说明该数据是两个文件的**交集**

**法二**：

*  文件1—> 将文件1中的数据**映射**到**位图**中 占用空间 ：512M
 *  文件2—> 将文件2中的数据映射到位图中 占用空间 ：512M
    
     *  位图可以求交集（&），求并集（|）  
        & ---------------------------------------------
     *  **保留最后所有为1的比特位**

**法三**：

*  哈希切割-----相对麻烦些

#### 3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。 ####

*  用**两个比特位**表示数据的状态
    
     *  00 没有出现；01 出现一次；10 出现两次；11 出现多次
 *  **data ----> data/4 ----> 找到字节** data%4 \*2 —> **找到比特位**

if(00)
         变成01
     else if(01)
        变成10
     else if(10)
        变成11

*  找出现次数**不超过两次**的数据：将比特位**两个两个进行检测**
    
     *  01或者10

#### 4. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？可不可以用位图解决，原因？ ####

*  将数据向位图中映射----> 将对象的**比特位置为1**
 *  找交集：用两个位图&-----> 检测结果为一的比特位
 *  假设query中存放的字符串，且用位图进行处理，需对其进行转化
    
     *  字符串转化为整形数据-----> **可能会转化成重叠的比特位置**  
        字符串哈希算法
 *  Tip：位图**不能处理**\-----> 可选用**布隆过滤器**、**哈希切割**…  
    位图只能处理带有明确数据的海量数据