什么计算机科学概念涉及组合多个条件以进行有效评估?

What computer science concept deals with combining multiple conditions for efficient evaluation?

我有一个现实世界的问题要解决。

有一个应用程序处理来自网络套接字的传入请求。

请求由多个属性值对组成。

我希望管理员能够通过请求中的属性值对过滤处理这些请求时生成的调试日志记录。

管理员将输入多个条件,每个条件映射到不同的输出流,例如:

以上条件的高效评估要求用户只需要被评估一次。例如if (&user != 'bar') 那么我们就可以停止处理了。

很明显需要某种树结构...

我还应该提一下,在我描述的场景中,条件评估没有副作用(您不能执行分配)。因此,大多数逻辑运算符的操作数都可以毫无问题地重新排序。

处理这个问题的计算机科学概念是什么?它有一些 NP 完整的气味。

更新:跟进问题。是否有任何 C 库或表达式语言(如 BPF)可以帮助解决现实世界的问题,或提供计算机科学概念的通用实现?

一般来说,这叫做"boolean algebra"。可以使用 Karnaugh maps or, in general, other circuit minimization techniques 等技术简化布尔代数表达式。这个领域可以追溯到基本的数字逻辑(在数字计算机出现之前)并且得到了很好的研究。

在特定情况下,例如搜索线性日志文件,您不太可能加快程序速度,因为任何搜索未索引日志文件的程序都可能受 IO 限制。或者在过滤日志条目的情况下,与您的应用程序执行的任何其他操作的成本相比,评估过滤器的成本可能是最小的。

我不知道这是否符合 "computer science concept",但您可以使用数据流规划/综合/调度技术来解决您的问题。当您的操作具有不同的相关成本时,这尤其有用(字符串的模式匹配可能比字节的位精确比较更昂贵)。

基本上每个 "atomic" 条件(如 user == 'bar')都会成为(我认为)称为序列图的节点。复合条件(&&,可能 ||!)然后成为此(有向)图中的更多节点,从它们的操作数(节点)到它们有一条边。

可以给定节点"durations",例如原子字符串比较需要 20 个时间单位,而 && 多个(已评估)条件只需要 1 个时间单位。

然后您可以在此图上使用不同的调度算法。候选人(据我所知)是 ASAP(尽快)、ALAP(尽可能晚)、"List Scheduling" 和 Force Directed Scheduling.

这些调度算法基本上将您的图形编译成一个有序列表,指定一个理想的(或启发式的)顺序,您应该按照该顺序评估操作数以获得所有(完整)条件表达式的结果。这并不是您真正需要的

设计上述调度算法是为了在有限的(硬件)资源(能够执行由节点表示的操作)可用时生成计划,但都关心评估完整表达式。

您需要对此进行扩展,以纳入比较可能 return 导致计算更多节点毫无意义的结果的可能性。不过我不知道怎么做,所以这是你需要自己弄清楚的事情。

为了做到这一点,我会编写一个程序 - 给定一些复杂的条件和一些(最好是大的)测试数据 - 找到(随机爬山,模拟退火,遗传算法)一个好的时间表,使得平均值期望时间很好,然后让不同的(从上图设计的)调度算法与之竞争。

以上都是关于静态调度的,还有动态调度算法可以利用原子条件的(逐步已知的)结果来可能做出更好的计划。