# Marpa

Update of "fast sparse integer sets in C"
Tcl 2016 Conference, Houston/TX, US, Nov 14-18

Overview

Artifact ID: b7692adba65535e160e71d67c78be64b97dc01a8 fast sparse integer sets in C 2017-02-23 19:39:28 akupries text/x-markdown 8c32f6e09c90d703e07a280320731d5a8b992ada
Content

Up: Notes

References

Excerpts from the first reference:

• Preston Briggs and Linda Torczon's 1993 paper, “An Efficient Representation for Sparse Sets,” describes the trick in detail. Their solution represents the sparse set using an integer array named `dense` and an integer `n` that counts the number of elements in `dense`. The `dense` array is simply a packed list of the elements in the set, stored in order of insertion. If the set contains the elements 5, 1, and 4, then `n = 3` and `dense[0] = 5`, `dense[1] = 1`, `dense[2] = 4`:

• Together `n` and `dense` are enough information to reconstruct the set, but this representation is not very fast. To make it fast, Briggs and Torczon add a second array named `sparse` which maps integers to their indices in `dense`. Continuing the example, `sparse[5] = 0`, `sparse[1] = 1`, `sparse[4] = 2`. Essentially, the set is a pair of arrays that point at each other:

• To check whether `i` is in the set, you verify that the two arrays point at each other for that element.

• If `i` is not in the set, then it doesn't matter what sparse[i] is set to: either `sparse[i]` will be bigger than `n` or it will point at a value in `dense` that doesn't point back at it. Either way, we're not fooled.

An important part of this structure is that none of the memory it uses requires initialization before reading from it.