Colección con iteración muy rápida y buenas velocidades de adición y eliminación

Question

Estoy buscando una colección que pueda iterar muy rápido. También agregaré elementos y eliminaré elementos (específicos) con bastante regularidad, por lo que me gustaría que esas operaciones también fueran rápidas.

Estoy desarrollando en la xbox y estoy restringido al marco compacto (más o menos). Es muy importante que mantenga las asignaciones de basura y objetos al mínimo, por lo que cualquier cosa en la que pueda preasignar el espacio para mis objetos sería genial.

Voy a almacenar uint s (pero puede ser int s si es necesario) en la colección. Sin embargo, una solución genérica sería buena, ya que estoy seguro de que tendré una necesidad en el futuro.

Una colección .net sería ideal, en su defecto, algo ligero y de código abierto sería genial.

¿Hay alguna clase de colección que se ajuste a mis necesidades? Si no, ¿cómo podría crear una?

---

Para elaborar un poco, son id de objeto que una clase debe procesar cada fotograma. Por lo general, se agregarán en orden ascendente, con espacios. No hay límite superior. Cualquiera podría ser eliminado, lo que dejaría huecos.
El orden de iteración no es completamente importante, pero sería muy útil (especialmente para la depuración) si estuviera en un orden constante.

Answer 1

Tengo dos sugerencias para tratar:

En primer lugar, ¿qué pasa con el uso del reflector o ILSpy para mirar dentro Genérico List<T>? Supongo que la implementación no está en el CF o podría usarlo. Genérico List<T> está respaldado por una matriz y utiliza un algoritmo de duplicación que comienza en una matriz de longitud 4, cada llamada a .Agregar sobre la Capacidad hace que se duplique y realice una Array.Copy en la nueva matriz. No cambia de tamaño a menos que establezca explícitamente Capacidad en cero, así que tenga cuidado desde el punto de vista de la memoria. Las adiciones son una cosa, pero cada Eliminar hará que la matriz se copie y se mueva hacia la izquierda después del índice que se eliminó.

La segunda sugerencia es esta: ¿qué tal crear una clase personalizada que envuelve una matriz entera para manejar esto que usa un algoritmo doble similar (o cuadruplicado) a List<T> genérico (para manejar el cambio de tamaño) pero comienza en dicho tamaño 256. Puede agregar ID de objeto entero a este fuera de orden tan rápido como quiera y no se duplicará con demasiada frecuencia. También puede simular una eliminación al designar (int) -1 o uint.MaxValue como un "índice nulo", lo que significa que no hay Array.Copy on remove. Luego, aplique algún tipo de clasificación rápida por cuadro para ordenar el conjunto de índices de objetos antes de dibujar. Si ordena de forma ascendente todos sus -1s aparecerán al inicio (o uint.MaxValues ​​al final) y pueden ser ignorados. Puede "recopilar" periódicamente el conjunto de índices cambiando el tamaño y eliminando el anterior -1 en un hilo separado (cuidado - use el bloqueo;)

¿Qué opina? Sólo de pensar que va a compensar algunos de computación una vez por cuadro para la clasificación rápida (no es caro en Xbox vs asignación de memoria/recogida en cada Retire y algunos agrega (caro)

ACTUALIZACIÓN -. BlockArray - Lista < T [] donde > T es una matriz de tamaño fijo

He estado experimentando recientemente con la estructura de datos más eficiente para listas de tamaño dinámico y descubrí por experimentación que los bloques de matriz - una clase que está respaldada por una Lista de T [ ], donde cada T [] era una matriz de bloque de tamaño fijo, por ejemplo 512, 4096, 8192 como varias ventajas sobre una lista simple <T>.

he encontrado que una implementación de add() (donde el tamaño es desconocido) en una lista < T [] > enormemente superó Añadir() para la Lista <T>, especialmente cuando el tamaño total se hizo más grande. Esto se debe al < de la lista > del algoritmo de duplicación que solicita una nueva matriz 2x del tamaño de la antigua, y la matriz anterior de memcpy siempre que se excede el tamaño.

La velocidad de iteración es similar. La preasignación (capacidad predefinida) fue mucho más lenta que la Lista <T> para tamaños de bloques pequeños (512), pero solo un poco más lenta para tamaños de bloques grandes (8192). Las eliminaciones son problemáticas, ya que requieren copiar/dejar desplazando muchos bloques.

Lo interesante es en una lista < T [] > (lista de bloqueos), puede almacenar en caché o agrupar los bloques. Si es lo suficientemente pequeño, los bloques de T [] caben en el pequeño montón de objetos (favoreciendo la compactación, una asignación más rápida), pueden caber en la memoria caché L2 y se pueden preasignar y agrupar varios bloques

Answer 2

¿Qué le parece usar el HashSet<T> de Mono?

https://github.com/mono/mono/blob/master/mcs/class/System.Core/System.Collections.Generic/HashSet.cs

Está autorizado bajo el MIT X11, que es una licencia permisiva.

---

iteración fin puede ser un problema dependiendo de cómo T implementa GetHashCode, pero eso no debería ser un problema cuando se utiliza uint. La implementación predeterminada de GetHashCode, por otro lado, devuelve valores diferentes en instancias diferentes, lo que puede conducir a un orden de iteración diferente.

El orden de iteración también puede depender del orden en que se agregan los elementos. es decir, dos colecciones que contienen los mismos elementos pueden iterar en un orden diferente si los elementos se agregaron en un orden diferente. También hay una colección de SortedSet<T>, pero no sé qué características de rendimiento tiene.

Answer 3

¿Qué tal una clase personalizada? , SparseList <T>:

• una lista que le permite eliminar elementos por ajuste de los valores que faltan en nulo (o para SparseValueList, un valor especial como -1 (como solución del Dr. ABT), 0 (por defecto (T)), o int.MinValue, o uint.MaxValue,) y
• manteniendo entonces una lista de índices eliminados (una pila <int>). Luego, cuando necesita agregar a la lista, aparece un índice eliminado de la pila y agrega el valor allí. (Para multihilo, tal vez ConcurrentQueue <int> sería otra idea.)
• la empadronador puede pasar por alto los elementos eliminados (para apoyar foreach)
• artículos pueden ser retirados de la colección durante la enumeración! (Tengo que hacer esto mucho, así que esto es bueno.)
• indizador proporciona acceso sin formato a la lista que contiene nulos. Entonces, si usa un ciclo for (;;), prepárese para filtrar nulos.
• llamada compacto() si/cuando se quiere eliminar todos los nulos
• Si uno nunca llama compacta durante un juego, estoy preocupado por iteración a través de un gran número de valores nulos. Por lo tanto, para una alternativa experimental a compacta, consulte SparseListCleaningEnumerator: reduzca automáticamente la lista cada vez que se enumera, al menos para situaciones de subproceso único: cuando MoveNext se aleja de un elemento, busca en la pila para ver si el índice es más bajo y si es así, asigna el ítem al índice más bajo, quitándolo de la posición actual, lo que reducirá la lista. El equilibrio puede tomar muchas iteraciones e involucrar movimientos múltiples antes de la optimización, a menos que la pila se remplace con una lista ordenada, o la pila se clasifique ocasionalmente. Si el último valor es nulo, esto no funcionará, porque el índice quedará oculto en la pila de índices libres (si se reemplaza la pila con algo ordenado se evitaría esto).

He implementado esto (aún no probado) pero yo estoy almacenando referencias reales a mis entidades juego en lugar de identificadores, por lo que tendrá que adaptarse para este INT o de alguna manera anulable. (Ok, para asegurarme de que respondo el requisito de int/uint de tu pregunta, también agregué una lista SparseValueList <T> que es ligeramente diferente, usando el valor predeterminado (T) en lugar de nulo. Esto significa que no puedes usar 0 en la lista). elimina el control de versiones si no crees que lo necesites, la mayoría de los juegos no.

/// <summary> 
/// Specifying null as value has unspecified results. 
/// CopyTo may contain nulls. 
/// </summary> 
/// <typeparam name="T"></typeparam> 
public class SparseList<T> : IList<T> 
    where T : class 
{ 
    int version = 0; 
    List<T> list = new List<T>(); 
    Stack<int> freeIndices = new Stack<int>(); 

    public int Capacity { get { return list.Capacity; } set { list.Capacity = value; } } 

    public void Compact() 
    { 
     var sortedIndices = freeIndices.ToList(); 

     foreach (var i in sortedIndices.OrderBy(x => x).Reverse()) 
     { 
      list.RemoveAt(i); 
     } 
     freeIndices.Clear(); 
     list.Capacity = list.Count; 
     version++; // breaks open enumerators 
    } 

    public int IndexOf(T item) 
    { 
     return list.IndexOf(item); 
    } 

    /// <summary> 
    /// Slow (forces a compact), not recommended 
    /// </summary> 
    /// <param name="index"></param> 
    /// <param name="item"></param> 
    public void Insert(int index, T item) 
    { 
     // One idea: remove index from freeIndices if it's in there. Stack doesn't support this though. 
     Compact(); // breaks the freeIndices list, so apply it before insert 
     list.Insert(index, item); 
     version++; // breaks open enumerators 
    } 

    public void RemoveAt(int index) 
    { 
     if (index == Count - 1) { list.RemoveAt(index); } 
     else { list[index] = null; freeIndices.Push(index); } 
     //version++; // Don't increment version for removals 
    } 

    public T this[int index] 
    { 
     get 
     { 
      return list[index]; 
     } 
     set 
     { 
      if (value == null) throw new ArgumentNullException(); 
      list[index] = value; 
     } 
    } 

    public void Add(T item) 
    { 
     if (item == null) throw new ArgumentNullException(); 

     if (freeIndices.Count == 0) { list.Add(item); return; } 

     list[freeIndices.Pop()] = item; 
     //version++; // Don't increment version for additions? It could result in missing the new value, but shouldn't break open enumerators 
    } 

    public void Clear() 
    { 
     list.Clear(); 
     freeIndices.Clear(); 
     version++; 
    } 

    public bool Contains(T item) 
    { 
     if (item == null) return false; 
     return list.Contains(item); 
    } 

    /// <summary> 
    /// Result may contain nulls 
    /// </summary> 
    /// <param name="array"></param> 
    /// <param name="arrayIndex"></param> 
    public void CopyTo(T[] array, int arrayIndex) 
    { 
     list.CopyTo(array, arrayIndex); 
    } 
    //public void CopyNonNullTo(T[] array, int arrayIndex) 
    //{ 
    //} 

    /// <summary> 
    /// Use this for iterating via for loop. 
    /// </summary> 
    public int Count { get { return list.Count; } } 

    /// <summary> 
    /// Don't use this for for loops! Use Count. 
    /// </summary> 
    public int NonNullCount 
    { 
     get { return list.Count - freeIndices.Count; } 
    } 

    public bool IsReadOnly 
    { 
     get { return false; } 
    } 

    public bool Remove(T item) 
    { 
     int i = list.IndexOf(item); 
     if (i < 0) return false; 

     if (i == list.Count - 1) 
     { 
      // Could throw . Could add check in 
      list.RemoveAt(i); 
     } 
     else 
     { 
      list[i] = null; 
      freeIndices.Push(i); 
     } 
     //version++; // Don't increment version for removals 
     return true; 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     return new SparseListEnumerator(this); 
    } 

    private class SparseListEnumerator : IEnumerator<T>, IRemovingEnumerator 
    { 
     SparseList<T> list; 
     int version; 
     int index = -1; 

     public SparseListEnumerator(SparseList<T> list) 
     { 
      this.list = list; 
      this.version = list.version; 

      //while (Current == null && MoveNext()) ; 
     } 

     public T Current 
     { 
      get { 
       if (index >= list.Count) return null; // Supports removing last items of collection without throwing on Enumerator access 
       return list[index]; 
      } 
     } 

     public void Dispose() 
     { 
      list = null; 
     } 

     object IEnumerator.Current 
     { 
      get { return Current; } 
     } 

     public bool MoveNext() 
     { 
      do 
      { 
       if (version != list.version) { throw new InvalidOperationException("Collection modified"); } 
       index++; 
       return index < list.Count; 
      } while (Current == null); 
     } 

     public void Reset() 
     { 
      index = -1; 
      version = list.version; 
     } 

     /// <summary> 
     /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return null. 
     /// </summary> 
     public void RemoveCurrent() 
     { 
      list.RemoveAt(index); 
     } 
    } 

    private class SparseListCleaningEnumerator : IEnumerator<T>, IRemovingEnumerator 
    { 
     SparseList<T> list; 
     int version; 
     int index = -1; 

     public SparseListCleaningEnumerator(SparseList<T> list) 
     { 
      this.list = list; 
      this.version = list.version; 

      //while (Current == null && MoveNext()) ; 
     } 

     public T Current 
     { 
      get 
      { 
       if (index >= list.Count) return null; // Supports removing last items of collection without throwing on Enumerator access 
       return list[index]; 
      } 
     } 

     public void Dispose() 
     { 
      list = null; 
     } 

     object IEnumerator.Current 
     { 
      get { return Current; } 
     } 

     public bool MoveNext() 
     { 
      do 
      { 
       if (version != list.version) { throw new InvalidOperationException("Collection modified"); } 
       if (index > 0 
        && Current != null // only works for values that are set, otherwise the index is buried in the free index stack somewhere 
        ) 
       { 
        int freeIndex = list.freeIndices.Peek(); 
        if (freeIndex < index) 
        { 
         list.freeIndices.Pop(); 
         list[freeIndex] = list[index]; 
         list.RemoveAt(index); 
        } 
       } 
       index++; 
       return index < list.Count; 
      } while (Current == null); 
     } 

     public void Reset() 
     { 
      index = -1; 
      version = list.version; 
     } 

     /// <summary> 
     /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return null. 
     /// </summary> 
     public void RemoveCurrent() 
     { 
      list.RemoveAt(index); 
     } 
    } 

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

/// <summary> 
/// Like SparseList but Supports value types, using default(T) in place of null. 
/// This means values of default(T) are not permitted as values in the collection. 
/// CopyTo may contain default(T). 
/// TODO: Use EqualityComparer&lt;T&gt;.Default instead of default(T).Equals() 
/// </summary> 
/// <typeparam name="T"></typeparam> 
public class SparseValueList<T> : IList<T> 
{ 
    int version = 0; 
    List<T> list = new List<T>(); 
    Stack<int> freeIndices = new Stack<int>(); 

    public int Capacity { get { return list.Capacity; } set { list.Capacity = value; } } 

    public void Compact() 
    { 
     var sortedIndices = freeIndices.ToList(); 

     foreach (var i in sortedIndices.OrderBy(x => x).Reverse()) 
     { 
      list.RemoveAt(i); 
     } 
     freeIndices.Clear(); 
     list.Capacity = list.Count; 
     version++; // breaks open enumerators 
    } 

    public int IndexOf(T item) 
    { 
     return list.IndexOf(item); 
    } 

    /// <summary> 
    /// Slow (forces a compact), not recommended 
    /// </summary> 
    /// <param name="index"></param> 
    /// <param name="item"></param> 
    public void Insert(int index, T item) 
    { 
     // One idea: remove index from freeIndices if it's in there. Stack doesn't support this though. 
     Compact(); // breaks the freeIndices list, so apply it before insert 
     list.Insert(index, item); 
     version++; // breaks open enumerators 
    } 

    public void RemoveAt(int index) 
    { 
     if (index == Count - 1) { list.RemoveAt(index); } 
     else { list[index] = default(T); freeIndices.Push(index); } 
     //version++; // Don't increment version for removals 
    } 

    public T this[int index] 
    { 
     get 
     { 
      return list[index]; 
     } 
     set 
     { 
      if (default(T).Equals(value)) throw new ArgumentNullException(); 
      list[index] = value; 
     } 
    } 

    public void Add(T item) 
    { 
     if (default(T).Equals(item)) throw new ArgumentNullException(); 

     if (freeIndices.Count == 0) { list.Add(item); return; } 

     list[freeIndices.Pop()] = item; 
     //version++; // Don't increment version for additions? It could result in missing the new value, but shouldn't break open enumerators 
    } 

    public void Clear() 
    { 
     list.Clear(); 
     freeIndices.Clear(); 
     version++; 
    } 

    public bool Contains(T item) 
    { 
     if (default(T).Equals(item)) return false; 
     return list.Contains(item); 
    } 

    /// <summary> 
    /// Result may contain default(T)'s 
    /// </summary> 
    /// <param name="array"></param> 
    /// <param name="arrayIndex"></param> 
    public void CopyTo(T[] array, int arrayIndex) 
    { 
     list.CopyTo(array, arrayIndex); 
    } 
    //public void CopyNonNullTo(T[] array, int arrayIndex) 
    //{ 
    //} 

    /// <summary> 
    /// Use this for iterating via for loop. 
    /// </summary> 
    public int Count { get { return list.Count; } } 

    /// <summary> 
    /// Don't use this for for loops! Use Count. 
    /// </summary> 
    public int NonNullCount 
    { 
     get { return list.Count - freeIndices.Count; } 
    } 

    public bool IsReadOnly 
    { 
     get { return false; } 
    } 

    public bool Remove(T item) 
    { 
     int i = list.IndexOf(item); 
     if (i < 0) return false; 

     if (i == list.Count - 1) 
     { 
      // Could throw . Could add check in 
      list.RemoveAt(i); 
     } 
     else 
     { 
      list[i] = default(T); 
      freeIndices.Push(i); 
     } 
     //version++; // Don't increment version for removals 
     return true; 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     return new SparseValueListEnumerator(this); 
    } 

    private class SparseValueListEnumerator : IEnumerator<T>, IRemovingEnumerator 
    { 
     SparseValueList<T> list; 
     int version; 
     int index = -1; 

     public SparseValueListEnumerator(SparseValueList<T> list) 
     { 
      this.list = list; 
      this.version = list.version; 

      //while (Current == default(T) && MoveNext()) ; 
     } 

     public T Current 
     { 
      get 
      { 
       if (index >= list.Count) return default(T); // Supports removing last items of collection without throwing on Enumerator access 
       return list[index]; 
      } 
     } 

     public void Dispose() 
     { 
      list = null; 
     } 

     object IEnumerator.Current 
     { 
      get { return Current; } 
     } 

     public bool MoveNext() 
     { 
      do 
      { 
       if (version != list.version) { throw new InvalidOperationException("Collection modified"); } 
       index++; 
       return index < list.Count; 
      } while (default(T).Equals(Current)); 
     } 

     public void Reset() 
     { 
      index = -1; 
      version = list.version; 
     } 

     /// <summary> 
     /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return default(T). 
     /// </summary> 
     public void RemoveCurrent() 
     { 
      list.RemoveAt(index); 
     } 
    } 

    private class SparseValueListCleaningEnumerator : IEnumerator<T>, IRemovingEnumerator 
    { 
     SparseValueList<T> list; 
     int version; 
     int index = -1; 

     public SparseValueListCleaningEnumerator(SparseValueList<T> list) 
     { 
      this.list = list; 
      this.version = list.version; 

      while (default(T).Equals(Current) && MoveNext()) ; 
     } 

     public T Current 
     { 
      get 
      { 
       if (index >= list.Count) return default(T); // Supports removing last items of collection without throwing on Enumerator access 
       return list[index]; 
      } 
     } 

     public void Dispose() 
     { 
      list = null; 
     } 

     object IEnumerator.Current 
     { 
      get { return Current; } 
     } 

     public bool MoveNext() 
     { 
      do 
      { 
       if (version != list.version) { throw new InvalidOperationException("Collection modified"); } 
       if (index > 0 
        && (!default(T).Equals(Current)) // only works for values that are set, otherwise the index might be buried in the stack somewhere 
        ) 
       { 
        int freeIndex = list.freeIndices.Peek(); 
        if (freeIndex < index) 
        { 
         list.freeIndices.Pop(); 
         list[freeIndex] = list[index]; 
         list.RemoveAt(index); 
        } 
       } 
       index++; 
       return index < list.Count; 
      } while (default(T).Equals(Current)); 
     } 

     public void Reset() 
     { 
      index = -1; 
      version = list.version; 
     } 

     /// <summary> 
     /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return default(T). 
     /// </summary> 
     public void RemoveCurrent() 
     { 
      list.RemoveAt(index); 
     } 
    } 

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