4 个版本
0.2.1 | 2022年6月19日 |
---|---|
0.2.0 | 2022年3月27日 |
0.1.1 | 2022年1月29日 |
0.1.0 | 2022年1月28日 |
在 算法 中排名 852
115KB
2K SLoC
graph_safe_compare
可以处理循环、共享和深度非常深的图的等价谓词。实现了论文《Efficient Nondestructive Equality Checking for Trees and Graphs》中描述的算法。增加了支持递归而不使用调用栈以支持深度很大的图,并支持多路比较以支持对图进行排序的功能。
动机
使用 Rust 时,常见的是 #[derive(PartialEq)]
为类型,以便比较值。然而,这样的派生实现无法处理循环或深度非常深的输入,并且在给它们时会导致栈溢出,并且在给具有大量共享结构的输入时执行效率低下。
此 crate 提供了适用于通用图形形状的函数,这些函数是安全和高效的,可以用作 PartialEq
实现。
示例
退化的有向无环图形状
一个链,其中每个 My::Branch
的左右边都引用相同的下一个 Rc<My>
节点。如果没有共享结构的检测,它将像完美二叉树一样遍历,有 2^(depth+1)-2
次递归,但使用此 crate 的共享结构检测,它只使用 2*depth
次递归。
use graph_safe_compare::{robust, utils::RefId, Node};
use std::rc::Rc;
use My::*;
#[derive(Eq)]
enum My {
Leaf { val: i32 },
Branch { left: Rc<Self>, right: Rc<Self> },
}
impl My {
fn new_degenerate_shared_structure(depth: usize) -> Self {
let next = Leaf { val: 1 };
(0..depth).fold(next, |next, _| {
let next = Rc::new(next);
Branch { left: Rc::clone(&next), right: next }
})
}
}
impl PartialEq for My {
fn eq(&self, other: &Self) -> bool { robust::equiv(self, other) }
}
impl Node for &My {
type Cmp = bool;
type Id = RefId<Self>;
type Index = usize;
fn id(&self) -> Self::Id { RefId(*self) }
fn get_edge(&self, index: &Self::Index) -> Option<Self> {
match (self, index) {
(Branch { left, .. }, 0) => Some(left),
(Branch { right, .. }, 1) => Some(right),
_ => None,
}
}
fn equiv_modulo_edges(&self, other: &Self) -> Self::Cmp {
match (self, other) {
(Leaf { val: v1 }, Leaf { val: v2 }) => v1 == v2,
(Branch { .. }, Branch { .. }) => true,
_ => false,
}
}
}
fn main() {
// A depth that is fast with the `robust` variant of this crate, but that
// would be infeasible and either take forever, due to the great degree of
// shared structure, or cause stack overflow, due to the great depth, if
// another variant were used.
let depth = 1_000_000;
let a = My::new_degenerate_shared_structure(depth);
let b = My::new_degenerate_shared_structure(depth);
assert!(a == b);
// Prevent running the drop destructor, to avoid the stack overflow it would
// cause due to the great depth. (A real implementation would need a `Drop`
// designed to properly avoid that.)
std::mem::forget((a, b));
}
循环形状
一个非常简单的循环。如果没有共享结构的检测,它将无限递归并溢出栈,但使用此 crate 的共享结构检测,它不会这样做,并且它高效地完成。
涉及的类型更为复杂,以便能够构建循环。
use graph_safe_compare::{cycle_safe, utils::RefId, Node};
use std::{cell::{Ref, RefCell}, rc::Rc};
use Inner::*;
#[derive(Clone)]
struct My(Rc<RefCell<Inner>>);
enum Inner {
Leaf { val: i32 },
Branch { left: My, right: My },
}
impl My {
fn leaf(val: i32) -> Self { My(Rc::new(RefCell::new(Leaf { val }))) }
fn set_branch(&self, left: My, right: My) {
*self.0.borrow_mut() = Branch { left, right };
}
fn new_cyclic_structure() -> Self {
let cyc = My::leaf(0);
cyc.set_branch(My::leaf(1), cyc.clone());
cyc
}
fn inner(&self) -> Ref<'_, Inner> { self.0.borrow() }
}
impl PartialEq for My {
fn eq(&self, other: &Self) -> bool {
cycle_safe::equiv(self.clone(), other.clone())
}
}
impl Eq for My {}
impl Node for My {
type Cmp = bool;
type Id = RefId<Rc<RefCell<Inner>>>;
type Index = u32;
fn id(&self) -> Self::Id { RefId(Rc::clone(&self.0)) }
fn get_edge(&self, index: &Self::Index) -> Option<Self> {
match (index, &*self.inner()) {
(0, Branch { left, .. }) => Some(left.clone()),
(1, Branch { right, .. }) => Some(right.clone()),
_ => None,
}
}
fn equiv_modulo_edges(&self, other: &Self) -> Self::Cmp {
match (&*self.inner(), &*other.inner()) {
(Leaf { val: v1 }, Leaf { val: v2 }) => v1 == v2,
(Branch { .. }, Branch { .. }) => true,
_ => false,
}
}
}
fn main() {
let a = My::new_cyclic_structure();
let b = My::new_cyclic_structure();
assert!(a == b);
// (A real implementation would need to break the cycles, to allow them to
// be dropped.)
}
多方式比较以排序
use graph_safe_compare::{basic, utils::RefId, Node};
use std::cmp::Ordering;
#[derive(Eq)]
struct My(Vec<i32>);
impl Ord for My {
fn cmp(&self, other: &Self) -> Ordering { basic::equiv(self, other) }
}
impl PartialOrd for My {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl PartialEq for My {
fn eq(&self, other: &Self) -> bool { self.cmp(other).is_eq() }
}
impl Node for &My {
type Cmp = Ordering;
type Id = RefId<Self>;
type Index = u8;
fn id(&self) -> Self::Id { RefId(*self) }
fn get_edge(&self, _: &Self::Index) -> Option<Self> { None }
fn equiv_modulo_edges(&self, other: &Self) -> Self::Cmp {
self.0.iter().cmp(other.0.iter())
}
}
fn main() {
let mut array = [My(vec![1, 2, 3]), My(vec![3]), My(vec![1, 2])];
array.sort();
assert!(array == [My(vec![1, 2]), My(vec![1, 2, 3]), My(vec![3])])
}
设计
-
无
unsafe
代码。 -
无恐慌。
-
非常少的依赖。
-
组织成模块,为不同可能的图形状提供算法变体。形状有限的程序可以从使用仅支持所需内容的变体中受益,从而避免其他变体涉及的开销。例如,当只有浅循环形状时,
cycle_safe
模块提供的函数就足够了;例如,当只有无环的深度形状时,deep_safe
模块就足够了;例如,当可能的深度循环形状时,可以使用robust
模块。 -
一个
generic
模块公开了通用的 API(其他模块基于此构建),这使得可以自定义算法的参数(类型和常量)以创建自定义变体。 -
通用的 API 支持可失败的结果
Result
,具有自定义的错误类型,可用于实现自定义限制,例如内存使用量或执行时间的限制。
no_std
支持
虽然对循环和深度图的支持需要内部动态内存分配,但这可以在没有 std
或 alloc
crate 的情况下提供。这个 crate 的通用 API 被设计为自定义提供所需动态数据结构。当不带其 "std"
功能构建时,此 crate 是 no_std
。
文档
源代码有许多文档注释,这些注释被渲染为 API 文档。
在线查看:[http://docs.rs/graph_safe_compare](http://docs.rs/graph_safe_compare)
或者,您可以通过执行以下操作自行生成并本地查看:
cargo doc --open
测试
有单元测试和集成测试,可以通过执行以下操作运行:
cargo test --workspace
可以运行 ignored
测试来演示不支持某些形状的变体的局限性,并预期它们将导致堆栈溢出崩溃或花费很长时间。
有一个包测试使用 crate 作为 no_std
,可以通过执行以下操作运行:
cd test_no_std
cargo build --features graph_safe_compare/wyrng
基准测试
有变体的基准测试,使用具有非常少开销的节点类型,可以通过执行以下操作运行:
cargo +nightly bench --profile bench-max-optim