背景

昨天在刷 AcWing 每日一题的第 3732 题「矩阵复原」时，发现在大容量数组作为缓存时提交无限 TLE，但是该用 HashMap 就 ac 了。

在我浅薄的知识勺中，一直认为数组的下标作为 key 随机访问其下标的元素数据时是要快于一些集合的，HashMap 有着复杂的数据结构，底层也是数组、链表和红黑树，怎么样都不会比一维数组作为缓存来的快吧，但实际上在该背景下确实是 HashMap 的效率更高。

来看这段算法的代码：

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

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        while (k-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] mat1 = new int[n][m];
            int[][] mat2 = new int[m][n];
            // int[] cache = new int[250001];
            Map<Integer, Integer> map = new HashMap<>();
            int[][] res = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    mat1[i][j] = sc.nextInt();
                    // cache[mat1[i][j]] = j;
                    map.put(mat1[i][j], j);
                }
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    mat2[i][j] = sc.nextInt();
                    // res[j][cache[mat2[i][j]]] = mat2[i][j];
                    res[j][map.get(mat2[i][j])] = mat2[i][j];
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                sb.setLength(0);
                for (int j = 0; j < m; j++) {
                    sb.append(res[i][j]).append(" ");
                }
                System.out.println(sb.toString());
            }

        }
    }
}

注释的地方是原先 TLE 的代码，只通过了大概 9 个 case（一共 11 个）。为什么会出现这样的情况呢？查阅了网上少量的资料和群友的解释大概是 CPU 高速缓存的命中问题，初始化需要分配的连续内存太大，造成CPU高速缓存整个缓存行失效，大大的降低了高速缓存的命中性。

可惜大学学的东西早忘完了，寻址算法都记不清了。这次正好也让我学习了在算法题中对于大数组的使用要谨慎，并非使用数组利用下标读写就是效率最高的。

2021.7.2 更新

以上那段代码，我尝试在 HashMap 的初始化设定一个容量，就像这样：Map<Integer, Integer> map = new HashMap<>(250000 * 4 / 3 + 1); 发现这样果然超时了，感觉 TLE 的原因就在于初始化分配的大小。在数据量较小的 case 上，「一直扩容」是会比初始化过大的容量（250000）快的， TLE 应该是在一些数据量较小的 case 上。

Map<Integer, Integer> map = new HashMap<>(n * m * 4 / 3 + 1) 这样写性能是最强的，用时最少。所以效率排名是这样的：

1. Map<Integer, Integer> map = new HashMap<>(n * m * 4 / 3 + 1)
2. Map<Integer, Integer> map = new HashMap<>()
3. int[] cache = new int[n * m + 1];
4. int[] cache = new int[250001];

HashMap 居然比数组随机读写的速度还要快，泪目，HashMap 永远滴神！

2021.7.6 更新

在复习《Redis核心技术与实战》这门课的时候，评论区的同学都非常厉害，老师抛出了一个问题：

如果在数组上是随机访问，对CPU高速缓存还友好不？

虽然是关于 Redis 的数据结构，但是其实本质和我们这道算法题碰到的问题类似，其中一个同学的解答非常好，我就直接在抄过来了

@irats:

数组通过下标访问数据虽然是O(1)，但是由于cpu读取数据从高速缓存读，而高速缓存的容量很小。

比如cpu要读取nums[0]，cpu发现高速缓存没有nums[0]，就会从内存把num[0]以及nums[0]附近的数据(比如还拖取了nums[1])都拖取到高速缓存中。如果接下来cpu要读取nums[1]，由于nums[1]已经在告诉缓存中，那么cpu能马上拿到数据。但如果cpu想要读取nums[100]，显然高速缓存中没有这个数据，然后就又要到内存中把nums[100]和他附近的数据拖到高速缓存。假设高速缓存只能存两个数字。那么因为读取nums[100]，就会把原本在nums[0]的数据替换掉。如果接下来cpu又读nums[0]。。那么就又要从内存中获取。

也就是说，老师问的对cpu友好，说的并不是你理解的时间复杂度。而是对于这种从高速缓存读取数据的行为。顺便说一句，在《深入理解操作系统中》中把要读取的数据附近的数据一起拖到高速缓存的行为，叫空间局部性。

• ← Previous Post
• Next Post →