|
我们在实现 List 时，通常会考虑使用 ArrayList 和 LinkedList ,Vector 属于遗留代码类库，已不推荐使用。
下面，我们将以 List 的各种常用操作作为测试指标，验证 ArrayList 和 LinkedList 两者的性能指标。
0.准备工作
在此之前，先定义好测试模板，更好的帮助我们编写测试代码；
ContainerTest 为一个通用的测试基类，用泛型来兼容 ArrayList 和 LinkedList；再定义抽象方法 test()，便于我们自定义各种需要测试的方法。
public abstract class ContainerTest<T extends List> {
private T list;
public abstract long test();
public ContainerTest(T list) {
this.list = list;
}
public T getList() {
return list;
}
public void setList(T list) {
this.list = list;
}
}
与此同时，拥有一个生成测试数据的工具类 InitIntegerList 也是相当的有必要；
public class InitIntegerList {
public static <T extends List> T initList(T list, int size) {
list.clear();
for (int i = 0; i < size; i++) {
list.add(i);
}
return list;
}
}
接下来，编写提供各种测试功能 ListPerformanceTest 工具类。其中 initList() 用于生成测试数据；displayHead() 打印测试信息的表头；
public class ListPerformanceTest {
public static <T extends List> T initList(T list, int size) {
List initList = InitIntegerList.initList(list, size);
list.addAll(initList);
return list;
}
public static <T> void displayHead(T t, String methodName) {
System.out.println(t.getClass().getSimpleName() + "\t" + methodName);
System.out.println("集合长度\t操作次数\t平均时间");
}
后续编写的方法都是在 ListPerformanceTest 内运行，重复的部分不再贴出来了。每次执行测试方法后，打印方法执行次数、集合长度、平均操作时间作为参考，在随机测试方面，指定 Random 随机种子，保证每次随机取得元素的一致性。
1.顺序添加
public static <T extends List> void add(T list, int loops) {
ContainerTest<T> testList = new ContainerTest<T>(list) {
@Override
public long test() {
long startTime = System.nanoTime();
T t = getList();
for (int i = 0; i < loops; i++) {
t.add(i);
}
return System.nanoTime() - startTime;
}
};
long operateTime = testList.test();
long avg = operateTime / loops;
System.out.println(list.size() + "\t" + loops + "\t" + avg);
}
public static void main(String[] args) {
Integer[] integers = {10000, 30000, 50000};
ArrayList<Integer> arrayList = new ArrayList<>();
displayHead(arrayList, "顺序添加");
for (int i = 0; i < integers.length; i++) {
add(arrayList, integers[i]);
}
System.out.println();
LinkedList<Integer> linkedList = new LinkedList<>();
displayHead(linkedList, "顺序添加");
for (int i = 0; i < integers.length; i++) {
add(linkedList, integers[i]);
}
}
ArrayList 顺序添加
集合长度 操作次数 平均时间
10000 10000 149
40000 30000 70
90000 50000 51
LinkedList 顺序添加
集合长度 操作次数 平均时间
10000 10000 60
40000 30000 31
90000 50000 27
2.中部添加
public static <T extends List> void addHalf(T list, int loops, int size) {
ContainerTest<T> testList = new ContainerTest<T>(list) {
@Override
public long test() {
long startTime = System.nanoTime();
T t = getList();
for (int i = 0; i < loops; i++) {
t.add(size / 2, i);
}
return System.nanoTime() - startTime;
}
};
long operateTime = testList.test();
long avg = operateTime / loops;
System.out.println(size + "\t" + loops + "\t" + avg);
}
public static void main(String[] args) {
Integer[][] integers = {{100, 10000}, {200, 30000}, {300, 50000}};
ArrayList<Integer> arrayList = new ArrayList<>();
displayHead(arrayList, "中部添加");
for (int i = 0; i < integers.length; i++) {
arrayList = initList(new ArrayList(), integers[i][1]);
addHalf(arrayList, integers[i][0], integers[i][1]);
}
System.out.println();
LinkedList<Integer> linkedList = new LinkedList<>();
displayHead(linkedList, "中部添加");
for (int i = 0; i < integers.length; i++) {
linkedList = initList(new LinkedList(), integers[i][1]);
addHalf(linkedList, integers[i][0], integers[i][1]);
}
}
ArrayList 中部添加
集合长度 操作次数 平均时间
10000 100 2061
30000 200 5779
50000 300 5098
LinkedList 中部添加
集合长度 操作次数 平均时间
10000 100 17215
30000 200 30818
50000 300 32258
3.头部添加
public static <T extends List> void addHead(T list, int loops, int size) {
ContainerTest<T> testList = new ContainerTest<T>(list) {
@Override
public long test() {
long startTime = System.nanoTime();
T t = getList();
for (int i = 0; i < loops; i++) {
t.add(0, i);
}
return System.nanoTime() - startTime;
}
};
long operateTime = testList.test();
long avg = operateTime / loops;
System.out.println(size + "\t" + loops + "\t" + avg);
}
public static void main(String[] args) {
Integer[][] integers = {{100, 10000}, {200, 30000}, {300, 50000}};
ArrayList<Integer> arrayList = new ArrayList<>();
displayHead(arrayList, "头部添加");
for (int i = 0; i < integers.length; i++) {
arrayList = initList(new ArrayList(), integers[i][1]);
addHead(arrayList, integers[i][0], integers[i][1]);
}
System.out.println();
LinkedList<Integer> linkedList = new LinkedList<>();
displayHead(linkedList, "头部添加");
for (int i = 0; i < integers.length; i++) {
linkedList = initList(new LinkedList(), integers[i][1]);
addHead(linkedList, integers[i][0], integers[i][1]);
}
}
ArrayList 头部添加
集合长度 操作次数 平均时间
10000 100 4900
30000 200 11711
50000 300 10227
LinkedList 头部添加
集合长度 操作次数 平均时间
10000 100 419
30000 200 517
50000 300 274
4.随机添加
public static <T extends List> void addRandom(T list, int loops, int size) {
ContainerTest<T> testList = new ContainerTest<T>(list) {
@Override
public long test() {
Random random = new Random(47);
long startTime = System.nanoTime();
T t = getList();
for (int i = 0; i < loops; i++) {
t.add(random.nextInt(size), i);
}
return System.nanoTime() - startTime;
}
};
long operateTime = testList.test();
long avg = operateTime / loops;
System.out.println(size + "\t" + loops + "\t" + avg);
}
public static void main(String[] args) {
Integer[][] integers = {{100, 10000}, {200, 30000}, {300, 50000}};
ArrayList<Integer> arrayList = new ArrayList<>();
displayHead(arrayList, "随机添加");
for (int i = 0; i < integers.length; i++) {
arrayList = initList(new ArrayList(), integers[i][1]);
addRandom(arrayList, integers[i][0], integers[i][1]);
}
System.out.println();
LinkedList<Integer> linkedList = new LinkedList<>();
displayHead(linkedList, "随机添加");
for (int i = 0; i < integers.length; i++) {
linkedList = initList(new LinkedList(), integers[i][1]);
addRandom(linkedList, integers[i][0], integers[i][1]);
}
}
ArrayList 随机添加
集合长度 操作次数 平均时间
10000 100 3934
30000 200 6010
50000 300 6568
LinkedList 随机添加
集合长度 操作次数 平均时间
10000 100 12981
30000 200 15777
50000 300 17045
5.迭代遍历
public static <T extends List> void iter(T list, int size) {
ContainerTest<T> testList = new ContainerTest<T>(list) {
@Override
public long test() {
long startTime = System.nanoTime();
T t = getList();
ListIterator listIterator = t.listIterator();
while (listIterator.hasNext()) {
listIterator.next();
}
return System.nanoTime() - startTime;
}
};
long operateTime = testList.test();
long avg = operateTime / size;
System.out.println(size + "\t" + size + "\t" + avg);
}
public static void main(String[] args) {
Integer[] integers = {10000, 30000, 50000};
ArrayList<Integer> arrayList = new ArrayList<>();
displayHead(arrayList, "迭代遍历");
for (int i = 0; i < integers.length; i++) {
arrayList = initList(arrayList, integers[i]);
iter(arrayList, integers[i]);
}
System.out.println();
LinkedList<Integer> linkedList = new LinkedList<>();
displayHead(linkedList, "迭代遍历");
for (int i = 0; i < integers.length; i++) {
linkedList = initList(linkedList, integers[i]);
iter(linkedList, integers[i]);
}
}
ArrayList 迭代遍历
集合长度 操作次数 平均时间
10000 10000 108
30000 30000 57
50000 50000 37
LinkedList 迭代遍历
集合长度 操作次数 平均时间
10000 10000 72
30000 30000 11
50000 50000 12
6.随机访问
public static <T extends List> void get(T list, int loops, int size) {
ContainerTest<T> testList = new ContainerTest<T>(list) {
@Override
public long test() {
long startTime = System.nanoTime();
T t = getList();
Random random = new Random(47);
for (int i = 0; i < loops; i++) {
t.get(random.nextInt(size));
}
return System.nanoTime() - startTime;
}
};
long operateTime = testList.test();
long avg = operateTime / loops;
System.out.println(size + "\t" + loops + "\t" + avg);
}
public static void main(String[] args) {
Integer[][] integers = {{100, 10000}, {200, 30000}, {300, 50000}};
ArrayList<Integer> arrayList = new ArrayList<>();
displayHead(arrayList, "随机访问");
for (int i = 0; i < integers.length; i++) {
arrayList = initList(new ArrayList(), integers[i][1]);
get(arrayList, integers[i][0], integers[i][1]);
}
System.out.println();
LinkedList<Integer> linkedList = new LinkedList<>();
displayHead(linkedList, "随机访问");
for (int i = 0; i < integers.length; i++) {
linkedList = initList(new LinkedList(), integers[i][1]);
get(linkedList, integers[i][0], integers[i][1]);
}
}
ArrayList 随机访问
集合长度 操作次数 平均时间
10000 100 3327
30000 200 494
50000 300 98
LinkedList 随机访问
集合长度 操作次数 平均时间
10000 100 13331
30000 200 18803
50000 300 16241
7.随机更新
public static <T extends List> void set(T list, int loops, int size) {
ContainerTest<T> testList = new ContainerTest<T>(list) {
@Override
public long test() {
long startTime = System.nanoTime();
T t = getList();
Random random = new Random(47);
for (int i = 0; i < loops; i++) {
t.set(random.nextInt(size), i);
}
return System.nanoTime() - startTime;
}
};
long operateTime = testList.test();
long avg = operateTime / loops;
System.out.println(size + "\t" + loops + "\t" + avg);
}
public static void main(String[] args) {
Integer[][] integers = {{100, 10000}, {200, 30000}, {300, 50000}};
ArrayList<Integer> arrayList = new ArrayList<>();
displayHead(arrayList, "随机更新");
for (int i = 0; i < integers.length; i++) {
arrayList = initList(new ArrayList(), integers[i][1]);
set(arrayList, integers[i][0], integers[i][1]);
}
System.out.println();
LinkedList<Integer> linkedList = new LinkedList<>();
displayHead(linkedList, "随机更新");
for (int i = 0; i < integers.length; i++) {
linkedList = initList(new LinkedList(), integers[i][1]);
set(linkedList, integers[i][0], integers[i][1]);
}
}
ArrayList 随机更新
集合长度 操作次数 平均时间
10000 100 4996
30000 200 538
50000 300 197
LinkedList 随机更新
集合长度 操作次数 平均时间
10000 100 14090
30000 200 15057
50000 300 16582
8.随机移除
public static <T extends List> void remove(T list, int loops, int size) {
ContainerTest<T> testList = new ContainerTest<T>(list) {
@Override
public long test() {
long startTime = System.nanoTime();
T t = getList();
Random random = new Random(47);
for (int i = 0; i < loops; i++) {
t.remove(random.nextInt(size - loops));
}
return System.nanoTime() - startTime;
}
};
long operateTime = testList.test();
long avg = operateTime / loops;
System.out.println(size + "\t" + loops + "\t" + avg);
}
public static void main(String[] args) {
Integer[][] integers = {{100, 10000}, {200, 30000}, {300, 50000}};
ArrayList<Integer> arrayList = new ArrayList<>();
displayHead(arrayList, "随机移除");
for (int i = 0; i < integers.length; i++) {
arrayList = initList(new ArrayList(), integers[i][1]);
remove(arrayList, integers[i][0], integers[i][1]);
}
System.out.println();
LinkedList<Integer> linkedList = new LinkedList<>();
displayHead(linkedList, "随机移除");
for (int i = 0; i < integers.length; i++) {
linkedList = initList(new LinkedList(), integers[i][1]);
remove(linkedList, integers[i][0], integers[i][1]);
}
}
ArrayList 随机移除
集合长度 操作次数 平均时间
10000 100 6140
30000 200 6284
50000 300 6349
LinkedList 随机移除
集合长度 操作次数 平均时间
10000 100 11941
30000 200 20445
50000 300 16182
9.测试结果汇总
| 测试项目 | ArrayList | LinkedList |
|---|
| 顺序添加 | 低 | 高 | | 中部添加 | 高 | 低 | | 头部添加 | 低 | 高 | | 随机添加 | 高 | 低 | | 迭代遍历 | 低 | 高 | | 随机访问 | 高 | 低 | | 随机更新 | 高 | 低 | | 随机移除 | 高 | 低 |
ArrayList 底层为数组结构，故其随机访问性能高；LinkedList 为双向链表结构，拥有良好的伸缩拓展性，当在遍历和向首尾两端拓展时，性能优于 ArrayList 。
本次分享至此结束，希望本文对你有所帮助，若能点亮下方的点赞按钮，在下感激不尽，谢谢您的【精神支持】。
若有任何疑问，也欢迎与我交流，若存在不足之处，也欢迎各位指正！
|