Скажем, у меня есть список целых чисел, где каждый элемент представляет собой число от 1 до 20. (Это не то, что я пытаюсь отсортировать.)

Теперь у меня есть массив «операций», где каждая операция:

Снимает определенные (известные) номера из спискаа также Добавляет некоторые другие (известные) номера в спискеа также Невозможно обработать список, если он содержит определенные (известные) номера в начале операции - вызовите этиПредотвращать

Изменить: может быть ноль или более чисел в каждом изДобавляет, Снимает, а такжеПредотвращать для каждой операции, и каждое число может появляться ноль или более раз в каждой группе для некоторой операции. Для любой данной операции,Добавляет а такжеСнимает не пересекаются,Предотвращать а такжеСнимает не пересекаются, ноДобавляет а такжеПредотвращать может перекрываться

Я хочу отсортировать массив операций так, чтобы для каждой операции:

Если операция имеетПредотвращать предметы, он помещается после операции, котораяСнимает эти цифры. Если не сразу после, не может бытьДобавляет операция, которая добавляет эти числа обратно между последнимиСнимает иПредотвращать.Если операцияСнимает предметы, все операции, которыеДобавляет любой из этих предметов ставится перед ним.

В случае циклической зависимости цепочка операций должна удалять как можно больше чисела также сообщите мне, что он не может удалить все номера.

Есть ли название / реализация для этого типа алгоритма, который превосходит тот, который у меня есть ниже?

Добавлено 8/23: Награда за удовлетворение требований сортировки с учетом как кодов операций (набор структур), так и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 чисел (без флагов).

Чтобы держать вещи в «черном ящике», я хочу, чтобы алгоритм упорядочения выполнял все операции, которые я пишу, чтобы они оказывали наибольшее влияние, и информировал меня о том, насколько успешно я упростил данные, которые в конечном итоге достигнут системы обработки. (ы). Естественно, я нацеливаюсь на самые сложные элементы в промежуточном представлении и упрощаю их до базовой арифметики указателей, где это возможно, что легче всего обрабатывать в ассемблерах. :)

После всего сказанного я добавлю еще одну заметку. Эффекты операции описаны как «атрибутные эффекты» в списке инструкций. В целом, операции ведут себя хорошо, но некоторые из них удаляют только числа, которые идут после других чисел (например, удаляют все 6, которые не следуют за 16). Другие удаляют все экземпляры определенного числа, которое содержит определенные флаги. Я займусь этим позже - ПОСЛЕ того, как я выясню основную проблему гарантированного добавления / удаления / предотвращения, перечисленную выше.

Добавлено 8/23: На этом изображенииВы можете увидетьcall инструкция (серая), которая имелаInstructionSemantics.NullCheck был обработанRemoveNullReferenceChecks преобразование, чтобы удалить флаг семантики в обмен на добавление другого вызова (без добавленной семантики к добавленному вызову). Теперь ассемблеру не нужно понимать / обрабатыватьInstructionSemantics.NullCheckпотому что он их никогда не увидит. Не критикуйте код ARM -это заполнитель на данный момент.