Tengo una clase Foo que contiene una lista de objetos: List<Bar> . Cada Bar tiene una propiedad en la que se pueden ordenar (de tipo TimeSpan , que representa una duración), y Bar es un objeto inmutable, es decir, la duración no cambia durante la ejecución del algoritmo. Actualmente, para cada Foo también mantengo la Bar que sería la primera en la lista si se ordenara (es decir, la Bar de menor duración). Algo como esto:
public class Foo { public List<Bar> AllBars { get; set; } public Bar FirstBar { get; set; } public Foo (Bar bar) { FirstBar = bar; AllBars = new List<Bar>() { bar }; } public AddBar(Bar bar) { if(bar.Duration < FirstBar.Duration) { FirstBar = bar; } AllBars.Add(bar); } } Esta clase Foo se usa en un algoritmo donde el rendimiento de procesamiento (velocidad) es crítico. La memoria es importante pero no tanto como la velocidad. Hay una lista de n Foo s, cada uno de los cuales tiene hasta m Bar s. Esta clase me ha servido bien hasta este punto. Ahora deseo ofrecer al usuario varias opciones, lo que significa que tendré que proporcionar acceso aleatorio a las primeras Bar de la lista.
Por lo tanto, me gustaría almacenar mis Bar s en orden para poder acceder a ellos por índice en orden. En mi clase Bar , implementé IComparable para permitir que Bar s se comparara en duración, pero estoy atascado en la elección de un tipo de datos apropiado. Miré System.Collections.SortedList pero (a menos que me equivoque) parece hacer referencia a elementos por clave, ya que implementa IDictionary . ¿Qué colección podría usar que mantuviera mis objetos de manera que permanezcan ordenados y que sean transitables en orden de índice?
Prefiero usar SortedSet<T> , que es un árbol binario donde la clave y el valor son el mismo objeto. Una vez más, esto significa que agregar/eliminar/búsquedas es logarítmico - O(log n) - pero obtiene la capacidad de iterar sobre los elementos en orden. Para que esta colección sea efectiva, el tipo T debe implementar IComparable<T> o debe proporcionar un IComparer<T> externo.
(promocionado a partir de un comentario, según lo solicitado por el autor de la pregunta)
Si puede vivir con tener "valores" que no significan nada, simplemente use SortedList<Bar, object> donde no use la parte de valor.
Agregue con yourSortedList.Add(yourBar, null) en tiempo O(n) (la lista tendrá que mover "hacia arriba" todas las entradas después del punto donde insertó). Recupere la i -ésima entrada en tiempo O(1) con yourSortedList.Keys[i] .
Consulte la documentación de la propiedad SortedList<,>.Keys para obtener alguna "prueba" de que la descripción anterior es correcta. Tenga en cuenta que SortedList<,> en realidad consta de una "lista" (es decir, una matriz de longitud Capacity , sujeta a sustitución por una matriz más grande cuando sea necesario). Esto es diferente de SortedDictionary<,> que creo que es un árbol de búsqueda binaria.
Sin embargo, tenga en cuenta: no podrá tener duplicados en su SortedList<,> , por lo que dos miembros de la lista no pueden CompareTo entre sí con un valor de retorno cero.
¿Por qué no usar List.Insert ?
Insert es O(n) y le permite insertar en un índice específico.
n + n sigue siendo O(n)
public AddBar(Bar bar) { int index = 0; foreach (bar b in AllBar) { if(bar.Duration < b.Duration) break; index++; } AllBars.Insert(index, bar); } Entonces tienes ordenación e índice O(1)
A un costo de O(n) Agregar
El complemento actual también O(n)
Una lista ordenada en NlogN y luego no tiene índice ya que la clave es Duración y la clave no es única
Una inserción de SortedSet es LogN pero una ToList es O(n) por lo que todavía es O(n)
Llamar al método Sort en la lista es NlogN
Esto responde a la pregunta planteada de: ¿Qué colección podría usar que mantuviera mis objetos de manera que permanezcan ordenados y que sean transitables en orden de índice?
No creo que vayas a hacer eso con algo mejor que O(n) Add.
¿Quién le dio un voto negativo entonces cuál es una mejor solución?