ZArray

使用Morton顺序（也称为Z-order）索引的Z-order索引2D和3D数组，具有方便的API，用于常见的2D和3D访问模式。使用zarray代替Vec of Vecs通常可以提高性能，尤其是在模糊和细胞自动机等算法中。

Crates.io页面

关于ZArray

zarray包是一个轻量级的Rust库，提供了用于处理2D和3D数组的结构，使用内部Z-Order Morton索引来提高数据定位，从而改善缓存行性能。

快速入门指南

只需导入zarray::z2d::ZArray2D和/或zarray::z3d::ZArray3D，然后使用ZArray_D::new(...)函数初始化一个新实例。类型将自动从提供的默认值推断出来。请注意，只有实现了Copy特质的类型是允许的（即不是Vec或其他堆分配类型）。

例如，这里有一个使用ZArray2D的简单模糊操作示例，通常比使用Vec of Vecs快10-25%。

use zarray::z2d::ZArray2D;
let h: isize = 200;
let w: isize = 300;
let radius: isize = 3;
let mut src = ZArray2D::new(w as usize, h as usize, 0u8);
// set values
src.bounded_fill(100, 100, 200, 150, 255u8);
// sum neighbors values with ZArray
let mut blurred = ZArray2D::new(w as usize, h as usize, 0u16);
for y in 0..h { for x in 0..w {
  let mut sum = 0;
  for dy in -radius..radius+1 { for dx in -radius..radius+1 {
    sum += *src.bounded_get(x+dx, y+dy).unwrap_or(&0u8) as u16;
  } }
  blurred.set(x as usize, y as usize, sum/((2*radius as u16+1).pow(2))).unwrap();
} }

它是如何工作的

ZArray_D结构将数据存储在8x8或8x8x8的块中，使用Z-order索引访问每个块内的数据（如这里所述）。这样，每个维度最低的4位是交错排列的，这显著提高了数据局部性和缓存行获取效率（尽管不如Hilbert曲线那样多）。

为什么不直接使用Vec of Vecs（即Vec<Vec>）？

大多数情况下，使用Vec<Vec>会有很好的性能，只要你记得正确地结构化你的for循环。然而，当数据不是以线性方式访问时，例如在实现细胞自动机或模糊或光线追踪算法时，Vec<Vec>的性能可能会因频繁的RAM访问和缓存行缺失而受到严重影响。这是数据局部性对性能最重要的时刻。

为什么不是对整个数据数组进行Z-Order排序？

有两个原因：首先，Z-Order索引仅适用于正方形/立方体形状的数据，因此对于长而瘦的2D和3D数组，纯Z-Order索引会浪费大量内存。其次，在大多数CPU架构（Intel、AMD和Arm）中，内存以64字节缓存行进行访问，因此Z-order索引带来的性能提升在超过6位线性地址空间（即8x8或4x4x4）之后并不明显。

注意

只有具有Copy特质的类型才能存储在ZArrady_D结构体中。因此，zarray适用于所有数值类型和大多数简单数据结构，但不适用于Vec等堆分配数据类型。这种限制源于填充数据块初始值时的复杂性。此外，如果数据位于堆上，则不会比简单的Vec看到性能提升。

许可

此库提供MIT许可。换句话说：免费使用。

贡献

如果您想贡献，请继续在GitHub仓库上分叉并/或提交一个拉取请求