Part of #260. Dynamic arrays are found in most imperative languages like Python, Rust, Java, C++. Sometimes they are referred to as lists (Python), vectors (Rust/C++). A dynamic array generally has the following properties:
Indexable (Supports random-access in constant-time)
Iterable (Supports sequential-access)
Variable-size which can be reallocated at runtime
Fast removal/insertion at the front
Slow removal/insertion at the back and middle
Mutable and ephemeral (non-persistent)
Out-of-bounds insertion allocates new space.
Inside-bounds insertion shifts elements.
Out-of-bounds update/removal results in panic.
Use cases
A use case is to support "holistic windows" which are windows over a stream whose aggregate can only be calculated once the whole window has been observed. For example, to calculate the median over every nth element:
task Median(n: u32): ~i32 -> ~i32 {
val window = [];
loop {
for i in 0..n {
on event => window[i] = event;
}
if n % 2 == 0 {
emit (window[n/2] + window[n/2+1]) / 2;
} else {
emit window[n/2];
}
}
}
A holistic aggregation could also be for example to train a machine learning model. I think though that we should have a tensor type for this use-case which can support higher dimensional structures like ndarray.
list.append(x) - Add an item to the end of the list.
list.extend(iterable) - Extend the list by appending all the items from the iterable.
list.insert(i, x) - Insert an item at a given position.
list.remove(x) - Remove the first item from the list whose value is equal to x.
list.pop([i]) - Remove the item at the given position in the list, and return it.
list.clear() - Remove all items from the list.
list.index(x[, start[, end]]) - Return zero-based index in the list of the first item whose value is equal to x.
list.count(x) - Return the number of times x appears in the list.
list.sort(*, key=None, reverse=False) - Sort the items of the list in place.
list.reverse() - Reverse the elements of the list in place.
list.copy() - Return a shallow copy of the list.
Comprehensions
Indexing with ranges
Implementation
The dynamic array could be implemented by wrapping a Rust Vec<T>. Rust vectors are fast as long as you do not start shifting elements. Another option is the Rust VecDeque<T> which allows O(1) insertion at the front and back at the cost of some overhead. A third option is to use an unrolled linked list (or chunked array queue), which is a linked list of vectors, to support more dynamic access patterns.
Part of #260. Dynamic arrays are found in most imperative languages like Python, Rust, Java, C++. Sometimes they are referred to as lists (Python), vectors (Rust/C++). A dynamic array generally has the following properties:
Use cases
A use case is to support "holistic windows" which are windows over a stream whose aggregate can only be calculated once the whole window has been observed. For example, to calculate the median over every
nth element:A holistic aggregation could also be for example to train a machine learning model. I think though that we should have a
tensortype for this use-case which can support higher dimensional structures likendarray.Operations
Python's lists support the following operations:
list.append(x)- Add an item to the end of the list.list.extend(iterable)- Extend the list by appending all the items from the iterable.list.insert(i, x)- Insert an item at a given position.list.remove(x)- Remove the first item from the list whose value is equal to x.list.pop([i])- Remove the item at the given position in the list, and return it.list.clear()- Remove all items from the list.list.index(x[, start[, end]])- Return zero-based index in the list of the first item whose value is equal to x.list.count(x)- Return the number of times x appears in the list.list.sort(*, key=None, reverse=False)- Sort the items of the list in place.list.reverse()- Reverse the elements of the list in place.list.copy()- Return a shallow copy of the list.Implementation
The dynamic array could be implemented by wrapping a Rust
Vec<T>. Rust vectors are fast as long as you do not start shifting elements. Another option is the RustVecDeque<T>which allowsO(1)insertion at the front and back at the cost of some overhead. A third option is to use an unrolled linked list (or chunked array queue), which is a linked list of vectors, to support more dynamic access patterns.