#relation #feedback #input #dataset #input-output #scenario #standing

standing-relations

针对“反馈循环”场景优化,对移动数据集上的静态关系进行优化的数据结构

3个版本

0.1.2 2022年7月23日
0.1.1 2022年7月23日
0.1.0 2022年7月15日

数据结构类别中排名655

每月下载量27

MIT许可证

105KB
3K SLoC

静态关系

概述

此包提供了一种类似于differential-dataflow的接口,用于在移动数据集上创建静态关系。关键的是, differential-dataflow不同,这里的操作是单线程的,并针对快速周转而不是高吞吐量进行了优化。也就是说,此包旨在用于“反馈循环”场景,其中调用代码使用输出确定下一个要馈入的输入。

入门

要开始,创建一个CreationContext

use standing_relations::CreationContext;

let mut context = CreationContext::new();

和一些输入

let (mut input1, relation1) = context.new_input::<(char, usize)>();
let (mut input2, relation2) = context.new_input::<(char, String)>();

设置你的关系操作

let foo = relation2.save();
let bar = relation1.join(foo.get());
let baz = foo
    .get()
    .map(|(_, s)| (s.as_str().chars().next().unwrap_or('x'), s.len()));
let qux = bar.map(|(c, n, s)| (c, n + s.len())).concat(baz).distinct();
let arrangement: Output<(char, usize), _> = qux.into_output(&context);

开始插入数据。为此,您必须首先通过调用CreationContext::begin将您的CreationContext更改为一个ExecutionContext。这告诉系统您的关系图已完全构建,您不会对其进行任何更多更改

let mut context = context.begin();

input1.add(&context, ('a', 5));
input1.add(&context, ('b', 6));
input2.add(&context, ('b', "Hello".to_string()));
input2.add(&context, ('b', "world".to_string()));

提交更改

context.commit();

读取输出

assert_eq!(
    &*arrangement.get(&context),
    &HashMap::from_iter(vec![(('H', 5), 1), (('b', 11), 1), (('w', 5), 1)])
);

进行一些更改(并提交它们)

input1.remove(&context, ('b', 6));
input2.add(&context, ('a', "Goodbye".to_string()));
context.commit();

读取新的输出

assert_eq!(
    &*arrangement.get(&context),
    &HashMap::from_iter(vec![
        (('G', 7), 1),
        (('H', 5), 1),
        (('a', 12), 1),
        (('w', 5), 1)
    ])
);

技巧和注意事项

  • 如果编译器抱怨、运行缓慢或使用太多内存,请考虑使用Relation::dynamic来简化您的类型签名。Relation::t对于跟踪复杂关系的项目类型非常有用。

  • 仅在调用Output::get时,才会从输入到输出懒惰地传播更改。调用ExecutionContext::commit仅将挂起的更改标记为“准备”传播,并将任何下游输出标记为脏。

  • 如果您出于某种原因创建了多个CreationContext,则涉及来自不同上下文的InputOutputRelation的任何函数调用应导致带有消息“上下文不匹配”的运行时恐慌。

反馈算子

除了创建无环关系图之外,还可以创建具有反馈循环的有环图,其中关系输出会反馈到输入,直到所有集合稳定。要使用这种方式创建反馈循环,请使用三种方法之一:CreationContext::feedCreationContext::feed_orderedCreationContext::feed_while

CreationContext::feed将一个Relation连接到一个Input,使得每次调用ExecutionContext::commit时,都会将Relation参数表示的集合的任何更改反馈到Input参数。这会一直重复,直到集合停止变化。

CreationContext::feed_orderedfeed类似,但Relation参数还有一个排序键。不是将所有更改都反馈到Input,而只是将具有最小当前排序键的更改反馈。如果因此取消任何后续更改(如果它们的计数变为零),则根本不会将它们反馈。这在使用feed可能导致无限循环的情况下很有用。

CreationContext::feed_while接受一个Output作为参数,而不是一个Relation。它不是通过将更改传播到它的参数,而是在每次访问时发送该Output的全部内容。feed_while旨在在存在参数和调用者之间负反馈循环的情况下使用,调用者希望保留任何已访问的值,而不是立即删除它们。

CreationContext::interrupt接受一个要监视的Output。如果在发现Output非空时调用commit,则会立即停止运行并应用提供的延续。如果commit调用返回一个Some,则这表明已经发生这种情况。

如果有多个对feedfeed_orderedfeed_whileinterrupt的调用,则早期调用具有更高的优先级。优先级较高的反馈会在任何较低优先级反馈之前完成。

有关示例,请参阅dijkstra.rs

依赖项

~87KB