sandbox/ods/notes/chapter2.txt

71 lines
3.2 KiB
Plaintext

# Chapter 2 (Array-based lists)
These data structures have common advantages and limitations:
* constant-time access
* resizing the array adds potentially non-trivial complexity, both in time and
storage, as a new array generally must be created and the old array copied
over.
* arrays aren't dynamic, which means inserting or deleting in the middle of an
array requires shifting all the following elements.
With some careful management, the additional *amortised* complexity added by
resizing isn't too bad.
## Array stack
* Uses backing array *a*.
* Typically, the array will be larger than necessary, so an element *n* is
used to track the actual number of elements stored in the stack.
* Add and remove requires shifting all the elements after i (O(n - i)
complexity), ignoring potential calls to resize
* Resizing is triggered when we run out of room in an add or when a remove
brings us to the point where the array is more than 3n elements
* Resizing creates a new array of size 2n and copies all the elements over;
this then has complexity O(n).
* The analysis of add and remove didn't consider cost of resize.
* An amortised analysis is done instead that considers the cost of all calls
to add and remove, given a sequence of *m* calls to either.
* **Lemma**: if an empty ArrayStack is created and any sequence of *m* >= 1
calls to add and remove are performed, the total time spent in calls to
resize is O(m).
* Optimisations (FastArrayStack): using memcpy or std::copy to copy blocks of
data, not one element at a time.
## ArrayQueue
* ArrayStack is a bad implementation for a FIFO queue; either add or remove
must work from the head with index = 0, which means all calls to that
method will result in running time of O(n).
* We could do this with an infinite array, using an index into the head (*j*)
and the size of the backing array. We don't have an infinite array, so we'll
have to use modular arithmetic with a finite stack.
* **Theorem**: Ignoring the cost of calls to resize, an ArrayQueue supports the
operations add and remove in O(1) per operation. Beginning with an empty
ArrayQueue, any sequence of m add/remove operations will result in a total
of O(m) time resizing.
## ArrayDeque
* Implementation of adding and removing from both ends using the same circular
buffer technique.
* add/remove check whether their index is before or after the halfway point and
shift from there as a performance benefit.
* **Theorem**: Ignoring the cost of calls to resize, an ArrayDeque supports
set/get in time O(1) time per operation, and add/remove in O(1+min(i, n-1))
time per operation. Beginning with an empty ArrayDeque, performing any
sequence of m operations results in a total of O(m) time resizing.
## Dual Array Deque
* Same performance bounds as ArrayDeque using a pair of ArrayStacks.
* While not better, it's instructive as an example of building a more complex
data structure from simpler ones.
* List is represented as a pair of ArrayStacks; these are fast when a
modification occurs at the end. The DAD uses two ArrayStacks called
front and back.
* front: list elements that are 0...front.size()-1
* back: same but reverse order