实验目标

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

实验环境

• OS: mac OS
• memory：8G
• CPU：双核 2.7 GHz Intel Core i5
• java version: 1.8.074
• 数据乱序比例：20%

实验数据结构

（1）数组实现（Array）

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

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

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

（2）跳表实现（SkipList）

实现数据结构：ConcurrentSkipList<Integer>

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

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

实验设置

（1）不同数据结构的内存占用

（2）不同数据结构写入及查询延迟

（3）不同数据结构读写混合负载下写入及查询吞吐量

不同数据结构内存占用

不同数据结构写入及查询延迟

写入延迟

查询延迟

不同数据结构读写混合负载下写入及查询吞吐量

测试方法

单线程写入，同时匹配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倍