实验目标

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

实验环境

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

实验数据结构

（1）数组实现（Array）

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

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

（2）跳表实现（SkipList）

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

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

内存占用

单序列一百万个点

Array: 4MB

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

十万序列每序列十个点

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

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

单线程写入+查询

单序列一千万个点

写入

Array：360ms

SkipList：8921ms

查询

Array：449ms

SkipList：76ms

十万序列每序列一百个点

写入

Array：429ms

SkipList：10129ms

查询

Array：172ms

SkipList：119ms

并发写入+查询

测试方法

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

n: 查询线程数

单序列一千万个点

n = 1

Array：528ms

SkipList: 12413ms

n = 3

Array：702ms

SkipList: 14202ms

n = 5

Array：1131ms

SkipList: 16304ms

十万序列每序列一百个点

n = 1

Array：1056ms

SkipList：10243ms

n = 3

Array：1539ms

SkipList：11620ms

n = 5

Array：2064ms

SkipList：13714ms

结论

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

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

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