c# - lista - ¿Hay una clase SortedList<T> en.NET?

queue c#

Question

Necesito ordenar algunos objetos de acuerdo con su contenido (de hecho, de acuerdo con una de sus propiedades, que NO es la clave y puede ser duplicada entre diferentes objetos).

.NET proporciona dos clases ( SortedDictionary y SortedList ), y ambas se implementan usando un árbol binario. Las únicas diferencias entre ellos son

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

Podría lograr lo que quiero usando una lista, y luego usar su método Sort () con una implementación personalizada de IComparer , pero no sería eficiente con el tiempo ya que ordenaría toda la lista cada vez que quisiera insertar un nuevo objeto. mientras que una buena SortedList simplemente insertaría el artículo en la posición correcta.

Lo que necesito es una clase SortedList con un RefreshPosition (índice int) para mover solo el objeto modificado (o insertado) en lugar de recurrir a la lista completa cada vez que cambia un objeto.

¿Me estoy perdiendo algo obvio?

Answer 1

Lo que necesito es una clase SortedList con un RefreshPosition (índice int) para mover solo el objeto modificado (o insertado) en lugar de recurrir a la lista completa cada vez que cambia un objeto.

¿Por qué actualizarías usando un índice cuando tales actualizaciones invalidaran el índice? Realmente, creo que actualizar por referencia de objeto sería más conveniente. Puede hacer esto con SortedList: solo recuerde que su tipo de Key es el mismo que el tipo de devolución de la función que extrae los datos comparables del objeto.

class UpdateableSortedList<K,V> {
    private SortedList<K,V> list = new SortedList<K,V>();
    public delegate K ExtractKeyFunc(V v);
    private ExtractKeyFunc func;

    public UpdateableSortedList(ExtractKeyFunc f) { func = f; }

    public void Add(V v) {
        list[func(v)] = v;
    }
    public void Update(V v) {
        int i = list.IndexOfValue(v);
        if (i >= 0) {
            list.RemoveAt(i);
        }
        list[func(v)] = v;
    }
    public IEnumerable<T> Values { get { return list.Values; } }
}

Algo así, supongo.

Answer 2

Finalmente decidí escribirlo:

class RealSortedList<T> : List<T>
    {
        public IComparer<T> comparer;

        public int SortItem(int index)
        {
            T item = this[index];
            this.RemoveAt(index);
            int goodposition=FindLocation(this[index], 0, this.Count);
            this.Insert(goodposition, item);
            return goodposition;
        }

        public int FindLocation(T item, int begin, int end)
        {
            if (begin==end)
                return begin;
            int middle = begin + end / 2;
            int comparisonvalue = comparer.Compare(item, this[middle]);
            if (comparisonvalue < 0)
                return FindLocation(item,begin, middle);
            else if (comparisonvalue > 0)
                return FindLocation(item,middle, end);
            else
                return middle;
        }
    }

Answer 3

He resuelto este problema en el pasado al escribir un método de extensión que realiza una búsqueda binaria en un IList y otro que hace una inserción. Puede buscar la implementación correcta en la fuente CLR porque hay una versión incorporada que funciona solo en matrices, y luego simplemente modifíquela para que sea una extensión en IList.

Una de esas cosas "debería estar en el BCL ya".

Answer 4

No olvide que insertar un elemento en una lista respaldada por una matriz puede ser una operación costosa: insertando un grupo de elementos y luego la clasificación puede ser más rápida a menos que realmente necesite clasificar después de cada operación.

Alternativamente, siempre puede envolver una lista y hacer que su operación de agregar encuentre el lugar correcto e insertarla allí.

Answer 5

Tal vez soy lento, pero ¿no es esta la implementación más fácil?

class SortedList<T> : List<T>
{
    public new void Add(T item)
    {
        Insert(~BinarySearch(item), item);
    }
}

http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

Desafortunadamente, Add no fue anulable, así que tuve que List<T> list = new SortedList<T>; lo que no es tan agradable cuando tienes List<T> list = new SortedList<T>; que realmente necesitaba hacer ... así que seguí adelante y reconstruí todo ...

class SortedList<T> : IList<T>
{
    private List<T> list = new List<T>();

    public int IndexOf(T item)
    {
        var index = list.BinarySearch(item);
        return index < 0 ? -1 : index;
    }

    public void Insert(int index, T item)
    {
        throw new NotImplementedException("Cannot insert at index; must preserve order.");
    }

    public void RemoveAt(int index)
    {
        list.RemoveAt(index);
    }

    public T this[int index]
    {
        get
        {
            return list[index];
        }
        set
        {
            list.RemoveAt(index);
            this.Add(value);
        }
    }

    public void Add(T item)
    {
        list.Insert(~list.BinarySearch(item), item);
    }

    public void Clear()
    {
        list.Clear();
    }

    public bool Contains(T item)
    {
        return list.BinarySearch(item) >= 0;
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        list.CopyTo(array, arrayIndex);
    }

    public int Count
    {
        get { return list.Count; }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

    public bool Remove(T item)
    {
        var index = list.BinarySearch(item);
        if (index < 0) return false;
        list.RemoveAt(index);
        return true;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return list.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return list.GetEnumerator();
    }
}

O tal vez algo como esto es una función de Remove más apropiada ...

    public bool Remove(T item)
    {
        var index = list.BinarySearch(item);
        if (index < 0) return false;
        while (((IComparable)item).CompareTo((IComparable)list[index]) == 0)
        {
            if (item == list[index])
            {
                list.RemoveAt(index);
                return true;
            }
            index++;
        }
        return false;
    }

Asumiendo que los elementos se pueden comparar iguales pero no ser iguales ...

Answer 6

Hice una pregunta similar hace un tiempo, y hay algunas buenas respuestas allí . Hay una buena colección de colecciones aquí .