THIS IS A TEST INSTANCE. ALL YOUR CHANGES WILL BE LOST!!!!
...
- OS: mac OS
- memory：8G
- CPU：双核 2.7 GHz Intel Core i5
- java version: 1.8.074
- 数据乱序比例：20%
实验数据结构
（1）数组实现（Array）
实现数据结构：int[][]
...
写入：通过跳表插入到正确的有序位置（写入排序）
查询：直接查询跳表的引用
...
实验设置
（1）不同数据结构的内存占用
（2）不同数据结构写入及查询延迟
（3）不同数据结构读写混合负载下写入及查询吞吐量
不同数据结构内存占用
| 负载 / 数据结构 | Array | SkipList |
|---|---|---|
| 单序列一百万个点 |
...
| 4 MB |
...
| 52 MB |
| 十万序列每序列十个点 |
...
| 5.6 MB |
...
| 59.6 MB |
...
...
不同数据结构写入及查询延迟
...
写入延迟
写入
Array：360 ms
SkipList：8921 ms
查询
Array：449 ms
...
| 负载 / 数据结构 | Array | SkipList |
|---|---|---|
| 单序列一百万个点 | 360 ms | 8921 ms |
| 一千序列每序列一万个点 |
写入
...
| 428 ms |
...
| 9138 ms |
...
| 十万序列每序列一百个点 |
...
| 429 ms |
SkipList：92 ms
十万序列每序列一百个点
写入
Array：429 ms
SkipList：10129 ms
查询
Array：172 ms
SkipList：119 ms
...
| 10129 ms |
查询延迟
| 负载 / 数据结构 | Array | SkipList |
|---|---|---|
| 单序列一百万个点 | 449ms | 76ms |
| 一千序列每序列一万个点 | 393ms | 92ms |
| 十万序列每序列一百个点 | 172ms | 119ms |
不同数据结构读写混合负载下写入及查询吞吐量
测试方法
单线程写入，同时匹配n个线程查询，测试在有查询的负载下，写入线程最终完成写入的总时间
n: 查询线程数
写入吞吐
| 负载 / 查询线程数 | n = 1 (points / ms) | n = 3 (points / ms) | n = 5 (points / ms) | |||
|---|---|---|---|---|---|---|
| 数据结构 | Array | SkipList | Array | SkipList | Array | SkipList |
| 单序列一千万个点 | 18.93 K | 0.81 K | 14.25 K | 0.70 K | 8.84 K | 0.61 K |
| 一千序列每序列一万个点 | 16.58 K | 0.36 K | 9.91 K | 0.25 K | 8.19 K | 0.19 K |
| 十万序列每序列一百个点 | 9.47 K | 0.97 K | 6.50 K | 0.86 K | 4.85 K | 0.72 K |
单序列一千万个点
n = 1
Array：528 ms
Array read: 28.40 K points / ms
...
SkipList read: 162.16 K points / ms
一千序列每序列一万个点
n = 1
Array：603 ms
Array read: 27.31 K points / ms
...
SkipList read: 112.91 K points / ms
十万序列每序列一百个点
n = 1
Array：1056 ms
Array read: 32.20 K points / ms
...