iskiplist

Overview ¶

Package iskiplist provides a skip list based implementation of arrays with O(log n) indexing, insertion and removal. The array element type is 'int'. The idea is to use the int value as an index into a slice of the data structure of your choice. If this technique isn't applicable, it's easy to modify the code to use interface{} as the element type instead.

Each ISkipList maintains its own pseudorandom number generator state. The algorithm used is PCG32. By default, seed initialization piggybacks on address space randomization by using the address of an ISkipList to generate a seed. A seed can be supplied manually via Seed() if more entropy is required.

A cache is maintained of the index and set of nodes associated with the last element access. This increases the efficiency of common iteration patterns without introducing the complexities associated with explicit iterators. For example, if you iterate through every third element in an ISkipList by indexing using At(), then the search for each element at i+3 will begin at element i, not at the root of the skip list. The cache is automatically invalidated in the expected way by operations that mutate the ISkipList. For example, removing the element at i invalidates the cache for a preceding access of any element at index >= i.

The fastest way to iterate through the elements of an ISkipList in sequence is to use Iterate(), IterateI(), IterateRange(), IterateRangeI(), ForAll(), ForAllI(), ForAllRange(), and ForAllRangeI(). These functions do the minimum work possible and do not update the cache.

The behavior of the iteration methods mentioned in the preceding paragraph is unspecified if the ISkipList is mutated within the callback function. (Mutating the element itself is fine – you just can't insert or remove elements.) If you wish to mutate an ISkipList while iterating through it, you should iterate by index.

The most efficient way to build an ISkipList is to add elements sequentially using PushFront(). The next most efficient method is to add elements sequentially using PushBack(). Both run in constant time (the latter due to caching), but PushFront() has a lower constant overhead.

Slices can often be faster in practice than more sophisticated data structures. The following cautionary notes should be borne in mind:

1) Inserting or removing an element in the middle of a slice is extremely fast for slices of a thousand elements or fewer. You will not necessarily see any benefit from using an ISkipList unless you are dealing with sequences of more than 1000 elements. Once you get up to around 10,000 elements, insertions and removals targetting the middle of an ISkipList are much faster.

2) It takes much longer to create an ISkipList by sequentially appending elements than it does to do the same with a slice. Profiling suggests that most of the additional time is spent allocating the list nodes. Thus, if you are creating a list in sequence and then performing only a small number of insertion/removal operations on it, you might find that the total time is dominated by creation time.

These issues can sometimes be mitigated by using a BufferedISkipList instead of an ISkipList (see the bufferediskiplist package).