10.4. Understanding the Performance of Collections
When choosing a collection for an application where performance is extremely important, you want to choose the right collection for the algorithm.
In many cases, you can reason about the performance of a
collection by understanding its basic structure. For instance, a
List is a singly linked list. It’s
not indexed, so if you need to access the one-millionth element of a
list(1000000), that will be slower than
accessing the one-millionth element of an
Array, because the
Array is indexed, whereas accessing the
element in the
traversing the length of the
In other cases, it may help to look at the tables. For instance,
Table 10-13 shows that
the append operation on a
eC, “effectively constant time.” As a result, I know I can create a
Vector in the REPL very quickly
However, as the table shows, the append operation on a
List requires linear time, so attempting to
List of the same size takes
a much (much!) longer time.
Before looking at the performance tables, Table 10-12 shows the performance characteristic keys that are used in the other tables that follow.
Table 10-12. Performance characteristic keys for the subsequent tables
The operation takes (fast) constant time.
The operation takes effectively ...