Digamos que tengo una lista de enteros, donde cada elemento es un número del 1 al 20. (Eso no es lo que estoy tratando de ordenar).

Ahora, tengo una serie de "operaciones", donde cada operación:

Elimina Ciertos números (conocidos) de la listay Añade Ciertos otros números (conocidos) a la lista.y No puede manejar la lista si contiene ciertos números (conocidos) al comienzo de la operación; llámelosEvitar

Editar: Puede haber cero o más números en cada uno deAñade, EliminayEvitar para cada operación, y cada número puede aparecer cero o más veces en cada grupo para alguna operación. Para cualquier operación dada,Añade yElimina son desunidos,Evitar yElimina son desunidos, peroAñade yEvitar puede superponerse.

Quiero ordenar la matriz de operaciones para que para cada operación:

Si la operación tieneEvitar artículos, se coloca después de una operación queElimina esos números Si no es inmediatamente después, no puede haber unAñade Operación que suma esos números de vuelta entre los últimos.Elimina y elEvitar.Si la operacionElimina artículos, todas las operaciones queAñade cualquiera de esos artículos se coloca delante de él.

En el caso de una dependencia circular, la cadena de operaciones debe eliminar tantos números como sea posibley Avísame que no se pudieron quitar todos los números.

¿Hay un nombre / implementación para este tipo de algoritmo que supere al que tengo a continuación?

23/08 agregado: la recompensa es por cubrir los requisitos de clasificación considerando tanto los OpCodes (conjunto de estructuras) comoInstructionSemantics (conjunto de indicadores de bit de una enumeración).

Agregado mas tarde 23/23: Realicé una mejora de rendimiento de 89: 1 al ordenar heurísticamente la matriz de origen. Ver mi respuesta actual para más detalles.

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

Edición: debajo de esta línea hay información de antecedentes sobre lo que realmente estoy haciendo, en caso de que la gente se pregunte por qué lo pregunto. No cambia el problema, solo muestra el alcance.

Tengo un sistema que lee una lista de elementos y lo envía a otro "módulo" para su procesamiento. Cada elemento es una instrucción en mi representación intermedia en un compilador, básicamente un número de 1 a ~ 300 más una combinación de unos 17 modificadores disponibles (enumeración de marcas). La complejidad del sistema de procesamiento (ensamblador de código de máquina) es proporcional al número de posibles entradas únicas (número + indicadores), donde tengo que codificar manualmente cada controlador individual. Además de eso, tengo que escribir al menos 3 sistemas de procesamiento independientes (X86, X64, ARM): la cantidad de código de procesamiento real que puedo usar para múltiples sistemas de procesamiento es mínima.

Al insertar "operaciones" entre la lectura y el procesamiento, puedo asegurar que ciertos elementos nunca aparezcan para el procesamiento; lo hago expresando los números y / o las marcas en términos de otros números. Puedo codificar cada "operación de transformación" en una caja negra describiendo sus efectos, lo que me ahorra una tonelada de complejidad por operación. Las operaciones son complejas y únicas para cada transformación, pero mucho más fáciles que el sistema de procesamiento. Para mostrar cuánto tiempo ahorra, una de mis operaciones elimina por completo 6 de las banderas al escribir sus efectos deseados en términos de aproximadamente 6 números (sin banderas).

Para mantener las cosas en la caja negra, quiero que un algoritmo de ordenación tome todas las operaciones que escribo, les pida que tengan el mayor impacto y que me informe sobre el éxito que tuve en la simplificación de los datos que finalmente llegarán al sistema de procesamiento. (s). Naturalmente, estoy apuntando a los elementos más complejos en la representación intermedia y simplificándolos a la aritmética de punteros básica cuando sea posible, que es el más fácil de manejar en los ensambladores. :)

Con todo lo dicho, añadiré otra nota. Los efectos de operación se describen como "efectos de atributo" en la lista de instrucciones. En general, las operaciones se comportan bien, pero algunas de ellas solo eliminan números que caen después de otras (como eliminar todas las 6 que no siguen a 16). Otros eliminan todas las instancias de un número particular que contiene ciertas banderas. Manejaré esto más tarde. DESPUÉS de que resuelva el problema básico de las opciones de agregar / eliminar / prevenir que se mencionaron anteriormente.

Añadido el 23/23: En esta imagen, puedes ver uncall instrucción (gris) que teníaInstructionSemantics.NullCheck fue procesado por elRemoveNullReferenceChecks transformar para eliminar el indicador semántico a cambio de agregar otra llamada (sin semántica adjunta a la llamada agregada tampoco). Ahora el ensamblador no necesita entender / manejarInstructionSemantics.NullCheck, porque nunca los verá. No criticar el código ARM -es un marcador de posición por ahora.