Page History

...

n = 1

Array：528 ms

Array read count: 15 M points: 28.40 K points / ms

SkipList: 12413 ms

SkipList read count: 506 M points: 40.76 K points / ms

n = 3

Array：702 ms

Array read count: 33 M points: 40.01 K points / ms

SkipList: 14202 ms

SkipList read count: 1628 M points: 114.63 K points / ms

n = 5

Array：1131 ms

Array read count: 48 M points: 42.44 K points / ms

SkipList: 16304 ms

SkipList read count: 2644 M points: 162.16 K points / ms

一千序列每序列一万个点

n = 1

Array：603 ms

Array read count: 7 M points:  27.31 K points / ms

SkipList：28053 ms

SkipList read count: 1187 M points: 42.31  K points / ms

n = 3

Array：1010 ms

SkipList Array read count: 16 M points: 66.73  K points / ms

SkipList: 40481 ms

SkipList read count: 3906 M points: 96.48  K points / ms

n = 5

Array：1221 ms

Array read count: 21 M points: 89.31  K points / ms

SkipList：52064 ms

SkipList read count: 5879 M points: 112.91  K points / ms

十万序列每序列一百个点

n = 1

Array：1056 ms

Array read count: 34 M points: 32.20  K points / ms

SkipList：10243 ms

SkipList read count: 86 M points: 8.40  K points / ms

n = 3

Array：1539 ms

SkipList Array read count: 93 M points: 60.43  K points / ms

SkipList：11620 ms

SkipList read count: 336 M points: 28.92  K points / ms

n = 5

Array：2064 ms

Array read count: 170 M points: 82.36  K points / ms

SkipList：13714 ms

SkipList read count: 483 M points: 35.22  K points / ms

结论：随着每序列的点数减少，skiplist的查询性能越来越低，最终会低于Array的查询性能

...