实验目标
- 测试不同数据结构的内存占用情况
- 测试不同读写比下不同数据结构的读写性能
实验环境
- 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
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倍