Effective Computation in Physics

Chapter 11. Important Data Structures in Physics

In every domain there are algorithms and data structures that seem to pop up over and over again. This is because of how useful these data structures are, rather than the everything-is-a-nail-when-all-you-have-is-a-hammer phenomenon. This chapter will present some of the important and common data structures for physics.

This is by no means a complete listing. Nor is this chapter meant to take the place of a formal computer science data structures course—the canonical data structures in that domain tend not to be the same as those in physics, though there is some overlap. Rather, this is meant to whet your appetite. Many of the data structures here have important variants, which will be mentioned but not discussed in detail.

We have already seen the most important data structure: arrays. Since these received an entire chapter, we will forgo talking about them here. Instead, we will cover:

Hash tables

Useful whenever you want to create associations between data

Data frames

Similar to structured arrays or tables, but with added capabilities that make them invaluable for experimental data

B-trees

Useful for managing array chunks and hierarchies

K-d trees

Space-partitioning data structures that are useful when trying to reason about the closest neighboring points in space

Let’s start at the top of this list and work our way down.

Hash Tables

Hash tables are everywhere in software development. The most common one that we have ...