Documentation ¶
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).
Index ¶
- func DebugPrintISkipList(l *ISkipList, pointerDigits int) string
- type ElemType
- type ISkipList
- func (l *ISkipList) At(i int) ElemType
- func (l *ISkipList) Clear()
- func (l *ISkipList) Copy() *ISkipList
- func (l *ISkipList) CopyRange(from, to int) *ISkipList
- func (l *ISkipList) CopyRangeToSlice(from, to int, slice []ElemType)
- func (l *ISkipList) CopyToSlice(slice []ElemType)
- func (l *ISkipList) ForAll(f func(*ElemType))
- func (l *ISkipList) ForAllI(f func(int, *ElemType))
- func (l *ISkipList) ForAllRange(from, to int, f func(*ElemType))
- func (l *ISkipList) ForAllRangeI(from, to int, f func(int, *ElemType))
- func (l *ISkipList) Insert(index int, elem ElemType)
- func (l *ISkipList) Iterate(f func(*ElemType) bool)
- func (l *ISkipList) IterateI(f func(int, *ElemType) bool)
- func (l *ISkipList) IterateRange(from, to int, f func(*ElemType) bool)
- func (l *ISkipList) IterateRangeI(from, to int, f func(int, *ElemType) bool)
- func (l *ISkipList) Length() int
- func (l *ISkipList) PopBack() (r ElemType, ok bool)
- func (l *ISkipList) PopFront() (r ElemType, ok bool)
- func (l *ISkipList) PtrAt(i int) *ElemType
- func (l *ISkipList) PushBack(elem ElemType)
- func (l *ISkipList) PushFront(elem ElemType)
- func (l *ISkipList) Remove(index int) ElemType
- func (l *ISkipList) Seed(seed1 uint64, seed2 uint64)
- func (l *ISkipList) SeedFrom(l2 *ISkipList)
- func (l *ISkipList) Set(i int, v ElemType)
- func (l *ISkipList) Swap(index1, index2 int)
- func (l *ISkipList) Truncate(n int)
- func (l *ISkipList) Update(i int, upd func(ElemType) ElemType)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DebugPrintISkipList ¶
DebugPrintISkipList returns a string representation of an ISkipList that is useful for debugging. There is no guarantee that this output will remain consistent between versions of this package.
Types ¶
type ISkipList ¶
type ISkipList struct {
// contains filtered or unexported fields
}
ISkipList is an indexable skip list. It behaves like an array or slice (elements sequenced and accessed by index) rather than a map (elements not sequenced and accessed by key).
func (*ISkipList) Clear ¶
func (l *ISkipList) Clear()
Clear empties an ISkipList. Following a call to Clear(), an ISkipList behaves the same as an ISkipList initialized with its default value.
func (*ISkipList) Copy ¶
Copy copies the ISkipList. It does not rerandomize. Seed() and SeedFrom() may be called on the result prior to any other operations. The cache of the ISkipList is not copied.
func (*ISkipList) CopyRange ¶
CopyRange creates a new ISkipList whose contents are equal to a range of the original ISkipList. The 'from' argument must be >= 0 and < the length of the ISkipList. The 'to' argument must be >= 0 and <= the length of the ISkipList. If neither 'from' nor 'to' is out of bounds but to <= from, then this is a no-op.
func (*ISkipList) CopyRangeToSlice ¶
CopyRangeToSlice copies a range of the ISkipList to a slice. The 'from' argument must be >= 0 and < the length of the ISkipList. The 'to' argument must be >= 0 and <= the length of the ISkipList. If neither 'from' nor 'to' is out of bounds but to <= from, then this is a no-op.
func (*ISkipList) CopyToSlice ¶
CopyToSlice(slice) is a shorthand for l.CopyRangeToSlice(0, l.Length(), slice)
func (*ISkipList) ForAllRange ¶
ForAllRange is like IterateRange except that the iteration always continues to the end of the specified range. This saves the bother of adding a boolean return value to the iteration function. Element pointers remain valid following any subsequent operations on the ISkipList. Keeping a pointer to a deleted element will prevent garbage collection of the associated skip list nodes.
func (*ISkipList) ForAllRangeI ¶
ForAllRangeI is like IterateRangeI except that the iteration always continues to the end of the specified range. This saves the bother of adding a boolean return value to the iteration function. Element pointers remain valid following any subsequent operations on the ISkipList. Keeping a pointer to a deleted element will prevent garbage collection of the associated skip list nodes.
func (*ISkipList) Insert ¶
Insert inserts an element before the element at the specified index, or at the end of the list if the index is equal to the length of the ISkipList.
func (*ISkipList) IterateRange ¶
IterateRange iterates over a range of the ISkipList and passes the supplied function a pointer to each element visited. The iteration is halted if the function returns false. The 'from' argument must be >= 0 and < the length of the ISkipList. The 'to' argument must be >= 0 and <= the length of the ISkipList. If neither 'from' nor 'to' is out of bounds but to <= from, then this is a no-op. Element pointers remain valid following any subsequent operations on the ISkipList. Keeping a pointer to a deleted element will prevent full garbage collection of the associated skip list nodes.
func (*ISkipList) IterateRangeI ¶
IterateRangeI iterates over a range of the ISkipList and passes to the supplied function the index of each visited element and a pointer to it. The iteration is halted if the function returns false. The 'from' argument must be >= 0 and < the length of the ISkipList. The 'to' argument must be >= 0 and <= the length of the ISkipList. If neither 'from' nor 'to' is out of bounds but to <= from, then this is a no-op. Element pointers remain valid following any subsequent operations on the ISkipList. Keeping a pointer to a deleted element will prevent full garbage collection of the associated skip list nodes.
func (*ISkipList) PopBack ¶
PopBack removes the last element of the list and returns it. The second return value is true iff the list was non-empty prior to the pop. PopFront should be preferred where applicable.
func (*ISkipList) PopFront ¶
PopFront removes the first element of the list and returns it. The second return value is true iff the list was non-empty prior to the pop. PopFront runs in constant time.
func (*ISkipList) PtrAt ¶
PtrAt retrieves a pointer to the element at the specified index. This pointer remains valid following any subsequent operations on the ISkipList. Keeping a pointer to a deleted element will prevent full garbage collection of the associated skip list nodes.
func (*ISkipList) PushBack ¶
PushBack adds an element to the end of the ISkipList. PushFront should be preferred where applicable.
func (*ISkipList) PushFront ¶
PushFront adds an element to the beginning of the ISkipList. PushFront runs in constant time.
func (*ISkipList) Remove ¶
Remove removes the element at the specified index. It returns the value of the removed element.
func (*ISkipList) Seed ¶
Seed seeds the random number generator used for the ISkipList. If Seed is called, it should be called immediately following creation of the ISkipList. If Seed is not called, the random number generator is automatically seeded using the address of the ISkipList. This works fine, but may not be sufficiently random if the ISkipList could be the target of adversarial usage.
func (*ISkipList) SeedFrom ¶
SeedFrom sets the pseudorandom number generator state of an ISkipList by copying it from another ISkipList. If SeedFrom is called, it should be called immediately following creation of the ISkipList.
Directories ¶
Path | Synopsis |
---|---|
Package bufferediskiplist provides a version of ISkipList that (i) buffers insertions at the start and end of the sequence and (ii) does not construct a skip list structure until the sequence reaches a certain length.
|
Package bufferediskiplist provides a version of ISkipList that (i) buffers insertions at the start and end of the sequence and (ii) does not construct a skip list structure until the sequence reaches a certain length. |
Package pcg is an internal package used by github.com/addrummond/iskiplist.
|
Package pcg is an internal package used by github.com/addrummond/iskiplist. |
Package sliceutils is an internal package used by github.com/addrummond/iskiplist.
|
Package sliceutils is an internal package used by github.com/addrummond/iskiplist. |