¿Qué tipo de clasificación es esta?

Question

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 funcionamiento:

• Elimina ciertos números (conocido) de la lista
• yAñade ciertos otros números (conocidos) a la lista
• y es incapaz de manejar la lista si contiene ciertos números (conocidos) al comienzo de la operación - llamar a estos Prevenir

Editar: Puede haber cero o más números en cada uno de Añade , Elimina y Evite 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 y Elimina son disjuntos, Prevenir y Elimina son disjuntos, pero Añade y Prevenir se pueden solapar.

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

• Si la operación tiene Prevenir artículos, que se coloca después de una operación que Elimina esos números. Si no inmediatamente después, no puede haber una operación Agrega que agrega esos números entre los últimos Elimina y Previene.
• Si la operación Elimina elementos, todas las operaciones que Agregue cualquiera de esos elementos se coloca delante de ella.

En el caso de una dependencia circular, la cadena de operaciones deberían eliminar tantos números como sea posible y informarme que no podía eliminar todos los números.

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

Agregado 8/23: La recompensa es para cubrir los requisitos de clasificación teniendo en cuenta tanto los opcodes (juego de estructuras) y InstructionSemantics (conjunto de indicadores de bits de una enumeración).

añadió más tarde 8/23: hice un 89: mejora del rendimiento 1 por heurísticamente preclasificación 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..."); 
     } 
    } 
} 

---

Editar: Por debajo de esta línea es información básica sobre lo que estoy haciendo en realidad, en caso de que la gente se pregunta por qué estoy pidiendo esto. No cambia el problema, solo muestra el alcance.

Tengo un sistema que lee en 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 aproximadamente 17 modificadores disponibles (enumeración de banderas). La complejidad del sistema de procesamiento (ensamblador de código de máquina) es proporcional a la cantidad de entradas únicas posibles (número + indicadores), donde tengo que codificar manualmente cada manejador 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 asegurarme de que ciertos elementos nunca aparecen para el procesamiento; esto lo hago expresando los números y/o indicadores 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 sencillas 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 el recuadro negro, quiero que un algoritmo de ordenamiento tome todas las operaciones que escribo, ordene que tengan el mayor impacto y me informen sobre el éxito que tuve en simplificar los datos que eventualmente llegar al (los) sistema (s) de procesamiento. Naturalmente, me estoy dirigiendo a los elementos más complejos en la representación intermedia y simplificándolos a la aritmética de puntero básico donde sea posible, que es el más fácil de manejar en los ensambladores. :)

Con todo lo dicho, agregaré otra nota. Los efectos de operación se describen como "efectos de atributo" sobre la lista de instrucciones. En general, las operaciones se comportan bien, pero algunas de ellas solo eliminan los números que caen después de otros números (como eliminar los 6 que no siguen un 16). Otros eliminan todas las instancias de un número particular que contiene ciertos indicadores. Los manejaré más tarde, DESPUÉS de resolver el problema básico de la garantía de agregar/quitar/prevenir enumerado anteriormente.

Agregado 8/23:In this image, se puede ver una instrucción call (gris) que tenían InstructionSemantics.NullCheck fue procesado por el RemoveNullReferenceChecks transformar a quitar la bandera semántica a cambio de añadir otra llamada (sin semántica asociada al agregado llama tampoco). Ahora el ensamblador no necesita comprender/manejar InstructionSemantics.NullCheck, porque nunca los verá. Sin criticar el código ARM - it's a placeholder for now.

Answer 1

Esto funciona por ahora. Si y solo si existe un pedido para cumplir con las condiciones, lo encontrará. No he intentado optimizarlo todavía. Funciona a la inversa al realizar un seguimiento de los elementos que la operación anterior no permite agregar.

Editar: no puedo marcar esto como una respuesta porque ya estoy teniendo un enorme impacto en el rendimiento de la misma y sólo tengo 17 operaciones (ITransform s). Se necesitan 15s para ordenar en este momento lol/fail.

Agregado 8/23: Consulte la siguiente sección de códigos para ver cómo mejoré la clasificación a algo que en realidad funciona de nuevo.

Editar 8/25: Las cosas se pusieron feas de nuevo cuando crucé 25 artículos, pero resultó que tenía un pequeño problema en la preordenación que está arreglado ahora.

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; 
    } 

En un esfuerzo por reclamar mi recompensa, que han reducido el tiempo de clase 15380s a 173ms por preacondicionamiento heurísticamente la matriz, seguido inmediatamente por el tipo de enrutamiento anterior.

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 2

Creo que aquí está hablando de un algoritmo de ordenamiento en lugar de un algoritmo de clasificación. Es que desea encontrar un pedido que tenga las propiedades enumeradas.

Me sorprendería si ya existiera un algoritmo de pedido específico que satisfaga estas propiedades.

Tenga en cuenta que es posible que no pueda encontrar un pedido para un conjunto determinado de operaciones. De hecho, es posible que ni siquiera haya un orden/celosía parcial.Un ejemplo trivial es:

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

Answer 3

Suena como topological sort, pensar en cada operación como un nodo en un gráfico dirigido con los bordes siendo las limitaciones que usted ha mencionado.

---

Editar:@280Z28 comentado esta respuesta:

estoy usando una ordenación topológica en este momento, pero es técnicamente demasiado fuerte. Necesito alguna manera de tener grupos "débiles" de los bordes (uno o más bordes del grupo tiene en el ordenamiento final)

No estoy seguro de entender lo que usted con respecto a los hombres débiles grupos de bordes, si esto se refiere a ciclos de interrupción, entonces el tipo topológico puede hacer esto, la forma en que lo hice fue mantener un en el recuento que mostró cuántos nodos no visitados apuntan a este nodo. Luego, para cada iteración, trabaja en (uno de) los nodos con el mínimo en el recuento, si el en el recuento no es cero, lo que significa que hay un ciclo y arbitrariamente interrumpe el ciclo para completar la ordenación.

Answer 4

Ya que si el elemento X puede aparecer a continuación en la lista depende no solo del último elemento de la lista sino también de los elementos anteriores, tiene razón al decir que la clasificación topológica es demasiado fuerte. Este es un problema de búsqueda más general, así que probaría una solución más general: ya sea la búsqueda de retroceso o la programación dinámica. Lo primero siempre se puede hacer, pero a veces es increíblemente lento; lo último conducirá a una solución mucho más rápida (pero más intensiva en memoria), pero requiere que pueda encontrar un D.P. formulación del problema, que no siempre es posible.