Programming with Judy

66
need. Typically, the rescaling is to
a larger size or volume. (2) The
ability not only to function well in
the rescaled situation, but to
actually take full advantage of it.
skip list A probabilistic
alternative to balanced trees that
was invented by William Pugh in
1987. Parallel lists at higher levels
skip geometrically more items.
Searching begins at the highest
level to quickly get to the right
part of the list, then uses
progressively lower level lists.
With enough levels, searching is
O(log n).
sparse array An array in which
some of the indexes may be
invalid. A sparse data set may be
represented by any of a large
variety of data structures; an array
is just one possibility. If the range
of the data set is large and the
valid indexes (keys) are sparse, a
simple array is wasteful of memory
although fast to access.
sort To arrange items in a
predetermined order. There are
dozens of sort algorithms, the
choice of which depends on factors
such as the number of items
relative to working memory,
knowledge of the orderliness of the
items or the range of the keys, the
cost of comparing keys versus the
cost of moving items, etc. (NIST)
T
tree structure A hierarchical
ADT in which the non-leaf nodes
(in the graph sense) contain
pointers to (that is, addresses of)
other nodes, in an acyclical and
non-multi-path fashion, possibly in
addition to other data stored in the
non-leaf nodes.
trie See digital tree.
U
ulong_t In C programming, an
integer type that is set to long
(maximum word length as defined
by the machine) and to unsigned (a
positive integer from 0 – n). On a
32-bit machine, ulong_t is 0 to 2
32
-
1. On a 64-bit machine, ulong_t is 0
to 2
64
- 1.
unbounded array An array
where the maximum size is not
arbitrarily limited (or bounded) at
less than the maximum word size
available to the machine. For
example, on a 32-bit machine an
unbounded array could be from 0
to 2
32
, while on a 64-bit machine
an unbounded array could be from
0 to 2
64
.
W
word A unit of memory that is the
same size as a pointer to pointer to
void, and/or an unsigned long, in
native C; typically 32 or 64 bits.