-
Notifications
You must be signed in to change notification settings - Fork 11
Efficient Collections
We need to figure out what kinds of data structures should back our collections.
Requirements:
- Persistence. In this day and age, our immutable structures should be persistent.
- Deterministism. Extensionally, if we have two collections
c1andc2, andc1 == c2, then for all verbsvand arguments*args,c1.v(*args) == c2.v(*args), and so forth for further messages sent to the results of those sends, ad infinitum. This means that things like iteration order should be predictable.
First we need to determine Const structures. All Flex structures can be modeled as mutable wrappers around persistent Const structures, and all Const structures are persistent with ConstList.with/1, ConstList.with/2, ConstSet.with/1, ConstSet.without/1, ConstMap.with/2, etc.
We have a problem. Objects are not always comparable. We can't simply make all objects have comparison operations; this would not fix the problem that 42 > "the answer" is neither true nor false. (It is, of course, an exceptional condition.)
We could hash objects. However, this requires defining a hash method which pervades all objects in the object model and is completely stable. This would, in turn, require fixing the hashing method for all time, which is not the kind of commitment we're prepared to make. So hash tables cannot be used on their own; a list of keys would be required as well.
ConstList would seem to be the easiest of these to plan for, but even here, there are several possibilities:
| operation | array | list | list (reversed) | deque |
|---|---|---|---|---|
| add/1 | O(n + m) | O(n) | O(m) | O(min(n, m)) |
| contains/1 | O(n) | O(n) | O(n) | O(n) |
| diverge/0 | O(n) | O(1) | O(1) | O(1) |
| get/1 | O(1) | O(n) | O(n) | O(n) |
| last/0 | O(1) | O(n) | O(1) | O(1) |
| with/1 | O(n) | O(n) | O(1) | O(1) |
| with/2 | O(n) | O(n) | O(n) | O(n) |
sort/0 is always going to be O(n lg n). size/0 is always going to be O(1).
| operation | array | list | list (reversed) | deque |
|---|---|---|---|---|
| add/1 | O(n + m) | O(n) | O(m) | O(min(n, m)) |
| contains/1 | O(n) | O(n) | O(n) | O(n) |
| get/1 | O(1) | O(n) | O(n) | O(n) |
| insert/2 | O(n) | O(n) | O(n) | O(n) |
| last/0 | O(1) | O(n) | O(1) | O(1) |
| snapshot/0 | O(n) | O(1) | O(1) | O(1) |
| push/1 | amortized O(1) | O(n) | O(1) | O(1) |
| pop/0 | O(1) | O(n) | O(1) | O(1) |
In order to be deterministic, sets generally have to be always ordered, either according to insertion order or some stable internal total ordering.
| operation | ConstList | ConstList + hash table |
|---|---|---|
| and/1 | O(n * m) | O(n * m) |
| butNot/1 | O(n * m) | O(n) |
| contains/1 | O(n) | O(1) |
| intersects/1 | O(n * m) | O(min(n, m)) |
| or/1 | O(n * m) | O(n + m) |
| with/1 | O(n) | O(n) |
| without/1 | O(n) | O(n) |
ConstMap complexities are the same as ConstSet complexities.