C# más rápido de clasificación de SortedList <>

Question

tenemos una

SortedList<Resource, Resource> resources = 
    new SortedList<Resource, Resource>(new ResourceIdle()); 

que utilizamos en nuestra simulación. Esta lista de recursos se inicializa de esta forma porque queremos pasar diferentes comparadores en cualquier momento. El primer problema que tenemos es que el SortedList<> requiere una comparación adicional dentro del comparador para que podamos agregar diferentes instancias de Resource con las mismas propiedades. Por ejemplo, si el comparador parece:

public int Compare(Resource x, Resource y) 
{ 
    int priority1 = x.Priority;  
    int priority2 = y.Priority;  

    if (priority1 > priority2) { 
     return -1; 
    } else if (priority1 < priority2) { 
     return 1; 
    } else { 
     return (x.Id.CompareTo(y.Id)); 
    } 
} 

entonces tenemos que hacer la comparación adicional cuando las prioridades son los mismos de otro modo volvamos una excepción para una entrada con la misma clave. Entonces mi pregunta es, ¿hay otra forma de lograr esto? Y como una pregunta secundaria ¿hay algo más rápido que el SortedList<> para pedir una gran cantidad de objetos?

Answer 1

Bueno, SortedDictionary<,> tiene diferentes características de rendimiento - depende de lo que esté haciendo con él. MSDN tiene un buen montón de detalles comparar los dos:

La clase genérica SortedDictionary<TKey, TValue> es un árbol binario de búsqueda con O (log n) de recuperación, donde n es el número de elementos en el diccionario. A este respecto, es similar a la clase genérica SortedList<TKey, TValue>. Las dos clases tienen modelos de objetos similares, y ambos tienen recuperación O (log n). Cuando las dos clases difieren es en el uso de memoria y la velocidad de inserción y extracción:

• SortedList<TKey, TValue> utiliza menos memoria que SortedDictionary<TKey, TValue>.
• SortedDictionary<TKey, TValue> tiene operaciones más rápidas de inserción y eliminación de datos sin clasificar: O (log n) en oposición a O (n) para SortedList<TKey, TValue>.
• Si la lista se rellena todos a la vez a partir de datos ordenados, SortedList<TKey, TValue> es más rápido que SortedDictionary<TKey, TValue>.

Answer 2

¿Es un requisito que la lista siempre esté ordenada en cualquier momento? de lo contrario, definitivamente sería más rápido ordenar solo a pedido. otra idea es que la clasificación se hace por un "OrderPriority", que es una combinación de los campos de prioridad y de identificación, por lo tanto, necesita ser hecha sólo una comparación:

int OrderPriority { get { return Priority * MAX_ID + ID; } } 

esto supone que los identificadores no demasiado gran ...

Answer 3

Es posible reducir el comparar un poco:

public int Compare(Resource x, Resource y) 
{ 
    int priority1 = x.Priority;  
    int priority2 = y.Priority;  

    if (priority1 != priority2) 
     return priority2 - priority1; 

    return (x.Id.CompareTo(y.Id)); 
} 

Answer 4

Si no se preocupan por distinguir entre los objetos con la misma prioridad, por qué no utilizar un SortedList de cubos (implementado como una cola quizás), con todos los elementos de igual prioridad en el mismo dólar et?

Answer 5

Cuando crea un SortedList de un diccionario, copiará las claves y valores en matrices, y luego usará el método Array.Sort para ordenarlas, por lo que es casi tan rápido como usted obtiene, a menos que tenga algún conocimiento especial sobre la colección que podría ayudarlo a elegir un algoritmo diferente que sea más adecuado para ese caso especial.

Sin embargo, parece que está creando un diccionario con la misma clave y valor solo para poder usar el SortedList. Si ese es el caso, debería colocar los elementos en una matriz o una lista y ordenarlos. Los métodos Array.Sort y List<T>.Sort también pueden usar un comparador personalizado.

Usted comparador con una comparación secundaria puede simplificarse como:

public int Compare(Resource x, Resource y) { 
    int result = x.Priority.CompareTo(y.Priority); 
    if (result == 0) { 
    result = x.Id.CompareTo(y.Id); 
    } 
    return result; 
}