13: Data Structures for Integers

Last updated
Save as PDF

Page ID: 8489

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

In this chapter, we return to the problem of implementing an SSet. The difference now is that we assume the elements stored in the SSet are \(\mathtt{w}\)-bit integers. That is, we want to implement \(\mathtt{add(x)}\), \(\mathtt{remove(x)}\), and \(\mathtt{find(x)}\) where \(\mathtt{x}\in\{0,\ldots,2^{\mathtt{w}}-1\}\). It is not too hard to think of plenty of applications where the data--or at least the key that we use for sorting the data--is an integer.

We will discuss three data structures, each building on the ideas of the previous. The first structure, the BinaryTrie performs all three SSet operations in \(O(\mathtt{w})\) time. This is not very impressive, since any subset of \(\{0,\ldots,2^{\mathtt{w}}-1\}\) has size \(\mathtt{n}\le 2^{\mathtt{w}}\), so that \(\log \mathtt{n} \le \mathtt{w}\). All the other SSet implementations discussed in this book perform all operations in \(O(\log \mathtt{n})\) time so they are all at least as fast as a BinaryTrie.

The second structure, the XFastTrie, speeds up the search in a BinaryTrie by using hashing. With this speedup, the \(\mathtt{find(x)}\) operation runs in \(O(\log \mathtt{w})\) time. However, \(\mathtt{add(x)}\) and \(\mathtt{remove(x)}\) operations in an XFastTrie still take \(O(\mathtt{w})\) time and the space used by an XFastTrie is \(O(\mathtt{n}\cdot\mathtt{w})\).

The third data structure, the YFastTrie, uses an XFastTrie to store only a sample of roughly one out of every \(\mathtt{w}\) elements and stores the remaining elements in a standard SSet structure. This trick reduces the running time of \(\mathtt{add(x)}\) and \(\mathtt{remove(x)}\) to \(O(\log \mathtt{w})\) and decreases the space to \(O(\mathtt{n})\).

The implementations used as examples in this chapter can store any type of data, as long as an integer can be associated with it. In the code samples, the variable \(\mathtt{ix}\) is always the integer value associated with \(\mathtt{x}\), and the method \(\texttt{in.}\)\(\mathtt{intValue(x)}\) converts \(\mathtt{x}\) to its associated integer. In the text, however, we will simply treat \(\mathtt{x}\) as if it is an integer.