Что это за сортировка?

Question

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

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

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

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

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

• Если операция содержит Запретить элементов, то после операции помещается , удаляющая эти числа. Если не сразу после этого, не может быть операции Adds , которая добавляет эти числа обратно между последними Removes и Prevent .
• Если операция Удаляет элементов, все операции, которые Добавляет любой из этих элементов, ставятся перед ней.

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

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

Добавлено 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 - на данный момент это заполнитель .

Answer 1

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

---

Редактировать: @ 280Z28 прокомментировал этот ответ:

Я сейчас использую топологическую сортировку, но технически она слишком сильна. Мне нужен какой-то способ иметь «слабые» группы ребер (одно или несколько ребер группы удерживаются в окончательном порядке)

Я не уверен, что следую тому, что вы, мужчины, относительно слабых групп ребер, если это относится к циклам разрыва, то топологическая сортировка может сделать это, как я это сделала, чтобы сохранить в подсчете , который показал, сколько непосещенных узлов указывают на этот узел. Затем для каждой итерации вы работаете с (одним из) узлами с минимальным в количестве , если в числе не равно нулю, это означает, что есть цикл, и вы произвольно прерываете цикл в Для завершения сортировки.

Answer 2

Это работает на данный момент. Если и только если заказ существует для удовлетворения условий, он найдет его. Я еще не пытался оптимизировать его. Он работает в обратном порядке, отслеживая, какие элементы не могут быть добавлены предыдущей операцией.

Редактировать: Я не могу пометить это как ответ, потому что я уже получаю от этого огромный удар по производительности и у меня всего 17 операций (ITransform с). Для сортировки требуется 15 секунд. Lol / fail.

Добавлено 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;
}

Answer 3

Я думаю, что вы говорите здесь об алгоритме упорядочения, а не об алгоритме сортировки. То есть вы хотите найти заказ, в котором перечислены свойства.

Я был бы удивлен, если бы уже существовал конкретный алгоритм упорядочения, который бы удовлетворял этим свойствам.

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

op1(adds(1),removes(2))
op2(adds(2),removes(1))

Answer 4

Поскольку то, может ли элемент X появляться следующим в списке, зависит не только от последнего элемента в списке, но и от предыдущих элементов, вы можете сказать, что топологическая сортировка слишком сильна. Это более общая проблема поиска, поэтому я бы попробовал более общее решение: поиск с возвратом или динамическое программирование. Первое всегда можно сделать, но иногда невероятно медленно; последнее приведет к гораздо более быстрому (но более интенсивному использованию памяти) решению, но для этого потребуется найти D.P. постановка проблемы, что не всегда возможно.