Template:Computer Science:Data Structures:Sets
From
(adding descriptions of various implementations) |
m (1 revision) |
Current revision as of 14:14, 9 April 2009
Contents |
Sets
A mathematical set has a fairly simple interface and can be implemented in a surprising number of ways.
Set<item-type> ADT
contains(test-item:item-type):Boolean- True if test-item is contained in the Set.
insert(new-item:item-type)- Adds new-item into the set.
remove(item:item-type)- Removes item from the set. If item wasn't in the set, this method does nothing.
remove(item-iter:List Iterator<item-type>)- Removes the item refered to by item-iter from the set.
get-begin():List Iterator<item-type>- Allows iteration over the elements in the Set.
get-end():List Iterator<item-type>- Also allows iteration over the elements in the Set.
union(other:Set<item-type>):Set<item-type>- Returns a set containing all elements in either this or the other set. Has a default implementation.
intersect(other:Set<item-type>):Set<item-type>- Returns a set containing all elements in both this and the other set. Has a default implementation.
subtract(other:Set<item-type>):Set<item-type>- Returns a set containing all elements in this but not the other set. Has a default implementation.
is-empty():Boolean- True if no more items can be popped and there is no top item.
get-size():Integer- Returns the number of elements in the set.
All operations can be performed in O(N) time.
List implementation
There are several different ways to implement sets. The simplest, but in most cases least efficient, method is to simply create a linear list (an array, linked list or similar structure) containing each of the elements in the set. For the most basic operation, testing membership, a possible implementation could look like
function contains(List<T> list, T member)
for item in list
if item == member
return True
return False
To add new members to this set, simply add the element to beginning or end of the list. (If a check is done to ensure no duplicate elements, some other operations may be simpler.) Other operations can be similarly implemented in terms of simple list operations. Unfortunately, the membership test has a worst-case running time of O(n) if the item is not in the list, and even an average-case time of the same, assuming the item is equally likely to be anywhere in the list. If the set is small, or if frequently accessed items can be placed near the front of the list, this may be an efficient solution, but other options can have a faster running time.
Assuming elements can be ordered and insertions and deletions are rare, a list guaranteed to be in sorted order with no duplicate elements can be much more efficient. Using an ordered list, the membership test can be efficient to the order of O(logn). Additionally, union, intersection and subtraction can be implemented in linear time, whereas they would take quadratic time with unordered lists.
Bit array implementation
For certain data, it may be more practical to maintain a bit array describing the contents of the set. In this representation, there is a 1 or 0 corresponding to each element of the problem domain, specifying whether the object is an element of the set. For a simple case, assume that only integers from 0 to n can be members of the set, where n is known beforehand. This can be represented by a bit array of length n+1. The contains operation is simple:
function contains(BitArray array, Int member)
if member >= length(array)
return False
else if array[member] == 1
return True
else
return False
To add or remove an element from this sort of set, simply modify the bit array to reflect whether that index should be 1 or 0. The membership runs in exactly O(1) (constant) time, but it has a severely restricted domain. It is possible to shift the domain, going from m to n with step k, rather than 0 to n with step 1 as is specified above, but there is not much flexibility possible here. Nevertheless, for the right domain, this is often the most efficient solution.
Associative array implementation
Associative arrays--that is, hash tables and binary search trees, represent a heavyweight but general representation of sets. Binary trees generally have O(logn) time implementations for lookup and mutation for a particular key, and hash tables have a O(1) implementation (though there is a higher constant factor). Additionally, they are capable of storing nearly any key type. The membership test is trivial: simply test if the potential set member exists as a key in the associative array. To add an element, just add the set member as a key in the associative array, with a dummy value. In optimized implementations, instead of reusing an existing associative array implementation, it is possible to write a specialized hash table or binary tree which does not store values corresponding to keys. Values are not meaningful here, and they take up a constant factor of additional memory space.
[TODO:] Disjoint sets, more operation descriptions for union, intersection, etc.
