队列减少算法？

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. 从每个根开始递归地折叠这些树。