🏁 数据结构 🏁

GridArray和滑动窗口实现用于DeepCausality。

滑动窗口实现在到达底层数据结构的末尾时会延迟回滚操作，以牺牲空间（内存）换取时间复杂度。具体来说，大小为N的滑动窗口可以容纳大约C-1个元素，其中C是总容量，定义为NxM，N为窗口大小，M为倍数。此crate有两种实现，一种基于vector，另一种基于const generic数组。const generic实现比基于vector的版本快得多。

ArrayGrid是一个类似于张量的标量、向量和低维矩阵的抽象。与张量不同，ArrayGrid限于低维（1到4），只允许标量、向量和矩阵类型。不过，所有这些都表示为一个静态固定大小的const generic数组。固定大小的数组允许进行多个编译器优化，包括缓存对齐的数据布局以及移除运行时数组边界检查，因为所有结构参数在开始时都是已知的，这为张量提供了显著的性能提升。

🤔 为什么？

1. 无依赖。
2. 无成本抽象。
3. 无不安全。100%安全且快速的Rust。

🚀 安装

只需运行

cargo add dcl_data_structures

或者，将以下内容添加到您的Cargo.toml中

dcl_data_structures = "0.4.2"

📚 文档

• API文档
• ArrayGrid设计与细节
• 滑动窗口摘要

⭐ 使用

查看

• 基准测试
• 示例
• 测试

ArrayGrid

重要细节

• 所有const generic参数都是必需的，无论您使用的是哪种ArrayType
• 要更改ArrayGrid类型，只需更改枚举即可。
• 编译后没有数组边界检查，因此您需要确保PointIndex不超过数组边界。

use dcl_data_structures::prelude::{ArrayGrid, ArrayType, PointIndex};

// Consts dimensions requires for const generic paramaters
// Use these to check whether your PointIndex stays within the Array boundaries.
const WIDTH: usize = 5;
const HEIGHT: usize = 5;
const DEPTH: usize = 5;
const TIME: usize = 5;

pub fn main(){
    // Make a simple 1D Array of type usize
    let array_type = ArrayType::Array1D;
    let ag: ArrayGrid<usize, WIDTH, HEIGHT, DEPTH, TIME> = ArrayGrid::new(array_type);

    // Create a 1D index
    let p = PointIndex::new1d(1);

    // Store a usize with the point index
    ag.set(p, 42);

    // Get the usize for the point index
    let res = ag.get(p);
    assert_eq!(res, 42);
    
    // Make a custom struct 
    // ArrayGrid requires Copy + Default to store MyStuct
    #[derive(Debug, Default, Copy, Clone)]
    struct MyStruct{
        number: usize,
        mod_five: bool,
    }
    
    // Make a 4D array aka matrix over x,y,z that stores My struct
    // Notice, only the ArrayType changes to do that. 
    let array_type = ArrayType::Array4D;
    let ag: ArrayGrid<MyStruct, WIDTH, HEIGHT, DEPTH, TIME> = ArrayGrid::new(array_type);

    // Create a new 4D point index where only time varies
    let idx_t0 = PointIndex::new4d(1, 1, 1, 0);
    let idx_t1 = PointIndex::new4d(1, 1, 1, 1);
    let idx_t2 = PointIndex::new4d(1, 1, 1, 2);

    // Create some data for each index 
    let my_struct_t0 = MyStruct{ number: 23, mod_five: false };
    let my_struct_t1 = MyStruct{ number: 24, mod_five: false };
    let my_struct_t2 = MyStruct{ number: 25, mod_five: true };

    // Store data
    ag.set(idx_t0, my_struct_t0);
    ag.set(idx_t1, my_struct_t1);
    ag.set(idx_t2, my_struct_t2);

    // Get data at t2
    let res = ag.get(idx_t2);
    
    // Verify results
    let exp_number = 25;
    assert_eq!(res.number, exp_number);
    let exp_mod = true;
    assert_eq!(res.mod_five, exp_mod);
}

滑动窗口

重要细节

• ArrayStorage和VectorStorage具有不同的签名，因为只有ArrayStorage需要const generics
• 大小表示滑动窗口可以存储的最大元素数。
• 容量表示在回滚之前可以存储的最大元素数。

use dcl_data_structures::prelude::{ArrayStorage, SlidingWindow,sliding_window};

// Size refers to the maximum number of elements the sliding window can store.
const SIZE: usize = 4;
// Capacity refers to the maximum number of elements before a rewind occurs.
// Note, CAPACITY > SIZE and capacity should be a multiple of size.
// For example, size 4 should be stored 300 times before rewind;
// 4 * 300 = 1200
const CAPACITY: usize = 1200;

// Util function that helps with type inference.
fn get_sliding_window() -> SlidingWindow<ArrayStorage<Data, SIZE, CAPACITY>, Data> {
    sliding_window::new_with_array_storage()
}

pub fn main(){
    let mut window = get_sliding_window();
    assert_eq!(window.size(), SIZE);

    // Filled means, the window holds 4 elements. 
    assert!(!window.filled());

    // If you try to access an element before the window id filled, you get an error.
    let res = window.first();
    assert!(res.is_err());

    let res = window.last();
    assert!(res.is_err());

    // Add some data
    window.push(Data { dats: 3 });
    window.push(Data { dats: 2 });
    window.push(Data { dats: 1 });
    window.push(Data { dats: 0 });
    assert!(window.filled());

    // Now we can access elements of the window
    // Last element added was 0
    let res = window.last();
    assert!(res.is_ok());
    let data = res.unwrap();
    assert_eq!(data.dats, 0);

    // First (oldest) element added was 3
    let res = window.first();
    assert!(res.is_ok());
    let data = res.unwrap();
    assert_eq!(data.dats, 3);

    // When we add more data after the window filled,
    // the "last" element refers to the last added
    // and the oldest element will be dropped.
    let d = Data { dats: 42 };
    window.push(d);

    let res = window.last();
    assert!(res.is_ok());

    let data = res.unwrap();
    assert_eq!(data.dats, 42);

    // Because 42 was added at the front,
    // 3 was dropped at the end therefore
    // the oldest element is now 2
    let res = window.first();
    assert!(res.is_ok());
    let data = res.unwrap();
    assert_eq!(data.dats, 2);
}

🙏 致谢

该项目受到了以下项目的启发

• sliding_features
• sliding-window-aggregation
• sliding_window_alt
• sliding_windows

👨‍💻👩‍💻 贡献

欢迎贡献，特别是与文档、示例代码和修复有关的内容。如果您不确定从哪里开始，只需打开一个问题并询问即可。

除非您明确声明，否则您提交给 deep_causality 的任何有意贡献，都将根据 MIT 许可证许可，不附加任何额外条款或条件。

📜 许可证

本项目受 MIT 许可证 许可。

👮️ 安全性

有关安全性的详细信息，请阅读 安全策略。

💻 作者

• Marvin Hansen.
• Github GPG 密钥 ID: 369D5A0B210D39BC
• GPG 指纹: 4B18 F7B2 04B9 7A72 967E 663E 369D 5A0B 210D 39BC