DynamicArray
Growable typed storage, initial capacity, allocation strategy, numerical operations, and time and space complexity.
DynamicArray<T> is a built in, growable, one dimensional data structure with an explicit scalar element type and an initial capacity. Logical length and allocated capacity are distinct. No import is required.
Construction
let readings = DynamicArray<Float64>(capacity: 2)
print(readings.len())
readings.append(3.0)
readings.append(1.0)
readings.append(2.0)
print(readings.len())
print(readings.capacity())
readings.sort()
print(readings.find(2.0))The output is 0, 3, 4, 1. The required constructor argument is capacity: Int64, between 0 and 1,000,000 inclusive. Construction initializes reserved native slots but creates no live elements.
The required element type is Int64, Float64, Bool, or String. DynamicArray<Any>, nullable elements, nested arrays, and user object element types are unsupported. Element arguments require exactly T; numeric promotion is explicit. Bool is a separate dtype. Float64 elements and computed results must be finite.
Storage, growth, and ownership
Int64 and Float64 use contiguous eight byte native slots; Bool uses one byte slots. String uses contiguous descriptors with separately owned text. Live elements do not carry individual Any tags.
When required length exceeds capacity, the new capacity is the larger of the required length and twice the old capacity, capped at 1,000,000. Zero capacity grows to one first. Requests above the limit fail. reserve allocates the requested minimum directly, without changing length. A nonnegative request at or below current capacity is an operation with no effect.
resize preserves the earlier prefix, initializes newly live elements from the required fill value, and discards trailing elements when shrinking. Removal and clear retain capacity. There is no automatic shrinking or shrink_to_fit. Pre reserving a known final size avoids intermediate reallocations.
let values = DynamicArray<Int64>(capacity: 0)
values.reserve(capacity: 8)
values.resize(size: 3, fill: 7)
let removed = values.remove_at(1)
print(values.len())
print(values.capacity())The output is 2, then 8.
A let binding prevents rebinding, not mutation. Assignment shares identity and storage. copy() returns an independent same type buffer retaining capacity. slice copies a half open range into an independent compact buffer; it is not a view. Equality compares identity. Values can be retained in Any, collection values, and user class fields. A matching typed cast validates family and dtype without conversion or copying.
reshape(shape: List) copies only the live elements into an independent fixed NDArray buffer. It discards unused capacity and preserves dtype and row major order. The shape requires 1 to 8 Int64 dimensions from 0 through 1,000,000 whose product equals current length; dimension inference is unavailable. Subsequent growth or mutation cannot affect the shaped result.
Methods and complexity
Let n be live length, C allocated capacity, C′ a replacement capacity, m a slice length, r a reshape rank, and k the number of elements added or removed by resize. Persistent scalar storage is O(C). The additional space column distinguishes auxiliary storage from result storage; during reallocation, the old and replacement buffers coexist.
| Method | Result | Time | Additional space |
|---|---|---|---|
DynamicArray<T>(capacity: Int64) | DynamicArray<T> | O(C) initialization | O(C) result |
append(value: T) | Unit | Amortized O(1); O(C′) when growing | O(1); O(C′) during growth |
capacity(), len() | Int64 | O(1) | O(1) |
clear() | Unit | O(n) | O(1) |
contains(value: T) | Bool | O(log n) sorted; O(n) otherwise | O(1) |
copy() | Independent DynamicArray<T> retaining C | O(C) | O(C) result |
fill(value: T) | Unit | O(n) | O(1), subject to String qualification |
find(value: T) | First matching Int64 index, or −1 | O(log n) sorted; O(n) otherwise | O(1) |
get(index: Int64) | T | O(1) | O(1), plus any returned String payload |
insert(index: Int64, value: T) | Unit | O(n − index + 1); O(C′) when growing | O(1); O(C′) during growth |
is_empty(), is_sorted() | Bool | O(1) | O(1) |
pop() | Removed T | O(1) | O(1), plus any returned String payload |
remove_at(index: Int64) | Removed T | O(n − index) | O(1), plus any returned String payload |
reserve(capacity: Int64) | Unit | O(1) operation with no effect; O(C′) allocation | O(1) operation with no effect; O(C′) allocation |
reshape(shape: List) | Independent NDArray<T> | O(n + r) | O(n + r) result |
resize(size: Int64, fill: T) | Unit | O(k); O(C′) when growing | O(1); O(C′) during growth, subject to String qualification |
reverse() | Unit | O(n) | O(1) |
set(index: Int64, value: T) | Unit | O(1) | O(1), subject to String qualification |
slice(start: Int64, stop: Int64) | Independent DynamicArray<T> | O(m) | O(m) result |
sort() | Unit | O(n log n), worst case | O(1) |
to_list() | Independent List | O(n) | O(n) result |
Reserved buffers are initialized. Construction and explicit reserve therefore have O(C) work even when length is zero. Doubling bounds cumulative scalar copying and initialization across successive appends by O(n + initial C), giving amortized O(1) append after construction. An individual append can reallocate and copy; the bound does not imply constant latency.
Sorting and searching
sort() uses in place, unstable ascending heapsort. Int64 and Float64 use numeric ordering. Bool orders false before true. String comparison is case sensitive lexicographic order of encoded bytes, without locale rules, natural number order, or Unicode normalization. Floating positive and negative zero compare equally. Custom comparators and a descending parameter are unavailable.
An exact count of adjacent inversions is maintained during mutation. is_sorted() is O(1), including empty and singleton inputs. Sorted find uses lower bound binary search; unsorted find scans linearly. Duplicates return the first matching index. contains uses the same strategy. No search tree is allocated.
Numerical methods
Int64 and Float64 provide the following operations. Binary operands require DynamicArray<T> with the same dtype and length. Result arrays are detached, compact numerical results; inputs remain unchanged.
| Method | Result | Time | Additional space |
|---|---|---|---|
add(other: DynamicArray<T>), sub(other: DynamicArray<T>), mul(other: DynamicArray<T>) | DynamicArray<T> | O(n) | O(n) result |
argmax(), argmin() | First tied Int64 index | O(n) | O(1) |
cumsum() | DynamicArray<T> | O(n) | O(n) result |
div(other: DynamicArray<Float64>): Float64 only | DynamicArray<Float64> | O(n) | O(n) result |
dot(other: DynamicArray<T>) | T | O(n) | O(1) |
max(), min(), sum() | T | O(n) | O(1) |
mean(), std(), variance() | Float64 | O(n) | O(1) |
scale(factor: T) | DynamicArray<T> | O(n) | O(n) result |
to_float() | DynamicArray<Float64> | O(n) | O(n) result |
to_tensor(rows: Int64, cols: Int64): Float64 only | Detached Tensor | O(n) | O(n) result |
Empty sum and dot return typed zero. Empty cumulative and elementwise results are valid. Mean, population variance, population standard deviation, extrema, and their indices require nonempty input. Population statistics divide by n; a sample statistic parameter is unavailable.
Int64 arithmetic checks intermediate operations and rejects overflow, including an overflowing intermediate that could later cancel. Integer division is unavailable. Float64 division rejects zero divisors and nonfinite results. Explicit to_float() can round large integer values. Scaled statistics reduce unnecessary overflow but remain subject to representable range and roundoff.
to_tensor requires positive dimensions whose product equals n and returns a detached row major Tensor. The array does not record gradients. Inference of the bridge result needs no import; explicit Tensor annotations and operations require a numerical module.
let x = DynamicArray<Float64>(capacity: 3)
x.append(1.0)
x.append(2.0)
x.append(3.0)
let y = x.scale(factor: 2.0)
print(x.dot(y))
print(x.cumsum().to_list())
let detached = x.to_tensor(rows: 1, cols: 3)String complexity
Persistent String storage is O(C + B), where B is total owned text bytes. Every operation that copies, returns, or releases text includes that byte cost. Reallocation copies live payloads as well as descriptors. get, pop, and remove_at include the owned returned String payload in result space.
String fill stages a full replacement buffer for failure atomicity: O(C + copied/released bytes) time and O(C + new text bytes) temporary space. String resize within capacity stages newly added text, using O(k + added text bytes) temporary space. Clearing and shrinking include payload destruction costs. Searching performs O(log n) or O(n) String comparisons. For maximum compared length k, sorting takes O(n log n · (1 + k)) worst case time and O(1) auxiliary descriptors.
Bounds and errors
Indices are zero based. get, set, and remove_at require 0 <= index < n. insert also permits index n. Negative indices are unsupported. Slices require 0 <= start <= stop <= n; pop requires a nonempty array.
Invalid size/capacity, bounds, nonfinite values, integer overflow, incompatible operands, invalid reshape, and logical quota exhaustion report source located R3001. Unsupported types/methods and statically known dtype mismatches are checked before execution. Host allocation failure uses E9003. Failed native mutation leaves existing contents unchanged. A persistent session runtime error clears session state.
Each buffer is limited to 1,000,000 slots. All typed array buffers in a heap share a 64 MiB logical quota for capacity slots, String descriptors, and text payloads. It is separate from collection slots and Tensor limits. Allocation bounds constrain committed logical heap storage, excluding allocator overhead, transient reallocation/replacement buffers, and total process memory. Unreachable buffers are reclaimed after successful persistent session cells.
Development inspection
Development observations show dtype, live length, capacity, sorted status, and at most 16 copied elements. Unused capacity is not exposed. Production omits recording without changing validation, allocation policy, or numerical algorithms. Use a new report directory:
aner examples/arrays_basic.aner --dev artifacts/dynamic-array-inspectionExamples and related references
The array construction tutorial, numerical tutorial, VS Code array notebook, and Jupyter array notebook exercise the typed array APIs.
- Array: fixed length typed sequences.
- NDArray: fixed multidimensional shapes and broadcasting.
- Tensor: numerical computation and differentiation.
- Development mode: reports and notebook observations.