实验目标

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

实验环境

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

实验数据结构

（1）数组实现（Array）

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

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

（2）跳表实现（SkipList）

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

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

内存占用

单序列一百万个点

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

SkipList: 12413 ms

n = 3

Array：702 ms

SkipList: 14202 ms

n = 5

Array：1131 ms

SkipList: 16304 ms

十万序列每序列一百个点

n = 1

Array：1056 ms

SkipList：10243 ms

n = 3

Array：1539 ms

SkipList：11620 ms

n = 5

Array：2064 ms

SkipList：13714 ms

结论

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

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

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