algorithm - 队列缩减算法？

Question

我有一个在客户端之间共享的事件队列，捕获用户事件并由另一个站点上的机器人执行。事件的一个例子可能是这样的:

CREATE FOLDER  /docs
CREATE FILE    /docs/journal.txt
DELETE FILE    /docs/blog.txt
MOVE   FOLDER  /docs/images /docs/photos
...

通常有一些事件可以简化为单个事件，或者没有。例如:

CREATE FOLDER /docs
RENAME FOLDER /docs /documents

可以简单地改成:

CREATE FOLDER /documents

还有类似的东西:

CREATE FOLDER /docs
RENAME FOLDER /documents
DELETE FOLDER /documents

可以从队列中完全删除。

这种减少/优化似乎是一个非常普遍的问题，在解决它之前我想尝试一些通用的解决方案。它看起来像一个寻路优化问题。

有什么想法吗？

Answer 1

我不知道有任何库或框架可以为您执行此操作。另一方面，您必须自己指定其背后的逻辑，在我看来，这将是大部分工作。

这是我会采用的方法:

1. 对操作进行拓扑排序(重命名文件夹“取决于”创建文件夹等...)

2. 每个没有依赖关系的命令都代表依赖关系树中的“根”。

3. 从每个根开始递归地折叠这些树。