Angenommen, ich habe eine Liste mit ganzen Zahlen, wobei jedes Element eine Zahl von 1 bis 20 ist. (Das ist nicht das, was ich zu sortieren versuche.)

Jetzt habe ich eine Reihe von "Operationen", bei denen jede Operation:

Entfernt bestimmte (bekannte) Nummern aus der Listeund Fügt hinzu bestimmte andere (bekannte) Nummern in der Listeund Kann die Liste nicht bearbeiten, wenn sie zu Beginn des Vorgangs bestimmte (bekannte) Nummern enthält - rufen Sie diese aufVerhindern

Bearbeiten: Es können null oder mehr Zahlen in jedem von vorhanden seinFügt hinzu, Entfernt, undVerhindern für jede Operation und jede Zahl kann für eine Operation in jeder Gruppe null- oder mehrmals vorkommen. Für jede gegebene Operation,Fügt hinzu undEntfernt sind disjunkt,Verhindern undEntfernt sind disjunkt, aberFügt hinzu undVerhindern kann überlappen.

Ich möchte das Array der Operationen so sortieren, dass für jede Operation:

Wenn die Operation hatVerhindern Elemente, wird es nach einer Operation platziert, dieEntfernt diese Zahlen. Wenn nicht sofort danach, kann es keinen gebenFügt hinzu Operation, die diese Zahlen zwischen den letzten zurückaddiertEntfernt und dasVerhindern.Wenn die OperationEntfernt Artikel, alle Operationen, dieFügt hinzu Jedes dieser Elemente wird davor platziert.

Im Falle einer zirkulären Abhängigkeit sollte die Operationskette so viele Zahlen wie möglich entfernenund Bitte informieren Sie mich, dass nicht alle Nummern entfernt werden konnten.

Gibt es einen Namen / eine Implementierung für diese Art von Algorithmus, der / die den unten angegebenen übertrifft?

Hinzugefügt am 23.08 .: Das Kopfgeld dient zur Deckung der Sortieranforderungen unter Berücksichtigung sowohl der OpCodes (Menge von Strukturen) als auchInstructionSemantics (Satz von Bit-Flags aus einer Aufzählung).

Hinzugefügt später am 23.08 .: Durch heuristisches Vorsortieren des Quell-Arrays habe ich eine Performance-Verbesserung von 89: 1 erzielt. Siehe meine aktuelle Antwort für Details.

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...");
        }
    }
}

Bearbeiten: Unterhalb dieser Zeile finden Sie Hintergrundinformationen darüber, was ich eigentlich tue, falls sich die Leute fragen, warum ich das frage. Es ändert nichts am Problem, es zeigt nur den Umfang.

Ich habe ein System, das eine Liste von Elementen einliest und sie zur Verarbeitung an ein anderes "Modul" sendet. Jedes Element ist eine Anweisung in meiner Zwischendarstellung in einem Compiler - im Grunde genommen eine Zahl von 1 bis 300 plus eine Kombination von ungefähr 17 verfügbaren Modifikatoren (Flaggenaufzählung). Die Komplexität des Verarbeitungssystems (Maschinencode-Assembler) ist proportional zur Anzahl der möglichen eindeutigen Eingaben (Anzahl + Flags), bei denen ich jeden einzelnen Handler handcodieren muss. Darüber hinaus muss ich mindestens 3 unabhängige Verarbeitungssysteme (X86, X64, ARM) schreiben - die Menge an tatsächlichem Verarbeitungscode, die ich für mehrere Verarbeitungssysteme verwenden kann, ist minimal.

Durch das Einfügen von "Operationen" zwischen Lesen und Verarbeiten kann ich sicherstellen, dass bestimmte Elemente niemals zur Verarbeitung angezeigt werden. Dazu drücke ich die Zahlen und / oder Flags in Form anderer Zahlen aus. Ich kann jede "Transformationsoperation" in einer Blackbox codieren, indem ich ihre Auswirkungen beschreibe, was mir jede Menge Komplexität pro Operation erspart. Die Operationen sind für jede Transformation komplex und einzigartig, aber viel einfacher als das Verarbeitungssystem. Um zu zeigen, wie viel Zeit dies spart, werden durch eine meiner Operationen 6 der Flags vollständig entfernt, indem die gewünschten Effekte in Form von etwa 6 Zahlen (ohne Flags) geschrieben werden.

Um die Dinge in der Black Box zu halten, möchte ich, dass ein Ordnungsalgorithmus alle von mir geschriebenen Vorgänge aufnimmt, die größte Wirkung erzielt und mich darüber informiert, wie erfolgreich ich die Daten vereinfacht habe, die schließlich das Verarbeitungssystem erreichen (s). Natürlich ziele ich auf die komplexesten Elemente in der Zwischendarstellung ab und vereinfache sie, soweit möglich, auf die grundlegende Zeigerarithmetik, die in den Assemblern am einfachsten zu handhaben ist. :)

Nach alledem werde ich eine weitere Notiz hinzufügen. Die Operationseffekte werden in der Anweisungsliste als "Attributeffekte" beschrieben. Im Allgemeinen verhalten sich die Operationen gut, aber einige von ihnen entfernen nur Zahlen, die hinter anderen Zahlen liegen (z. B. alle 6en entfernen, die nicht auf eine 16 folgen). Andere entfernen alle Instanzen einer bestimmten Nummer, die bestimmte Flags enthält. Ich werde mich später darum kümmern - NACHDEM ich das oben aufgeführte Grundproblem des garantierten Hinzufügens / Entfernens / Verhinderns herausgefunden habe.

Hinzugefügt am 23.08 .: In diesem BildSie können eine sehencall Anweisung (grau), die hatteInstructionSemantics.NullCheck wurde von der verarbeitetRemoveNullReferenceChecks transformieren, um das Semantik-Flag zu entfernen, um einen weiteren Aufruf hinzuzufügen (auch ohne dem hinzugefügten Aufruf zugeordnete Semantik). Jetzt muss der Assembler nicht mehr verstehen / handhabenInstructionSemantics.NullCheck, weil es sie nie sehen wird. Keine Kritik am ARM-Code -es ist ein Platzhalter fürs Erste.