实验目标

1. 测试不同数据结构的内存占用情况
2. 测试不同读写比下不同数据结构的读写性能

实验环境

• OS: mac OS
• memory：8G
• CPU：双核 2.7 GHz Intel Core i5
• java version: 1.8.074

实验数据结构

（1）数组实现（Array）

实现数据结构：int[][]

写入：追加写入数组的最后位置

查询：先拷贝一份数组，做排序后做查询

（2）跳表实现（SkipList）

实现数据结构：ConcurrentSkipList<Integer>

写入：通过跳表插入到正确的有序位置（写入排序）

查询：直接查询跳表的引用

内存占用

单序列一百万个点

Array: 4 MB

SkipList：52 MB （Integer：16 MB, SkipListNode：36 MB）

十万序列每序列十个点

SkipList：59.6 MB (SkipList: 58 MB, ref: 1.6 MB)

Array: 5.6 MB (data: 4 MB, ref: 1.6 MB)

单线程写入+查询

单序列一千万个点

写入

Array：360 ms

SkipList：8921 ms

查询

Array：449 ms

SkipList：76 ms

一千序列每序列一万个点

写入

Array：428 ms

SkipList：9138 ms

查询

Array：393 ms

SkipList：92 ms

十万序列每序列一百个点

写入

Array：429 ms

SkipList：10129 ms

查询

Array：172 ms

SkipList：119 ms

并发写入+查询

测试方法

单线程写入，同时匹配n个线程查询，测试在有查询的负载下，写入线程最终完成写入的总时间

n: 查询线程数

单序列一千万个点

n = 1

Array：528 ms

Array read: 28.40 K points / ms

SkipList: 12413 ms

SkipList read: 40.76 K points / ms

n = 3

Array：702 ms

Array read: 40.01 K points / ms

SkipList: 14202 ms

SkipList read: 114.63 K points / ms

n = 5

Array：1131 ms

Array read: 42.44 K points / ms

SkipList: 16304 ms

SkipList read: 162.16 K points / ms

一千序列每序列一万个点

n = 1

Array：603 ms

Array read:  27.31 K points / ms

SkipList：28053 ms

SkipList read: 42.31  K points / ms

n = 3

Array：1010 ms

Array read: 66.73  K points / ms

SkipList: 40481 ms

SkipList read: 96.48  K points / ms

n = 5

Array：1221 ms

Array read: 89.31  K points / ms

SkipList：52064 ms

SkipList read: 112.91  K points / ms

十万序列每序列一百个点

n = 1

Array：1056 ms

Array read: 32.20  K points / ms

SkipList：10243 ms

SkipList read: 8.40  K points / ms

n = 3

Array：1539 ms

Array read: 60.43  K points / ms

SkipList：11620 ms

SkipList read: 28.92  K points / ms

n = 5

Array：2064 ms

Array read: 82.36  K points / ms

SkipList：13714 ms

SkipList read: 35.22  K points / ms

结论：随着每序列的点数减少，skiplist的查询性能越来越低，最终会低于Array的查询性能

Array/Skiplist查询耗时比随序列中的点数变化趋势

结论

（1）内存占用：skiplist 的内存占用为 array 的10倍左右

（2）写性能：array 的写性能大约为 skiplist 的20倍

（3）读性能：由于内存拷贝及排序，内存中的点数越多，array查询的性能越差，在1000万点时，skiplist 的查询性能约为array的5倍，100点时，skiplist 的查询性能约为array的1.5倍