开放式数据量级问题

发表于 更新于 分类于 阅读次数：

TOPK

堆排序

维护一个 n = k 的堆 PriorityQueue，for i < 数据量级来元素就加进去，如果超过了 k，就poll 堆顶元素

时间复杂度就是 数据量级 log K

空间复杂度，因为堆本质其实就是一数组，空间为 O k

类似快排法

使用hash

对于这种问题

字典树

混合查询

有一批文件，每个文件里面有很多单词，如何快速统计所有单词的出现次数?

数据重复、是否存在问题

位图

bitmap 其实就是对HashSet或者数组的一个压缩版

Java的BItSet

海量数据的极致优化还有 压缩位图

布隆过滤器

解决 return true 就表示 可能在 和 return false 就表示 一定不在的

解决的业务问题：

找出排名前500的数

方法 思路 时间复杂度 空间复杂度 优劣
方法1：逐个归并（维护 top500） 先取第一个数组的后500个，然后与后续数组逐个合并，再保留最大500个 每次合并 500 + 500 → O(500)，共 10000 次 → O(10000 × 500) = 5×10⁶ ≈ 5M O(500) 简单稳定
方法2：多路堆（K 路最大堆） 每个数组取最后一个元素（最大值）放入大顶堆，每次弹出一个并往回移动指针 每次堆操作 log10000，执行500次 → O(500 × log10000) ≈ 500 × 14 = 7000，外加初始化堆 10000 → 10000log10000≈ 140000 → 总约 15 万 O(10000 + 500) 性能最优

堆本质上就是一颗完全二叉树

多路堆，最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.*;

public class Top500FromSortedArrays {

    static class Node {
        int value;      // 元素值
        int row;        // 来自哪个数组
        int index;      // 在该数组中的下标（倒序移动）
        
        Node(int value, int row, int index) {
            this.value = value;
            this.row = row;
            this.index = index;
        }
    }

    public static List<Integer> top500(int[][] arrs) {
        int k = arrs.length;  // 数组个数 (10000)
        PriorityQueue<Node> maxHeap = new PriorityQueue<>(
                (a, b) -> b.value - a.value   // 大顶堆
        );

        // 初始化：每个数组的最后一个元素入堆
        for (int i = 0; i < k; i++) {
            int lastIndex = arrs[i].length - 1;
            maxHeap.offer(new Node(arrs[i][lastIndex], i, lastIndex));
        }

        List<Integer> result = new ArrayList<>(); // 存前500
        for (int count = 0; count < 500 && !maxHeap.isEmpty(); count++) {
            Node top = maxHeap.poll();
            result.add(top.value);

            // 往前移动一个位置，继续加入该数组的下一个大值
            if (top.index - 1 >= 0) {
                maxHeap.offer(new Node(arrs[top.row][top.index - 1], top.row, top.index - 1));
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // 构造一个简单的测试用例 (真实情况是10000×500，这里只演示)
        int[][] data = {
                {1, 3, 5, 7, 9},
                {2, 4, 6, 8, 10},
                {11, 12, 13, 14, 15}
        };

        System.out.println(top500(data));  // 输出最大的前5个
    }
}

两个大文件中找出共同URL

64 byte * 50 亿 ，一个文件 320g 全加载到内存 建立Hash表，那肯定是不现实的。

还是 分治

对A ：hash(url) % 1000 -> 1000个小文件 命名为 a0,a1,a2….. a999

对B：同样，hash一定得相同

那么a99 和 b99里面可能存在相同的。但a99和a98里面的就不可能出现相同的

然后再把小文件加载到内存，建立hashmap