Project Nayuki

Binary array set

Introduction

The binary array set[0] is a very space-efficient data structure that supports adding elements and testing membership reasonably quickly. It basically works as a collection of sorted arrays with power-of-2 sizes.

Adding one element to a BAS takes amortized Θ(log n) time (worst-case Θ(n)), searching/testing for an element takes worst-case Θ((log n)2) time, and removing an element is not supported at all (although the entire set can be cleared easily). Despite the lack of deletion functionality, the data structure is still useful in applications that only add and test but don’t delete – for example, breadth-first search maintains an ever-growing set of visited nodes that shouldn’t be revisited. To compare time complexities with a popular alternative, a balanced binary search tree takes worst-case Θ(log n) time alike for adding, testing, or removing one element.

The binary array set data structure is succinct because it only uses Θ(log n) extra space for overhead (i.e. the space not used for storing the element values themselves). For modest sizes of n (e.g. over 1000), the amount of overhead space used by a BAS is practically negligible. The data structure that best minimizes overhead space would be the single flat array (which uses only Θ(1) extra space), but it doesn’t support both fast insertion and testing simultaneously. Note that despite the word “array” in the data structure’s name, the set is in fact orderless and can present elements in any order.

By comparison, a balanced BST uses Θ(n) extra space for pointers to all the tree nodes. (B-trees also use Θ(n) extra space, but the scaling constant approaches zero as the degree increases.) This extra space usage for node pointers would be problematic in the situation where the array of raw data values (without pointers and other overheads) barely fits in system memory. This disadvantage of node-based data structures is especially painful in languages like Java, where each object (i.e. the tree nodes) inherently has tens of bytes of overhead.

Internal details

How this data structure works is that it has a sequence of ⌊log2 n⌋ + 1 slots, where the slot at index k (0-based counting) is either null or an ascending-sorted array of length 2k. For example, the abstract conceptual set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13} could be represented as a binary array set in one way like this:

Number of slots: ⌊log2 13⌋ + 1 = 4.
Slot 0: [5]. (length 1)
Slot 1: Null.
Slot 2: [2, 3, 9, 13]. (length 4)
Slot 3: [1, 4, 6, 7, 8, 10, 11, 12]. (length 8)

Note that the size of the set is 13, whose binary representation is 11012. The binary representation corresponds with which slots are filled. Also note that the union of all the arrays in the binary array set is exactly equal to the set of elements being represented, no more, no less, without duplicates.

To test if a given value is a member of the set, we simply perform the standard binary search in each array (in the non-null slots) and return whether a result was found.

To add a new element, we wrap the element in a new array of length 1. If slot 0 is empty, we simply store the new array there. Otherwise we merge the new array with the array already at slot 0, which forms a new sorted array of length 2. Next we check if slot 1 is empty; we repeat this merge/check process on increasing slot indexes until we find an empty slot.

Interactive visualization

Slot # Values

Source code

Java (SE 7+)

The class implements the java.util.Set interface, so it can be used as a drop-in replacement of HashSet or TreeSet as long as remove() is not called. The iterator is not fail-fast on concurrent modifications. The maximum set size is Integer.MAX_VALUE (i.e. 231 − 1).

The implemented iterator is not guaranteed to output the elements in sorted order. The benefits of this unsorted iterator are short code, Θ(1) time complexity per element[1], and Θ(1) storage space at all times. It is indeed possible to design an iterator that yields elements in sorted order; this would require more code and a priority queue, Θ(log log n) time per element, and Θ(log n) space.

Python

This implementation only supports the methods {add(), clear()}, built-in functions {len(), iter()}, and operator in – so it only supports a fraction of the methods that the built-in set type has.

C++ (C++11 and above)

The class is modeled after the Java version, supporting the methods size(), add(), contains(), empty(), and clear(). It has far fewer features than std::set. Currently no iterator is implemented.

Rust

This struct and its methods are modeled after std::collections::BTreeSet, but has fewer features. A move iterator and an immutable reference iterator are supported.

License: MIT (open source)

Notes

  • This data structure is described in Introduction to Algorithms (“CLRS”) 2nd and 3rd editions, chapter 17 “Amortized Analysis”, problem 17-2 “Making binary search dynamic” (page 473 in the 3rd edition). It is also adapted for use in log-structured merge-trees.

  • The binary-merge behavior of this data structure is like a simplified version of binomial heaps with flat arrays instead of binary tree nodes.

  • The binary array set can be readily adapted to a map/dictionary if needed.

  • [0]: The name “binary array set” for this data structure was made up by me. I had asked a question on Stack Overflow to see if there was an existing name for this structure, but the result was negative. Thus it should be impossible to search for existing literature using the BAS name.

  • [1]: Strictly speaking, the iterator needs worst-case Θ(log n) time, amortized Θ(1) time to process each element, because it needs to skip over empty slots that have no array. However, the number of slots is at most log2 n + 1, which is less than 64 on real computers, which is a rather small number. Moreover, it’s possible to use a linked list of arrays (with no empty elements) instead of an array of arrays (with empty slots), which avoids the Θ(log n) time cost of skipping empty slots. Hence we can treat the act of skipping empty slots to be effectively a constant-time operation.

More info