|
> with O(1) expected restructuring time and exponentially infrequent occurrences of expensive restructuring So I was curious about this, so I threw together a quick and dirty implementation of the insert function as described in the paper, counting both the number of times the insert() function is called and the number of times a pointer is written to when inserting 65535 (2^16 - 1) random numbers: Below are the results: Inserts 0 to 1: Avg fn calls: 2.00, Avg ptr writes: 2.00
Inserts 1 to 3: Avg fn calls: 3.50, Avg ptr writes: 1.00
Inserts 3 to 7: Avg fn calls: 5.00, Avg ptr writes: 4.00
Inserts 7 to 15: Avg fn calls: 6.12, Avg ptr writes: 5.00
Inserts 15 to 31: Avg fn calls: 7.06, Avg ptr writes: 4.62
Inserts 31 to 63: Avg fn calls: 7.28, Avg ptr writes: 3.59
Inserts 63 to 127: Avg fn calls: 9.64, Avg ptr writes: 4.81
Inserts 127 to 255: Avg fn calls: 11.72, Avg ptr writes: 4.08
Inserts 255 to 511: Avg fn calls: 13.73, Avg ptr writes: 4.73
Inserts 511 to 1023: Avg fn calls: 17.61, Avg ptr writes: 5.30
Inserts 1023 to 2047: Avg fn calls: 18.95, Avg ptr writes: 4.99
Inserts 2047 to 4095: Avg fn calls: 19.12, Avg ptr writes: 5.05
Inserts 4095 to 8191: Avg fn calls: 19.67, Avg ptr writes: 4.98
Inserts 8191 to 16383: Avg fn calls: 20.76, Avg ptr writes: 4.94
Inserts 16383 to 32767: Avg fn calls: 22.38, Avg ptr writes: 4.99
Inserts 32767 to 65535: Avg fn calls: 24.18, Avg ptr writes: 4.99
So it turns out that it is O(1) in terms of number of pointer writes but O(lg(n)) in terms of number of function calls, and since every function call will perform at least one comparison, that means this algorithm is O(1) for writes but O(lg(n)) for reads, meaning that given large enough n, the O(lg(n)) read term will dominate and thus this algorithm is O(lg(n)) for inserts.That said, if writes are far more expensive than reads in the context this is used, this could still be useful. |