Function Repository Resource:

SkipListStructure

Source Notebook

A values-sorted data structure with fast insertion and deletion

Contributed by: Bradley Klee

ResourceFunction["SkipListStructure"][]

initializes an empty data skiplist structure.

ResourceFunction["SkipListStructure"][init]

sequentially inserts key-value pairs from init.

ResourceFunction["SkipListStructure"][data,"Insert",key,value]

updates data to include key→value at the correct insertion position, returning False if key has previously been set, and True otherwise.

ResourceFunction["SkipListStructure"][data,"KeyDrop",key]

updates data to remove key and its associated value, returning False if key has not been previously set, and True otherwise.

ResourceFunction["SkipListStructure"][data,"Lookup",key]

returns the value associated to key, or a Missing object if key is not set.

ResourceFunction["SkipListStructure"][data,"Normal"]

returns a values-sorted Association of all key-value pairs contained in data.

ResourceFunction["SkipListStructure"][data,"First"]

returns the first element in data.

ResourceFunction["SkipListStructure"][data,"PopFirst"]

returns the first element and removes it from data.

ResourceFunction["SkipListStructure"][data,"Visualization"]

depicts data as a rectangular Graph, with key-value pairs on all interior nodes.

ResourceFunction["SkipListStructure"][data,method,args]

supports an additional method, with optional arguments args as necessary.

Details

ResourceFunction["SkipListStructure"] is an implementation of a values-sorted association, which is optimized to have logarithmic Insert and KeyDrop times. In terms of functionality and design, this skiplist structure most closely follows DataStructure (but without optimizations due to compiling code).

An initialization init can be either an Association or a List. If the latter, the keys are taken to be the corresponding Part indices.

ResourceFunction["SkipListStructure"] accepts the option "OrderFunction", with default value Order. User-specified alternatives should behave like built-in Order by taking an adjacent pair of input values and returning 1 if the values are correctly ordered, -1 if they need to be transposed, or 0 if they are equivalent. An initialization of the structure can be done using this option.

In addition to primary usages above, ResourceFunction["SkipListStructure"] allows a wide variety of auxiliary usages:

SkipListStructure[data, "InsertPosition", value]

searches data and returns before and after indices pointing where to insert value.

SkipListStructure[data, "Lookup", key,default]

attempts a Lookup, and returns default when key is not set.

SkipListStructure[data, "Normal", n]

returns a values-sorted Association of only those key-value pairs occurring on the n^th level of the data structure.

SkipListStructure[data, "Last"]

returns the last element of data in the given ordering.

SkipListStructure[data, "PopLast"]

returns the last element and removes it from data.

SkipListStructure[data, "FirstLast"]

returns both first and last elements of data.

SkipListStructure[data, "MemberQ", value]

returns True if data already contains value, and False otherwise.

SkipListStructure[data, "EmptyQ"]

returns True if data contains no key-value pairs, and False otherwise.

SkipListStructure[data, "Validate"]

checks local structure and Ordering, returning True for valid data, and False otherwise.

Desired complexity statistics are achieved by emulating 2,3-Trees with a linked list. In fact, the linked list has both horizontal and vertical links, so it can also be accurately described as a linked array with dimensions (log n)⨯ n.

All valid ResourceFunction["SkipListStructure"] linked arrays are consistent with a constraint on branching ratio per-level. One or two vertices occur between every pair of adjacent horizontal links.

The linked array of a particular ResourceFunction["SkipListStructure"] can be depicted through the "Visualization" method. Five or six different colors are used to distinguish between inequivalent vertex figures:

Color

Vertical?

Next Color

Yes

, or

Yes

, or

Yes

None

It is relatively easy to delete a blue or purple vertex, or to insert around a yellow vertex. Deleting a yellow vertex or inserting around a blue or purple vertex sometimes requires non-trivial recursion and heuristic decision making.

The leading depth dimension log n is predictive of Insert / KeyDrop times. This method iterates through levels, making local changes only, until a halting condition is reached when the ResourceFunction["SkipListStructure"] is proven valid around every vertex.

ResourceFunction["SkipListStructure"] is path dependent with regard to sequences of insertions and deletions. Two ResourceFunction["SkipListStructure"] objects can fail a SameQ test, while having the same normal form.

Examples

Basic Examples (3)

Initialize an empty SkipListStructure:

In[1]:=

Out[1]=

Insert a string value:

In[2]:=

Out[2]=

Look up the value associated with key 1:

In[3]:=

Out[3]=

Insert another string value and print the normal form:

In[4]:=

Out[4]=

Use KeyDrop method to remove the value "alpha" and again print the normal form:

In[5]:=

Out[5]=

Remove the key corresponding to the value "one" and check if the data is empty:

In[6]:=

Out[6]=

Sort a list of ten random reals:

In[7]:=

SeedRandom[903274];
data = ResourceFunction["SkipListStructure"][RandomReal[1, 10]];
Table[ResourceFunction["SkipListStructure"][data, "PopFirst"], 10]

Out[9]=

Initialize a SkipListStructure with random initial data and print the first and last elements:

In[10]:=

SeedRandom[920384];
data = ResourceFunction["SkipListStructure"][
Association@MapIndexed[Rule[#2, #1] &,
RandomSample[WordList[], 30]]];
ResourceFunction["SkipListStructure"][data, "FirstLast"]

Out[12]=

Visualize the SkipListStructure as a rectangular graph:

In[13]:=

Out[13]=

List the five lexicographically earliest elements of the SkipListStructure:

In[14]:=

Out[14]=

Print the new first element:

In[15]:=

Out[15]=

Visualize the SkipListStructure again as a rectangular graph:

In[16]:=

Out[16]=

Validate the remaining data:

In[17]:=

Out[17]=

Scope (2)

Initialize alphabetical data with randomized pointers and show the visualization:

In[18]:=

SeedRandom[7348923];
data = ResourceFunction["SkipListStructure"][
Association@Map[Rule[Key[LetterNumber[#]], #] &,
RandomSample[Alphabet[]]]];
ResourceFunction["SkipListStructure"][data, "Visualization"]

Out[18]=

Return values on each level in normal form:

In[19]:=

Out[19]=

Find before and after pointers when inserting a second letter "k":

In[20]:=

Out[20]=

Look up the predecessor and successor directly:

In[21]:=

Out[21]=

Use SkipListStructure to sort a randomized list of RandomTree outputs:

In[22]:=

Out[19]=

Options (1)

OrderFunction (1)

Sort values in reverse order:

In[23]:=

SeedRandom[903274];
data = ResourceFunction["SkipListStructure"][RandomReal[1, 10],
"OrderFunction" -> Function[-Order[#1, #2]]];
Table[ResourceFunction["SkipListStructure"][data, "PopFirst"], 10]

Out[23]=

Properties and Relations (1)

Both SkipListStructure and the resource function IndexedQueue have logarithmic insertion times:

In[24]:=

$Module[{randData, heap, heapTimes, data, skipTimes, size = 2^12}, SeedRandom[23434]; randData = MapIndexed[#2[[1]] -> #1 &, RandomInteger[size, size]]; heap = ResourceFunction["IndexedQueue"][{ "InitialSize" -> 1, "NullElement" -> Missing[], "ComparisonFunction" -> Greater}, {}, "Initialize"]; heapTimes = Reap[Module[{next}, Fold[Sow[AbsoluteTiming[ ResourceFunction["IndexedQueue"][heap, Last[#2], "Enqueue"] ][[1]]] &, {}, randData]]][[2, 1]]; data = ResourceFunction["SkipListStructure"][]; skipTimes = Reap[Fold[Sow[AbsoluteTiming[ ResourceFunction["SkipListStructure"][data, "Insert", First[#2], Last[#2] ]][[1]]] &, {}, randData]][[2, 1]]; Labeled[Show[ ListPlot[skipTimes, PlotStyle -> Darker@Blue], ListPlot[heapTimes, PlotStyle -> Red], PlotRange -> All], Row[{Darker@Blue, Text@" SkipListStructure", Spacer[35], Red, Text@" IndexedQueue"}] ] ]$

Out[24]=