# 大规模数据场景

针对百万或者几十亿的数据的场景。

# 位存储

使用位存储，使用位存储最大的好处是占用的空间更小。

# 1. 使用 4KB 内存查找重复元素

题目要求：给定一个数组，包含从 1 到 N 的整数，N 最大为 32000，数组可能还有重复值，且 N 的取值不定，若只有 4KB 的内存可用，该如何打印数组中所有重复元素。

如果只有 4KB 的空间，那么只能寻址 8*4*2^10 位，这个值比 32000 要大的，因此我们可以创建 32000 位的位向量 (比特数组)，其中一个比特位置就代表一个整数。

	func printDuplicates(arr []int) {
	bitArray := make([]bool, 32001) // 创建 32001 位的位向量，默认值为 false

	for _, num := range arr {
	if bitArray[num] {
	fmt.Println(num) // 打印重复的元素
	} else {
	bitArray[num] = true
	}
	}
	}

	func main() {
	arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 5, 6, 7} // 示例输入数组
	printDuplicates(arr)
	}

# 2. 从 40 个亿中找到一个不存在的整数

判断可行性，40 亿位的数组需要占用多少内存。

4000000000/8/1000/1000 = 500MB 大约占用 500MB 内存

建立一个长度为 40 亿的位数组

	func generateMissingNumber() int {
	const size = 4000000000

	bitArray := make([]bool, size) // 创建长度为 40 亿的位数组，默认值为 false

	// 随机填充位数组
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < size-1; i++ {
	num := rand.Intn(size - 1)
	bitArray[num] = true
	}

	// 寻找第一个为 false 的位置
	for i := 0; i < size-1; i++ {
	if !bitArray[i] {
	return i
	}
	}

	return -1 // 如果找不到不存在的整数，返回 - 1
	}

	func main() {
	missingNumber := generateMissingNumber()
	fmt.Println("Missing number:", missingNumber)
	}

# 3. 40 亿个数中找到出现两次的数

题目要求：32 位无符号整数的范围是 0～4 294 967 295，现在有 40 亿个无符号整数，可以使用最多 1GB 的内存，找出所有出现了两次的数。

所有出现过两次的数字，所以我们可以用两个位去标识一个数出现的次数。

可行性分析，占用空间为 (2^32)/8/1000/1000*2 ≈ 1000MB

建立一个长度为 (2^32)*2 的数组，遍历所有数，
当遍历到第 1 次的时候，把 bitArr[num*2+1] 和 bitArr[num*2] 设置为 01
当遍历到第 2 次的时候，把 bitArr[num*2+1] 和 bitArr[num*2] 设置为 10
当遍历到第 3 次的时候，把 bitArr[num*2+1] 和 bitArr[num*2] 设置为 11
之后无论遍历到多少次，就不做任何操作。

所有数遍历完成了之后，重新遍历，如果发现 bitArr[num*2+1] 和 bitArr[num*2] = 10 就是出现了两次

# 分块处理

如果文件实在太大，无法在内存中放下，则需要考虑将大文件分成若干小块，先处理每个块，最后再逐步得到想要的结果，这种方式也叫做外部排序。这样需要遍历全部序列至少两次，是典型的用时间换空间的方法，

# 4. 从 40 个亿中产生一个不存在的整数，限制内存为 10MB

可行性分析，没办法使用位图。

40 亿个数需要 500MB，10MB 空间的话至少分成 50 块，一般都是按照 2 的整数倍来划分，所以我们划分成 64 块。

(2^32) 约 40 亿平均分成 64 个区间，每个区间的数量为 (2^26) 个

具体流程为：

第一次遍历，创建一个长度为 64 的数组，用于统计区间 i 上的数有多少；
遍历到的数除以 (2^26) 得到对应的区间，之后对应的区间数组的统计值 + 1；
遍历完所有数之后，必然有某个区间的数字小于 (2^26) 。
找到这个区间，假设这个区间为 partNum ，然后第二次遍历。申请长度为 (2^26) 的位数组。
遍历到的数除以 (2^26) ，只处理商为 partNum 的值， num/(2^26)==partNum
遍历完所有数之后，在位数组内必然存在有个值没被设置为 1

# 5. 用 2GB 内存在 20 亿个整数中找到出现次数最多的数

题目要求：有一个包含 20 亿个全是 32 位整数的大文件，在其中找到出现次数最多的数。
要求，内存限制为 2GB。

可行性分析，直接读到内存里，使用哈希表。假设哈希表的 key 是 32 位 int 占 4B 内存，哈希表的 value 是 32 位 int 占 4B 内存，一条不重复的记录占用 8B，如果哈希表的记录为 20 亿个，占用内存 2000000000*8/1000/1000/1000 = 16GB

所以我们需要把这 20 亿个数通过哈希函数分成不同的小文件。这边我们分成 16 个小文件。相同的数通过同一个哈希函数之后，都会落入相同的文件中。

具体流程为：

遍历 20 亿个数，根据哈希函数算出哈希值，然后对 16 取模，进入到不同的小文件中。
找到每个小文件中出现最多的数，对这几个数进行对比，找到出现最多的数。

# 6. 对 20GB 文件进行排序

题目要求：假设你有一个 20GB 的文件，每行一个字符串，请说明如何对这个文件进行排序？

我们将文件划分成一些块，每块大小是 xMB，x 就是可用内存的大小，例如 1GB 一块，那我们就可以将文件分为 20 块。我们先对每块进行排序，然后再逐步合并。这时候我们可以使用两两归并，也可以使用堆排序策略将其逐步合并成一个。

# 7. 从 100 亿个 URL 中查找的问题

题目要求：有一个包含 100 亿个 URL 的大文件，假设每个 URL 占用 64B，请找出其中所有重复的 URL。

可行性分析，所有文件占用存储大小为 10000000000*64/1000/1000/1000 = 640GB

同上，我们需要大文件通过哈希函数拆分成小文件，然后再进行处理。

比如拆成 128 个小文件，如果哈希函数足够优秀的话，每个文件约 5GB

后续流程略

# 堆

如果在超大数据中找第 K 大、第 K 小，K 个最大、K 个最小，则特别适合使用堆来做。

而且将超大数据换成流数据也可以，而且几乎是唯一的方式，口诀就是 “查小用大堆，查大用小堆”

# 8. 从 100 亿个 URL 中找到出现次数 Top 100 的 URL

同上，将大文件拆分成小文件之后。我们可以把不同的小文件的 top100 进行处理合并处理，直到合并完所有的 top100。

合并方法使用小顶堆来实现，

# 9. 从 10 亿数字中寻找最小的 100 万个数字

为前 100 万个数字创建一个大顶堆，最大元素位于堆顶。

然后，遍历整个序列，只有比堆顶元素小的才允许插入堆中，并删除原堆的最大元素。

之后继续遍历剩下的数字，最后剩下的就是最小的 100 万个。

数据结构算法