algorithm - 这是什么样的排序？

Question

假设我有一个整数列表，其中每个元素是一个从1到20的数字。(这不是我要排序的内容。)

现在，我有一个“操作”数组，其中每个操作:

从列表

中删除某些(已知)数字

和将某些其他(已知)数字添加到列表

中

和如果在操作开始时包含某些(已知)数字，则无法处理该列表-调用这些阻止

编辑:对于每个操作，“添加”，“删除”和“阻止”中的每个可以有零个或多个数字，并且对于某些操作，每个数字在每个组中可以出现零个或多个时间。对于任何给定的操作，“添加和删除”是不相交的，“防止”和“删除”是不相交的，但是“添加”和“阻止”可能会重叠。

我想对操作数组进行排序，以便对每个操作:

如果该操作具有“阻止”项目，则将其放置在“删除”这些数字的操作之后。如果不是紧接在后，则不能执行“加法”操作，以将这些数字加到最后一次“删除”和“阻止”之间。

如果该操作删除了项目，则添加这些项目中的任何一项的所有操作都将放在其前面。

在循环依赖的情况下，操作链应删除尽可能多的数字 和通知我，它无法删除所有数字。

这种算法的名称/实现是否优于我下面的算法？

已添加8/23:赏金用于满足同时考虑OpCodes(结构集)和InstructionSemantics(枚举中的位标志集)的排序要求。

稍后在8/23中添加:我通过试探性地对源数组进行预排序，使性能提高了89:1。有关详细信息，请参见我当前的答案。

namespace Pimp.Vmx.Compiler.Transforms
{
    using System;
    using System.Collections.Generic;
    using System.Reflection.Emit;

    internal interface ITransform
    {
        IEnumerable<OpCode> RemovedOpCodes { get; }
        IEnumerable<OpCode> InsertedOpCodes { get; }
        IEnumerable<OpCode> PreventOpCodes { get; }

        InstructionSemantics RemovedSemantics { get; }
        InstructionSemantics InsertedSemantics { get; }
        InstructionSemantics PreventSemantics { get; }
    }

    [Flags]
    internal enum InstructionSemantics
    {
        None,
        ReadBarrier = 1 << 0,
        WriteBarrier = 1 << 1,
        BoundsCheck = 1 << 2,
        NullCheck = 1 << 3,
        DivideByZeroCheck = 1 << 4,
        AlignmentCheck = 1 << 5,
        ArrayElementTypeCheck = 1 << 6,
    }

    internal class ExampleUtilityClass
    {
        public static ITransform[] SortTransforms(ITransform[] transforms)
        {
            throw new MissingMethodException("Gotta do something about this...");
        }
    }
}

编辑:此行下面是有关我实际上在做什么的背景信息，以防人们想知道为什么我问这个问题。它不会改变问题，仅显示范围。

我有一个系统，该系统读取项目列表并将其发送到另一个“模块”进行处理。每一项都是我在编译器中的中间表示形式中的一条指令-基本上是1到〜300之间的数字，加上大约17个可用修饰符(标志枚举)的某种组合。处理系统(机器代码汇编器)的复杂性与可能的唯一输入的数量(数量+标志)成正比，在这里我必须对每个处理程序进行手工编码。最重要的是，我必须至少编写3个独立的处理系统(X86，X64，ARM)-我可以用于多个处理系统的实际处理代码量很小。

通过在读取和处理之间插入“操作”，我可以确保某些项目永远不会出现以进行处理-我通过用其他数字表示数字和/或标志来做到这一点。我可以通过描述每个“转换操作”的效果来对它们进行编码，从而为每个操作节省了大量的复杂性。每个转换的操作都是复杂且唯一的，但比处理系统要容易得多。为了显示这节省了多少时间，我的一项操作通过以大约6个数字(不带标志)的形式写入它们所需的效果，从而完全删除了6个标志。

为了将事情保留在黑匣子中，我希望一种排序算法来处理我编写的所有操作，使它们产生最大的影响，并告知我在简化最终将到达处理系统的数据方面取得了多么大的成功。 (s)。自然，我瞄准了中间表示形式中最复杂的项目，并在可能的情况下将它们简化为基本指针算法，这在汇编程序中最容易处理。 :)

话虽如此，我将再添加一个注释。操作效果在指令列表中被描述为“属性效果”。通常，这些运算的性能良好，但是其中一些仅删除掉在其他数字之后的数字(例如删除所有不跟16的6)。其他人删除包含特定标志的特定编号的所有实例。我将在稍后处理这些-在找出以上列出的保证添加/删除/阻止的基本问题之后。

已添加8/23: In this image，您可以看到一条 call指令(灰色)，其中 InstructionSemantics.NullCheck已由 RemoveNullReferenceChecks转换处理，以删除语义标志，以换取添加另一个调用(也没有在添加的调用上附加语义)。现在，汇编程序不需要理解/处理 InstructionSemantics.NullCheck，因为它将永远不会看到它们。不要批评ARM代码 it's a placeholder for now。

Answer 1

听起来像topological sort，可以将每个操作都视为有向图中的一个节点，其边缘是您提到的约束。

编辑: @280Z28评论了这个答案:

I'm using a topological sort right now, but it's technically too strong. I need some way to have "weak" groups of edges (one or more edges of the group holds in the final ordering)

我不确定我是否遵循您关于弱边缘组的看法，如果这是指破坏循环，那么拓扑排序可以做到这一点，我这样做的方法是维持一个计数，该计数显示多少 未访问的节点指向这个节点。然后，对于每次迭代，您都在in数最少的节点上(其中一个)工作，如果in数不为零，则意味着存在一个循环，您可以任意中断该循环以完成排序。