fmela/libdict — pull request #9 by alexbers (2014-07-21 16:50:01+00:00)
Title: Update skiplist.c

This patch changes node level distributions.
As said in the original doc: ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf variable p(franction of the nodes with level i that also have level i+1 pointers) should be chosen as 1/4 unless the variability of running times is not our primary concern.

This change decreases number of comparisons and dramaticly improves performance. The benchmark time dropped from 52.2 sec. to 9.6 sec. Also memory consumption droped from 47992kB to 42666kB.

Here is the results of benchmark.

Before:
$ bin/benchmark S r.txt
sk container: 0.19kB
sk memory: 47992.38kB
sk insert: 7.793 s (265126074 cmp, 0 hash)
sk fwd iterate: 0.093 s
sk rev iterate: 0.092 s
sk good search: 18.019 s (512545083 cmp, 0 hash)
sk bad search: 18.166 s (516927720 cmp, 0 hash)
sk remove: 8.070 s (272280836 cmp, 0 hash)
sk total: 52.234 s (1566879713 cmp, 0 hash)

After:
$ bin/benchmark S r.txt
sk container: 0.19kB
sk memory: 42666.86kB
sk insert: 2.265 s ( 35900850 cmp, 0 hash)
sk fwd iterate: 0.091 s
sk rev iterate: 0.089 s
sk good search: 2.501 s ( 37698480 cmp, 0 hash)
sk bad search: 2.591 s ( 37965496 cmp, 0 hash)
sk remove: 2.104 s ( 36015791 cmp, 0 hash)
sk total: 9.641 s (147580617 cmp, 0 hash)

File r.txt was generated with this Python script:

import random

abc = "qwertyuiopasdfghjklzxcvbnm"

def g():
ret = []
for i in range(10):
ret.append(random.choice(abc))
return "".join(ret)

for i in range(1000000):
print(g())