Java编程如何高效利用CPU缓存?

首先我们来看一个Java的例子:

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
/**
* @author Shuai Junlan[shuaijunlan@gmail.com].
* @since Created in 1:43 PM 1/17/19.
*/
public class ArrayTraverse {
private static long[][] arrs = new long[1024*1024][8];
public static void main(String[] args) {
long temp = 0;
long start = System.currentTimeMillis();

// Vertical traverse
for (int i = 0; i < 8; i ++){
for (int j = 0; j < 1024 * 1024; j++){
temp = arrs[j][i];
}
}
System.out.println("Vertical traverse spending time: " + (System.currentTimeMillis() - start) + "ms");

start = System.currentTimeMillis();
// Horizontal traverse
for (int i = 0; i < 1024 * 1024; i++){
for (int j = 0; j < 8; j++){
temp = arrs[i][j];
}
}
System.out.println("Horizontal traverse spending time: " + (System.currentTimeMillis() - start) + "ms");
}
}

上述代码中定义了一个二维数组,分别从横向遍历和纵向遍历了;两个方面来计算耗时,相信通过上面的代码大家也都能知道两种遍历方式耗时差距很大,结果确实是这样的:

1
2
Vertical traverse spending time: 75ms
Horizontal traverse spending time: 13ms

看上面的输出结果,耗时差距确实很大,但是为什么会有这个大的差距呢?显然跟我们这篇文章的题目有关,那就是横向遍历充分利用了CPU高速缓存机制,使得遍历速度要快于纵向遍历,那么……

基于HashMap和双向链表实现LRUCache

使用HashMap和双向链表实现LRUCache,HashMap用来定位节点是否已经存在,时间复杂度为O(1),双向链表用来用来实现LRU规则,移动节点的时间复杂度也是O(1),代码如下:

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×