language-agnostic - 我应该从哪里开始解决这个优化问题？

Question

我有一个简单的程序，它从文件系统中读取一堆东西，过滤结果，然后打印出来。这个简单的程序实现了一种特定于领域的语言，使选择更加容易。此 DSL“编译”为如下所示的执行计划(输入为 C:\Windows\System32\* OR -md5"ABCDEFG"OR -tf):

Index  Success  Failure  Description
    0        S        1  File Matches C:\Windows\System32\*
    1        S        2  File MD5 Matches ABCDEFG
    2        S        F  File is file. (Not directory)

过滤器应用于给定的文件，如果成功，索引指针跳转到成功字段中指示的索引，如果失败，索引指针跳转到失败字段中指示的编号。 “S”表示文件通过过滤器，F表示文件应该被拒绝。

当然，基于简单文件属性 (!FILE_ATTRIBUTE_DIRECTORY) 检查的过滤器比基于文件 MD5 的检查要快得多，后者需要打开并执行文件的实际哈希。每个过滤器“操作码”都有一个与之关联的时间类； MD5获得高时序号，ISFILE获得低时序号。

我想对这个执行计划重新排序，以便尽可能少地执行需要很长时间的操作码。对于上述计划，这意味着它必须是:

Index  Success  Failure  Description
    0        S        1  File is file. (Not directory)
    1        S        2  File Matches C:\Windows\System32\*
    2        S        F  File MD5 Matches ABCDEFG

根据“龙书”，为三个地址代码选择最佳执行顺序是一个 NP 完全问题(至少根据该文本第二版的第 511 页)，但在那种情况下他们正在谈论关于机器的寄存器分配和其他问题。就我而言，实际的“中间代码”要简单得多。我想知道是否存在允许我将源 IL 重新排序为最佳执行计划的方案。

这是另一个例子:
{ C:\Windows\Inf* AND -tp } 或 { -tf AND NOT C:\Windows\System32\Drivers* }

解析为:

Index  Success  Failure  Description
    0        1        2  File Matches C:\Windows\Inf\*
    1        S        2  File is a Portable Executable
    2        3        F  File is file. (Not directory)
    3        F        S  File Matches C:\Windows\System32\Drivers\*

这是最优的:

Index  Success  Failure  Description
    0        1        2  File is file. (Not directory)
    1        2        S  File Matches C:\Windows\System32\Drivers\*
    2        3        F  File Matches C:\Windows\Inf\*
    3        S        F  File is a Portable Executable

Answer 1

听起来在编译为您的操作码之前选择最佳顺序可能更容易。如果您有一个解析树，并且它尽可能“扁平”，那么您可以为每个节点分配一个分数，然后首先按照最低的总分数对每个节点的子节点进行排序。

例如:

{ C:\Windows\Inf* AND -tp } OR { -tf AND NOT C:\Windows\System32\Drivers* }
         1             2          3                 4

      OR
     /  \
  AND    AND
 /  \   /   \
1    2 3     4

您可以按最低分数对 AND 节点 (1, 2) 和 (3, 4) 进行排序，然后将该分数分配给每个节点。然后根据他们 child 的最低分数对 OR 节点的 child 进行排序。

由于 AND 和 OR 是可交换的，因此此排序操作不会改变整个表达式的含义。