这是什么样的排序？

Question

假设我有一个整数列表,其中每个元素都是1到20之间的数字.(这不是我想要排序的.)

现在,我有一个"操作"数组,其中每个操作:

• 从列表中删除某些(已知)数字
• 并 在列表中添加某些其他(已知)数字
• 和无法处理的列表,如果它包含在操作开始时一定(已知)的数字-调用这些预防

编辑:每个操作的每个添加,删除和阻止中都可以有零个或多个数字,并且每个组的每个数字在某些操作中可以出现零次或多次.对于任何给定的操作,再添和移除了是不相交的,预防和移除了不相交,但再添和防止可能重叠.

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

• 如果操作具有" 预防"项,则会在删除这些编号的操作之后放置该项.如果不是紧接着,则不能有Adds操作在最后的Removes和Prevent之间添加这些数字.
• 如果操作删除项目,则添加任何这些项目的所有操作都将放在其前面.

如果存在循环依赖关系,则操作链应删除尽可能多的数字,并通知我它无法删除所有数字.

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

添加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: 在此图像中,您可以看到由转换处理的call指令(灰色)以删除语义标志以换取添加另一个调用(没有附加到调用的语义).现在汇编程序不需要理解/处理,因为它永远不会看到它们.没有批评ARM代码 - 它现在是占位符.InstructionSemantics.NullCheckRemoveNullReferenceChecksInstructionSemantics.NullCheck

Answer 1

目前这有效。当且仅当存在满足条件的排序时，它才会找到它。我还没有尝试优化它。它通过跟踪先前操作不允许添加哪些项目来反向工作。

编辑：我无法将此标记为答案，因为我已经从中受到了巨大的性能影响，而且我只有 17 次操作ITransform。现在排序需要 15 秒，哈哈/失败。

添加了 8/23：检查下一个代码部分，了解我如何将排序改进为实际上再次可行的东西。

编辑 8/25：当我跨越 25 个项目时，事情再次变得糟糕，但事实证明我在预排序中遇到了一个小问题，现在已经修复了。

    private static ITransform[] OrderTransforms(ITransform[] source)
    {
        return OrderTransforms(
            new List<ITransform>(source),
            new Stack<ITransform>(),
            new HashSet<OpCode>(source.SelectMany(transform => transform.RemovedOpCodes)),
            source.Aggregate(InstructionSemantics.None, (preventedSemantics, transform) => preventedSemantics | transform.RemovedSemantics)
            );
    }

    private static ITransform[] OrderTransforms(List<ITransform> source, Stack<ITransform> selected, HashSet<OpCode> preventAdd, InstructionSemantics preventSemantics)
    {
        if (source.Count == 0 && preventAdd.Count == 0)
            return selected.ToArray();

        for (int i = source.Count - 1; i >= 0; i--)
        {
            var transform = source[i];
            if ((preventSemantics & transform.InsertedSemantics) != 0)
                continue;

            if (preventAdd.Intersect(transform.InsertedOpCodes).Any())
                continue;

            selected.Push(transform);
            source.RemoveAt(i);
#if true
            var result = OrderTransforms(source, selected, new HashSet<OpCode>(preventAdd.Except(transform.RemovedOpCodes).Union(transform.PreventOpCodes)), (preventSemantics & ~transform.RemovedSemantics) | transform.PreventSemantics);
#else // this is even slower:
            OpCode[] toggle = preventAdd.Intersect(transform.RemovedOpCodes).Union(transform.PreventOpCodes.Except(preventAdd)).ToArray();
            preventAdd.SymmetricExceptWith(toggle);
            var result = OrderTransforms(source, selected, preventAdd, (preventSemantics & ~transform.RemovedSemantics) | transform.PreventSemantics);
            preventAdd.SymmetricExceptWith(toggle);
#endif
            if (result != null)
                return result;

            source.Insert(i, transform);
            selected.Pop();
        }

        return null;
    }

为了收回我的赏金，我通过启发式预处理数组，将排序时间从 15380 秒减少到 173 毫秒，然后立即进行上面的排序路由。

private static ITransform[] PreSortTransforms(ITransform[] source)
{
    // maps an opcode to the set of transforms that remove it
    ILookup<OpCode, ITransform> removals =
        source
        .SelectMany(transform => transform.RemovedOpCodes.Select(opcode => new
        {
            OpCode = opcode,
            Transform = transform
        }))
        .ToLookup(item => item.OpCode, item => item.Transform);

    // maps an opcode to the set of transforms that add it
    ILookup<OpCode, ITransform> additions =
        source
        .SelectMany(transform => transform.InsertedOpCodes.Select(opcode => new
        {
            OpCode = opcode,
            Transform = transform
        }))
        .ToLookup(item => item.OpCode, item => item.Transform);

    // maps a set of items (A) to a set of items (B), where ALL elements of B must come before SOME element of A
    ILookup<IEnumerable<ITransform>, ITransform> weakForwardDependencies =
        removals
        .SelectMany(item => additions[item.Key].Select(dependency => new
        {
            Transform = item,
            Dependency = dependency
        }))
        .ToLookup(item => item.Transform.AsEnumerable(), item => item.Dependency);

    /* For items in the previous map where set A only had one element, "somewhat" order the
     * elements of set B before it. The order doesn't [necessarily] hold when a key from one
     * relationship is a member of the values of another relationship.
     */
    var ordered =
        weakForwardDependencies
        .Where(dependencyMap => dependencyMap.Key.SingleOrDefault() != null)
        .SelectMany(dependencyMap => dependencyMap.AsEnumerable());

    // Add the remaining transforms from the original array before the semi-sorted ones.
    ITransform[] semiSorted = source.Except(ordered).Union(ordered).ToArray();

    return semiSorted;
}