Spatial Data Structures - Computer Graphics: Principles and Practice - page 1081

exploiting small-scale instruction parallelism. Which of these micro-optimizations
are worthwhile depends on your target platform, scenes, and queries, and how
much you are willing to tailor the data structure to them. We describe some of
the more timeless conventional wisdom accumulated over a few decades of the
field's collective experience. Check the latest SIGGRAPH course notes, EGSR
STAR report, and topics in series like GPU Pro for the latest advice on current
architectures.

37.5 List

A1D list is an ordered set of values stored in a way that does not take advantage
of the keys to lower the asymptotic order of growth time for query operations.
For instance, consider the example of a mapping from student grades to student
records encoded as a linked list that is described in Section 37.3.1. Each element
of the list contains a record with a grade and other student information. Searching
for a specific record by grade takes n comparisons for a list of n records if they are
unordered. At best, we could keep the list sorted on the keys and bring this down
to expected n / 2 comparisons, but it is still linear and still has a worst case of

n comparisons.
For the unsorted 1D list, there's little distinction between the expected space
and time costs of a dynamic array (see Listing 37.9) and a linked-list implemen-
tation (see Listing 37.8). For the sorted case, the array admits binary search while
the linked list simplifies insertion and deletion. The array implementation is good
for small sets of primitives with small memory footprints each; the linked list is a
better underlying representation for primitives with a large memory footprint, and
even more sophisticated spatial data structures are preferred for larger sets.

Listing 37.9: C++ implementation of a spatial list, using an array as the
underlying structure.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

template < class Value, class Trait = PrimitiveKeyTrait<Value> >
class List {
std::vector<Value> data

public :

int size() const {
return data.size();

}

/ * O(1) time * /
void insert( const Value& v) {
data.push_back(v);

}

/ * O(1) time * /
void remove( const Value& v) {
int i = data.find(v);
if (i != -1) {
// Remove the last
data[i] = data[data.size() - 1];
data.pop();

}

}

...

};