collections

Performance Characteristics

The previous explanations have made it clear that different collection types have different performance characteristics. That’s often the primary reason for picking one collection type over another. You can see the performance characteristics of some common operations on collections summarized in the following two tables.

Performance characteristics of sequence types:

headtailapplyupdateprependappendinsert
immutable
ListCCLLCL-
StreamCCLLCL-
VectoreCeCeCeCeCeC-
StackCCLLCCL
QueueaCaCLLLC-
RangeCCC----
StringCLCLLL-
mutable
ArrayBufferCLCCLaCL
ListBufferCLLLCCL
StringBuilderCLCCLaCL
MutableListCLLLCCL
QueueCLLLCCL
ArraySeqCLCC---
StackCLLLCLL
ArrayStackCLCCaCLL
ArrayCLCC---

Performance characteristics of set and map types:

lookupaddremovemin
immutable
HashSet/HashMapeCeCeCL
TreeSet/TreeMapLogLogLogLog
BitSetCLLeC1
ListMapLLLL
mutable
HashSet/HashMapeCeCeCL
WeakHashMapeCeCeCL
BitSetCaCCeC1
TreeSetLogLogLogLog

Footnote: 1 Assuming bits are densely packed.

The entries in these two tables are explained as follows:

CThe operation takes (fast) constant time.
eCThe operation takes effectively constant time, but this might depend on some assumptions such as maximum length of a vector or distribution of hash keys.
aCThe operation takes amortized constant time. Some invocations of the operation might take longer, but if many operations are performed on average only constant time per operation is taken.
LogThe operation takes time proportional to the logarithm of the collection size.
LThe operation is linear, that is it takes time proportional to the collection size.
-The operation is not supported.

The first table treats sequence types–both immutable and mutable–with the following operations:

headSelecting the first element of the sequence.
tailProducing a new sequence that consists of all elements except the first one.
applyIndexing.
updateFunctional update (with updated) for immutable sequences, side-effecting update (with update for mutable sequences.
prependAdding an element to the front of the sequence. For immutable sequences, this produces a new sequence. For mutable sequences it modified the existing sequence.
appendAdding an element and the end of the sequence. For immutable sequences, this produces a new sequence. For mutable sequences it modified the existing sequence.
insertInserting an element at an arbitrary position in the sequence. This is only supported directly for mutable sequences.

The second table treats mutable and immutable sets and maps with the following operations:

lookupTesting whether an element is contained in set, or selecting a value associated with a key.
addAdding a new element to a set or key/value pair to a map.
removeRemoving an element from a set or a key from a map.
minThe smallest element of the set, or the smallest key of a map.
blog comments powered by Disqus