1 个不稳定版本
0.1.0 | 2022年1月29日 |
---|
#1231 in 算法
600KB
12K SLoC
bidivec
提供二维数组、向量和切片的库,包含电池。该库力求尽可能通用,然后进行合理的优化。
特性
该库通过宏、迭代器和索引的组合,以简单易用的方式支持二维容器。
例如
use bidivec::*;
// Create a new BidiVec<i32> using a macro
let mut bvec = bidivec!{
[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
};
// Overwrite cell (1,1) - the 5 - with 7+8
bvec[(1, 1)] = bvec[(0, 2)] + bvec[(1, 2)];
assert_eq!(bvec, bidivec!{
[1, 2, 3],
[4, 15, 6],
[7, 8, 9]
});
// Using iterators, collect the items in a vec
let v = bvec.iter().copied().collect::<Vec<i32>>();
// Assert the result is the expected one
assert_eq!(v, vec![1, 2, 3, 4, 15, 6, 7, 8, 9]);
// Change the sign of all items in the 2x2 rect located at (1,1)
for item in bvec
.iter_mut()
.on_rect(&BidiRect::new(1, 1, 2, 2,))
{
*item = -(*item);
}
assert_eq!(bvec, bidivec!{
[1, 2, 3],
[4, -15, -6],
[7, -8, -9]
});
数据结构
所有数据结构都提供(如果适用)迭代器支持、快速随机访问任何特定二维位置、插入和删除列和行、旋转、转置和裁剪。
支持的数据结构包括
BidiVec
:在Vec<T>
上实现的二维包装器,以保持线性布局以实现与本地代码的最佳互操作性。可以使用bidivec!
宏构建。BidiArray
:在Box<[T]>
上实现的二维包装器,也保持线性布局以实现与本地代码的最佳互操作性,并且保持固定长度(但宽度和高度可能变化)。可以使用bidiarray!
宏构建。BidiGrowVec
:在Vec<Vec<T>>
上实现的二维包装器,牺牲内存布局和局部性以在集合中间插入时提供更好的性能。可以使用bidigrowvec!
宏构建。BidiMutSlice
:在&mut [T]
切片上实现的二维包装器,牺牲一些功能以支持外部提供的数据存储,包括就地转换。BidiSlice
:在&[T]
切片上实现的双向包装器,具有与之前相同的注意事项,但不可变。
其他功能
当可能时,功能(有时通过适当的数据结构以优化方式实现)应用于由所有数据结构实现的BidiView
和BidiViewMut
特质,这些特质易于其他类型实现。
功能包括
- 将一个数据结构的矩形复制(粘贴)到另一个数据结构中,通过
Copy
和Clone
特质(使用editing::copy
和editing::clone_over
方法)或使用自定义混合函数(editing::blend
)。 - 具有自定义操作和比较的洪水填充(
editing::flood_fill
)。 - 实现转换以将数据结构视为转置、裁剪、旋转等。
- 对可变数据结构进行就地转换以转置、旋转、裁剪等。
- 迭代器,包括数据结构部分的迭代器,以及与项目一起枚举原始坐标的可能性。
- 用于二维瓦片地图的路径查找算法,对单个源、多个目的地执行Djikstra算法,以及对单个源、单个目的地的Djikstra或A*。
性能
性能相当快,对于大多数算法,即使原始性能不是此crate的重点。
在移动Ryzen 9上,在2000x2000地图(400万个节点)的对角线之间进行路径查找(无启发式方法)需要约1500ms找到最短路径,相同的洪水填充需要110ms填充整个区域,70ms填充棋盘图案。
在5000x5000地图(2500万个节点)上,路径查找需要约10秒,洪水填充需要约500ms。
在200x200地图(20万个节点)上,这是一种更合理的算法大小,路径查找降低到10ms,洪水填充约为1ms。
依赖关系
~270–730KB
~17K SLoC