程序包 edu.princeton.cs.algs4

类 PatriciaSET

java.lang.Object

edu.princeton.cs.algs4.PatriciaSET

所有已实现的接口:

java.lang.Iterable<java.lang.String>

public class PatriciaSET
extends java.lang.Object
implements java.lang.Iterable<java.lang.String>

The PatriciaSET class provides an implementation of an unordered set, with the restriction that the items (keys) are of class String. It supports the usual add, contains, delete, size, and is-empty methods. It also provides an iterator method for iterating over all the elements in the set.

This unordered set class implements PATRICIA (Practical Algorithm to Retrieve Information Coded In Alphanumeric). In spite of the acronym, string keys are not limited to alphanumeric content. A key may possess any string value, with one exception: a zero-length string is not permitted.

Unlike other generic set implementations that can accept a parameterized key type, this set class can only accommodate keys of class String. This unfortunate restriction stems from a limitation in Java. Although Java provides excellent support for generic programming, the current infrastructure somewhat limits generic collection implementations to those that employ comparison-based or hash-based methods. PATRICIA does not employ comparisons or hashing; instead, it relies on bit-test operations. Because Java does not furnish any generic abstractions (or implementations) for bit-testing the contents of an object, providing support for generic keys using PATRICIA does not seem practical.

PATRICIA is a variation of a trie, and it is often classified as a space-optimized trie. In a classical trie, each level represents a subsequent digit in a key. In PATRICIA, nodes only exist to identify the digits (bits) that distinguish the individual keys within the trie. Because PATRICIA uses a radix of two, each node has only two children, like a binary tree. Also like a binary tree, the number of nodes, within the trie, equals the number of keys. Consequently, some classify PATRICIA as a tree.

The analysis of PATRICIA is complicated. The theoretical wost-case performance for an add, contains, or delete operation is O(N), when N is less than W (where W is the length in bits of the longest key), and O(W), when N is greater than W. However, the worst case is unlikely to occur with typical use. The average (and usual) performance of PATRICIA is approximately ~lg N for each add, contains, or delete operation. Although this appears to put PATRICIA on the same footing as binary trees, this time complexity represents the number of single-bit test operations (under PATRICIA), and not full-key comparisons (as required by binary trees). After the single-bit tests conclude, PATRICIA requires just one full-key comparison to confirm the existence (or absence) of the key (per add, contains, or delete operation).

In practice, decent implementations of PATRICIA can often outperform balanced binary trees, and even hash tables. Although this particular implementation performs well, the source code was written with an emphasis on clarity, and not performance. PATRICIA performs admirably when its bit-testing loops are well tuned. Consider using the source code as a guide, should you need to produce an optimized implementation, for anther key type, or in another programming language.

Other resources for PATRICIA:
Sedgewick, R. (1990) Algorithms in C, Addison-Wesley
Knuth, D. (1973) The Art of Computer Programming, Addison-Wesley

构造器概要

构造器

构造器	说明
PatriciaSET()	Initializes an empty PATRICIA-based set.

方法概要

修饰符和类型	方法	说明
void	add(java.lang.String key)	Adds the key to the set if it is not already present.
boolean	contains(java.lang.String key)	Does the set contain the given key?
void	delete(java.lang.String key)	Removes the key from the set if the key is present.
java.util.Iterator<java.lang.String>	iterator()	Returns all of the keys in the set, as an iterator.
static void	main(java.lang.String[] args)	Unit tests the PatriciaSET data type.
java.lang.String	toString()	Returns a string representation of this set.

从类继承的方法 java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

从接口继承的方法 java.lang.Iterable

forEach, spliterator

构造器详细资料

PatriciaSET

public PatriciaSET()

Initializes an empty PATRICIA-based set.

方法详细资料

add

public void add(java.lang.String key)

Adds the key to the set if it is not already present.

参数:

key - the key to add

抛出:

java.lang.IllegalArgumentException - if key is null

java.lang.IllegalArgumentException - if key is the empty string.

contains

public boolean contains(java.lang.String key)

Does the set contain the given key?

参数:

key - the key

返回:

true if the set contains key and false otherwise

抛出:

java.lang.IllegalArgumentException - if key is null

java.lang.IllegalArgumentException - if key is the empty string.

delete

public void delete(java.lang.String key)

Removes the key from the set if the key is present.

参数:

key - the key

抛出:

java.lang.IllegalArgumentException - if key is null

java.lang.IllegalArgumentException - if key is the empty string.

iterator

public java.util.Iterator<java.lang.String> iterator()

Returns all of the keys in the set, as an iterator. To iterate over all of the keys in a set named set, use the foreach notation: for (Key key : set).

指定者:

iterator 在接口中 java.lang.Iterable<java.lang.String>

返回:

an iterator to all of the keys in the set

toString

public java.lang.String toString()

Returns a string representation of this set.

覆盖:

toString 在类中 java.lang.Object

返回:

a string representation of this set, with the keys separated by single spaces

main

public static void main(java.lang.String[] args)

Unit tests the PatriciaSET data type. This test fixture runs a series of tests on a randomly generated dataset. You may specify up to two integer parameters on the command line. The first parameter indicates the size of the dataset. The second parameter controls the number of passes (a new random dataset becomes generated at the start of each pass).

参数:

args - the command-line arguments