设计方案总结

2024-06-10 20:44

文章标签 总结设计方案

本文主要是介绍设计方案总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2G 内存在 20 亿个整数中找出现次数最多的数

案例分析：
- 整数占用 4个字节。
- 整数的范围是 -21亿 ~ 21亿。
- kv 对需要 8个字节，k 存储整数，v 存储出现次数。
- 存储 20亿个整数需要 16G内存。
数据存储使用散列表。
分治：
- 要将一个大文件拆分成若干个小文件。
  - 同一个数字不能分布在多个文件中。
  - 20亿个整数能够均衡分布在多个文件中。
  - 通过 hash 运算实现。
    - 因为同一个数字经过运算会得到相同的值，可用于数据分流
    - hash 算法具备随机性 → 将大文件中的数据均衡分布在多个小文件中；siphash → 近似的 key 通过哈希函数会得到反差很大的值。
  - 建议拆分为 16个文件，这样每个文件大体上需要占用 1G内存。
    - 考虑 hash 不均衡的情况。
    - 考虑散列表扩容的情况。
    - 为了优化取余运算，要找一个恰好大于 10 的 $2^n$ ，即 $2^4$ 。
      - x % 16 = x & (16 - 1)
- 分别统计单个文件中的最大值，最终得到整体的最大值。
优化：如果某个数出现次数超过 10亿了，直接返回这个数，无需继续统计。
如果是 40亿个整数 ?
- 拆分出更多的文件。
- 出现次数 value 起始值不能为 0，可以为 -20亿。
如果是 80亿个整数 ?
- 拆分出更多的文件。
- 出现次数 value 起始值不能为 0，可以为 -20亿。
- 因为某个数出现次数超过 40亿的时候，无需继续统计。

100 亿个 URL 中重复词汇的 TOP K 问题

题目：一个包含 100 亿条 URL 的大文件，每个 URL 占用 64 个字节，找出重复的 URL。
附加：某搜索公司每天需要处理海量搜索词汇，设计一个找出每天热门 Top 100 词汇的可行方法。
解决方案：hash 分流 + 散列表词频统计。
询问资源限制：内存、时间、机器。
hash 分流：
- 把大文件拆分为若干个小文件。
- hash 运算特征：同一个 key 反复 hash 运算总是得到同一个值。
- hash 算法具备随机性 → 将大文件中的数据均衡分布在多个小文件中。
- 把大文件分流到多台机器中处理。
时间限制：
- 使用散列表进行词频统计。
- 为什么不使用平衡二叉树（红黑树）?
  - 因为不要求有序。
Top K 问题：
- 此时是否使用平衡二叉树来统计 ?
  - 只要求一部分有序，不使用平衡二叉树。
- 维护一个大小为 K 的最小堆。

40 亿个非负整数中找到未出现的数

题目：最多使用 1GB 内存，怎么找到所有未出现过的数。
进阶：内存限制为 10MB，只需找到一个没出现过的数即可。
解题思路：
- 非负整数范围：0 ~ 42.9亿之间，那么有接近 3亿的数字未出现。
- 散列表：40亿 * 4B = 16G。
- 位图：大概需要 537MB 空间。
  - unsigned char arr[536870911];
  - x / 8 得到数组索引值，也就是 unsigned char 的一个值 value。
    - 因为每个 unsigned char 存储 8位。
  - x % 8 得到具体位，value = value | 1 << bit;。
  - 将 40亿个数字执行前两步后进行整体遍历，如果某一位不为 1，则该数字未出现过。
如果内存限制为 10MB：
- 问题拆分：537 / 10 = 53.7份，至少需要拆分为 54份数据。
- 为了优化除法运算，找一个恰好大于 54 的 $2^n$ ，即 $2^6$ 。
  - 除以 64 可以优化为右移 6 位。
- 解题思路：
  - 准备一个数组 unsigned int arr[64]，每个区间的数字个数为 67108864。
  - 将某个数字对 67108864 整除，相当于右移 26位，得到的值肯定在 0 ~ 63 之间。
  - 假设得到的是 x，arr[x]++。
  - 将 40亿个数字经过上面运算，找出 arr[i] < 67108864，这样找出 i 区间有未出现的数字。
  - 接着对 i 区间的数字使用位图，找出未出现的数字即可。