Powiedzmy, że mam listę liczb całkowitych, gdzie każdy element jest liczbą od 1 do 20. (Nie to próbuję sortować).

Teraz mam tablicę „operacji”, gdzie każda operacja:

Usuwa pewne (znane) liczby z listyi Dodaje niektóre inne (znane) numery na liściei Nie jest w stanie obsłużyć listy, jeśli zawiera pewne (znane) liczby na początku operacji - wywołaj jeZapobiec

Edytuj: w każdym z nich może być zero lub więcej liczbDodaje, Usuwa, iZapobiec dla każdej operacji, a każda liczba może pojawić się zero lub więcej razy w każdej grupie dla niektórych operacji. Dla każdej danej operacjiDodaje iUsuwa są rozłączne,Zapobiec iUsuwa są rozłączne, aleDodaje iZapobiec może się pokrywać.

Chcę posortować tablicę operacji, aby dla każdej operacji:

Jeśli operacja maZapobiec elementy, które są umieszczane po operacjiUsuwa te liczby. Jeśli nie od razu, nie może byćDodaje operacja, która dodaje te liczby z powrotem między ostatnimUsuwa iZapobiec.Jeśli operacjaUsuwa przedmioty, wszystkie operacje, któreDodaje każdy z tych przedmiotów jest umieszczony przed nim.

W przypadku zależności kołowej łańcuch operacji powinien usuwać jak najwięcej liczbi poinformuj mnie, że nie może usunąć wszystkich numerów.

Czy istnieje nazwa / implementacja tego typu algorytmu, który przewyższa ten, który mam poniżej?

Dodano 8/23: Bounty służy do pokrycia wymagań sortowania, biorąc pod uwagę zarówno OpCodes (zbiór struktur), jak iInstructionSemantics (zestaw flag bitowych z wyliczenia).

Dodano później 8/23: Poprawiłem wydajność 89: 1 poprzez heurystyczne wstępne sortowanie tablicy źródłowej. Zobacz moją obecną odpowiedź po szczegóły.

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

Edytuj: Poniżej tej linii znajdują się podstawowe informacje o tym, co aktualnie robię, na wypadek gdyby ludzie zastanawiali się, dlaczego o to pytam. To nie zmienia problemu, tylko pokazuje zakres.

Mam system, który odczytuje listę elementów i wysyła ją do innego „modułu” w celu przetworzenia. Każdy element jest instrukcją w mojej pośredniej reprezentacji w kompilatorze - zasadniczo liczba od 1 do ~ 300 plus pewna kombinacja około 17 dostępnych modyfikatorów (wyliczanie flag). Złożoność systemu przetwarzania (asembler kodu maszynowego) jest proporcjonalna do liczby możliwych unikalnych wejść (liczba + flagi), gdzie muszę ręcznie kodować każdy pojedynczy program obsługi. Ponadto muszę napisać co najmniej 3 niezależne systemy przetwarzania (X86, X64, ARM) - ilość rzeczywistego kodu przetwarzania, którego mogę użyć dla wielu systemów przetwarzania, jest minimalna.

Poprzez wstawienie „operacji” pomiędzy odczytem i przetwarzaniem, mogę zapewnić, że pewne elementy nigdy nie pojawią się do przetwarzania - robię to, wyrażając liczby i / lub flagi w kategoriach innych liczb. Mogę kodować każdą „operację transformacji” w czarnej skrzynce, opisując jej efekty, co oszczędza mi mnóstwo złożoności na operację. Operacje są złożone i unikalne dla każdej transformacji, ale znacznie łatwiejsze niż system przetwarzania. Aby pokazać, ile czasu to oszczędza, jedna z moich operacji całkowicie usuwa 6 flag, pisząc ich pożądane efekty w postaci około 6 liczb (bez flag).

Aby zachować wszystko w czarnej skrzynce, chcę, aby algorytm zamawiania wykonał wszystkie operacje, które piszę, nakazał im mieć największy wpływ i poinformował mnie, jak skutecznie udało mi się uprościć dane, które ostatecznie dotrą do systemu przetwarzania (s). Naturalnie, kieruję najbardziej złożone elementy w pośredniej reprezentacji i upraszczam je do podstawowej arytmetyki wskaźników, jeśli to możliwe, co jest najłatwiejsze do obsługi w asemblerze. :)

Po tym wszystkim dodam kolejną notatkę. Efekty operacji są opisane jako „efekty atrybutów” na liście instrukcji. Zasadniczo operacje zachowują się dobrze, ale niektóre z nich usuwają tylko liczby, które spadają po innych liczbach (np. Usuwają wszystkie 6, które nie następują po 16). Inni usuwają wszystkie wystąpienia określonego numeru zawierającego pewne flagi. Będę się nimi zajmował później - PO ustaleniu podstawowego problemu gwarantowanego dodawania / usuwania / zapobiegania wymienionych powyżej.

Dodano 8/23: Na tym obrazie, możesz zobaczyćcall instrukcja (szara), która miałaInstructionSemantics.NullCheck został przetworzony przezRemoveNullReferenceChecks przekształcić, aby usunąć flagę semantyki w zamian za dodanie innego wywołania (bez dołączonej semantyki do dodanego wywołania). Teraz asembler nie musi rozumieć / obsługiwaćInstructionSemantics.NullCheck, ponieważ nigdy ich nie zobaczy. Bez krytykowania kodu ARM -to na razie symbol zastępczy.