14 releases
0.2.11 | Jun 10, 2024 |
---|---|
0.2.10 | Jun 9, 2024 |
0.2.2 | May 31, 2024 |
0.1.1 | May 22, 2024 |
#304 in Data structures
170 downloads per month
Used in 2 crates
(via kbnf)
54KB
1K
SLoC
JaggedArray
This crate provides multidimensional jagged arrays. It should be usable though some advanced features are not fully tested or in WIP status.
Features
- Multidimensional jagged arrays on a contiguous buffer.
- Methods for efficient array traversal, mutation, adding and removing last rows.
- Short index type(like
u8
,u16
) support.
Getting Started
Installation
Add the following to your Cargo.toml
:
[dependencies]
jaggedarray = "0.1.0"
Example
use jaggedarray::JaggedArray;
use jaggedarray::utils::U16;
let mut data = jagged_array::JaggedArray::<i32, U16, 3>::new();
data.new_row::<0>();
data.new_row::<1>();
data.push_to_last_row(1);
assert!(data[[0, 0, 0]] == 1);
assert!(data.view::<1, 2>([0]).view::<1, 1>([0])[[0]] == 1);
data.new_row::<1>();
data.push_to_last_row(4);
data.push_to_last_row(5);
assert!(data[[0, 1, 0]] == 4);
assert!(data[[0, 1, 1]] == 5);
data.new_row::<1>();
data.push_to_last_row(7);
data.push_to_last_row(8);
data.push_to_last_row(9);
assert!(data[[0, 2, 0]] == 7);
assert!(data[[0, 2, 1]] == 8);
assert!(data[[0, 2, 2]] == 9);
data.new_row::<0>();
data.new_row::<1>();
data.push_to_last_row(10);
data.push_to_last_row(11);
data.push_to_last_row(12);
data.push_to_last_row(13);
assert!(data[[1, 0, 0]] == 10);
assert!(data[[1, 0, 1]] == 11);
assert!(data[[1, 0, 2]] == 12);
assert!(data[[1, 0, 3]] == 13);
data.new_row::<0>();
data.new_row::<0>();
data.new_row::<1>();
data.push_to_last_row(100);
// assert!(data[[2, 0, 0]] == 100);
assert!(data[[3, 0, 0]] == 100);
data.append(data.clone());
assert!(data[[7, 0, 0]] == 100);
data.remove_last_row::<0>();
assert!(data[[0, 0, 0]] == 1);
assert!(data[[0, 1, 0]] == 4);
assert!(data[[0, 1, 1]] == 5);
assert!(data[[0, 2, 0]] == 7);
assert!(data[[0, 2, 1]] == 8);
assert!(data[[0, 2, 2]] == 9);
Benchmark
The performance of nested vectors heavily depends on usage patterns and allocator behaviour. If you can allocate all your vectors at once and/or your vector is really small, then nested vectors could be more efficient, especially at higher dimension. Otherwise, jagged arrays are more efficient.
sample-size/2d nested vector iteration 1000
time: [95.485 µs 96.837 µs 98.321 µs]
change: [+1.1201% +2.3958% +3.8359%] (p = 0.00 < 0.05)
Performance has regressed.
Found 46 outliers among 300 measurements (15.33%)
14 (4.67%) high mild
32 (10.67%) high severe
sample-size/2d jagged array iteration 1000
time: [71.956 µs 72.113 µs 72.275 µs]
change: [-0.5941% +0.0530% +0.7736%] (p = 0.88 > 0.05)
No change in performance detected.
Found 13 outliers among 300 measurements (4.33%)
8 (2.67%) high mild
5 (1.67%) high severe
sample-size/2d jagged array iteration 1000(U32)
time: [56.048 µs 56.211 µs 56.400 µs]
change: [-1.0558% -0.3365% +0.4911%] (p = 0.41 > 0.05)
No change in performance detected.
Found 13 outliers among 300 measurements (4.33%)
8 (2.67%) high mild
5 (1.67%) high severe
sample-size/2d nested vector iteration 10000
time: [16.935 ms 16.976 ms 17.025 ms]
change: [-0.5051% -0.1652% +0.1817%] (p = 0.35 > 0.05)
No change in performance detected.
Found 16 outliers among 300 measurements (5.33%)
9 (3.00%) high mild
7 (2.33%) high severe
sample-size/2d jagged array iteration 10000
time: [15.319 ms 15.348 ms 15.380 ms]
change: [-0.2571% +0.0457% +0.3378%] (p = 0.76 > 0.05)
No change in performance detected.
Found 10 outliers among 300 measurements (3.33%)
8 (2.67%) high mild
2 (0.67%) high severe
sample-size/2d jagged array iteration 10000(U32)
time: [15.135 ms 15.166 ms 15.201 ms]
change: [-0.4291% -0.1197% +0.1793%] (p = 0.46 > 0.05)
No change in performance detected.
Found 10 outliers among 300 measurements (3.33%)
7 (2.33%) high mild
3 (1.00%) high severe
sample-size/3d nested vector iteration 10
time: [96.544 ns 96.762 ns 96.996 ns]
change: [-1.1622% -0.5117% +0.2933%] (p = 0.17 > 0.05)
No change in performance detected.
Found 15 outliers among 300 measurements (5.00%)
7 (2.33%) high mild
8 (2.67%) high severe
sample-size/3d jagged array iteration 10
time: [212.26 ns 212.67 ns 213.11 ns]
change: [-1.4673% -0.9200% -0.3818%] (p = 0.00 < 0.05)
Change within noise threshold.
Found 11 outliers among 300 measurements (3.67%)
4 (1.33%) high mild
7 (2.33%) high severe
sample-size/3d jagged array iteration 10(U16)
time: [212.59 ns 213.00 ns 213.47 ns]
change: [-1.5934% -0.9125% -0.1971%] (p = 0.01 < 0.05)
Change within noise threshold.
Found 19 outliers among 300 measurements (6.33%)
8 (2.67%) high mild
11 (3.67%) high severe
sample-size/3d nested vector iteration 100
time: [38.712 µs 38.792 µs 38.874 µs]
change: [-2.2883% -1.7169% -1.1787%] (p = 0.00 < 0.05)
Performance has improved.
Found 18 outliers among 300 measurements (6.00%)
3 (1.00%) low mild
7 (2.33%) high mild
8 (2.67%) high severe
sample-size/3d jagged array iteration 100
time: [77.382 µs 77.567 µs 77.763 µs]
change: [-1.0918% -0.4742% +0.2046%] (p = 0.14 > 0.05)
No change in performance detected.
Found 18 outliers among 300 measurements (6.00%)
8 (2.67%) high mild
10 (3.33%) high severe
sample-size/3d jagged array iteration 100(U32)
time: [57.242 µs 57.371 µs 57.516 µs]
change: [-0.7841% -0.3735% -0.0037%] (p = 0.06 > 0.05)
No change in performance detected.
Found 10 outliers among 300 measurements (3.33%)
7 (2.33%) high mild
3 (1.00%) high severe
sample-size/3d nested vector iteration 500
time: [14.210 ms 14.237 ms 14.267 ms]
change: [-0.7055% -0.4232% -0.1433%] (p = 0.00 < 0.05)
Change within noise threshold.
Found 10 outliers among 300 measurements (3.33%)
6 (2.00%) high mild
4 (1.33%) high severe
sample-size/3d jagged array iteration 500
time: [7.3264 ms 7.3520 ms 7.3807 ms]
change: [-0.1417% +0.3313% +0.8417%] (p = 0.18 > 0.05)
No change in performance detected.
Found 11 outliers among 300 measurements (3.67%)
4 (1.33%) high mild
7 (2.33%) high severe
sample-size/3d jagged array iteration 500(U32)
time: [7.2936 ms 7.3134 ms 7.3355 ms]
change: [-0.9109% -0.5831% -0.2039%] (p = 0.00 < 0.05)
Change within noise threshold.
Found 5 outliers among 300 measurements (1.67%)
2 (0.67%) high mild
3 (1.00%) high severe
License
This project is licensed under the MIT License.
Contributing
Contributions are welcome! Please submit a pull request or open an issue on GitHub.
Dependencies
~1MB
~25K SLoC