Raccolta con iterazione molto veloce e buona aggiunta e rimozione delle velocità

Question

Sono in cerca di una raccolta che posso scorrere molto velocemente. Aggiungerò anche articoli e rimuoverò articoli (specifici) abbastanza regolarmente e quindi idealmente vorrei che anche quelle operazioni fossero veloci.

Sto sviluppando su xbox e quindi sono limitato al framework compatto (più o meno). È molto importante mantenere le assegnazioni dei rifiuti e degli oggetti al minimo, quindi qualsiasi cosa in cui posso pre-allocare lo spazio per i miei oggetti sarebbe ottima.

Conserverò uint s (ma può essere int s se necessario) nella raccolta. Una soluzione generica sarebbe comunque buona, poiché sono sicuro che ne avrò bisogno in futuro.

Una raccolta .net sarebbe l'ideale, in mancanza di qualcosa di leggero e open source sarebbe grandioso.

Esiste una classe di raccolta adatta alle mie esigenze? Se no, come potrei fare per crearne uno?

---

Per elaborare un bit, sono ID oggetto che una classe deve elaborare ogni frame. Verranno generalmente aggiunti in ordine crescente, con spazi vuoti. Non c'è limite massimo. Tuttavia, chiunque potrebbe essere rimosso, il che lascerebbe lacune.
L'ordine di iterazione non è completamente importante, ma sarebbe molto utile (in particolare per il debug) se fosse in un ordine coerente.

Answer 1

ho due suggerimenti da provare:

In primo luogo, ciò che sull'utilizzo riflettore o ILSpy di guardare dentro generico List<T>? Suppongo che l'implementazione non sia nella CF o potresti usarla. Il numero di serie List<T> è supportato da array e utilizza un algoritmo di raddoppiamento a partire dall'array di lunghezza 4, ogni chiamata a .Add sulla Capacità ne provoca il raddoppio ed esegue un Array.Copy nel nuovo array. Non viene ridimensionato a meno che non si imposti esplicitamente la capacità su zero, quindi attenzione da un punto di vista della memoria. Le aggiunte sono una cosa, ma ciascuna Rimuovi farà sì che l'array venga copiato e spostato a sinistra dopo l'indice che è stato rimosso.

Il secondo suggerimento è questo - che dire sulla creazione di una classe personalizzata che avvolge una matrice integer per gestire tale che utilizza un simile doppio algoritmo (o quadruplicare) per Generic List<T> (per gestire il ridimensionamento), ma dalle ore dire dimensione 256. Potresti aggiungere l'ID di un intero oggetto a questo fuori ordine a tuo piacimento e non raddoppierà troppo spesso. È anche possibile simulare una rimozione designando (int) -1 o uint.MaxValue come "indice nullo", ovvero senza Array.Copy alla rimozione. Quindi, applica una sorta di ordinamento veloce per fotogramma per ordinare l'array di indice dell'oggetto prima del disegno. Se ordinate in modo ascendente, tutti i -1 appariranno all'inizio (o uint.MaxValues ​​alla fine) e possono essere ignorati. Puoi periodicamente "raccogliere" l'array di indici ridimensionando e rimuovendo il precedente -1 su un thread separato (attenzione - usa il blocco;)

Cosa ne pensi? Basta pensare si compensare alcuni calcoli, una volta per frame per un veloce l'ordinamento (non costoso su xbox vs. allocazione di memoria/raccolta su ogni Rimuovere e alcuni Aggiunge (costoso)

UPDATE -. BlockArray - Lista < T [] > dove T è array di dimensioni fisse

Un ulteriore commento a questo proposito: recentemente stavo sperimentando la struttura dati più efficiente per elenchi di dimensioni dinamiche e ho scoperto sperimentando che i blocchi di array - una classe supportata da un elenco di T [ ], dove ogni T [] era un array di blocchi a dimensione fissa, ad esempio 512, 4096, 8192 come diversi vantaggi rispetto a un elenco semplice <T>.

ho scoperto che l'implementazione di Add() (dove la dimensione è sconosciuta) in un elenco < T [] > notevolmente sovraperformato Aggiungi() per Lista <T>, soprattutto quando la dimensione totale è diventato più grande. Ciò è dovuto all'algoritmo di duplicazione T > di T > che richiede un nuovo array 2x alla dimensione del vecchio e memcpy è il vecchio array ogni volta che viene superata la dimensione.

La velocità di iterazione è simile. La pre-allocazione (capacità predefinita) era molto più lenta di Lista <T> per blocchi di piccole dimensioni (512), ma solo leggermente più lento per blocchi di grandi dimensioni (8192). Rimuove sono problematici, poiché richiedono la copia/spostamento a sinistra di molti blocchi.

Ciò che è interessante è in un elenco < T [] > (elenco di blocchi), è possibile memorizzare nella cache/pool i blocchi. Se abbastanza piccoli, i blocchi di T [] si adattano all'heap di piccoli oggetti (favorendo la compattazione, un'allocazione più rapida), possono essere inseriti nella cache L2 e un numero di blocchi potrebbe essere pre-allocato e raggruppato

Answer 2

Informazioni sull'utilizzo di Mono HashSet<T>?

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

E 'sotto licenza MIT X11, che è una licenza permissiva.

---

Iterazione fine potrebbe essere un problema a seconda di come T implementa GetHashCode, ma che non dovrebbe essere un problema quando si utilizza uint. L'implementazione predefinita di GetHashCode restituisce invece valori diversi su istanze diverse, che potrebbero portare a un diverso ordine di iterazione.

L'ordine di iterazione può dipendere anche dall'ordine in cui vengono aggiunti gli articoli. vale a dire due raccolte contenenti gli stessi articoli potrebbero scorrere in un ordine diverso se gli articoli sono stati aggiunti in un ordine diverso.

C'è anche una collezione SortedSet<T>, ma non so quali caratteristiche di prestazione ha.

Answer 3

Come su una classe personalizzata , SparseList <T>:

• un elenco che permette di rimuovere gli elementi da impostazione valori mancanti su null (o per SparseValueList, un valore speciale come -1 (come la soluzione del Dott ABT), 0 (di default (T)), o int.MinValue o uint.MaxValue,) e
• quindi mantenendo un elenco di indici cancellati (una pila <int>). Quindi, quando è necessario aggiungere all'elenco, apre un indice eliminato dallo stack e aggiunge il valore lì. (Per il multithreading, forse ConcurrentQueue <int> sarebbe un'altra idea.)
• l'enumeratore può saltare gli elementi eliminati (per sostenere foreach)
• oggetti possono essere rimossi dalla raccolta durante l'enumerazione! (Devo farlo molto, quindi questo è bello.)
• indicizzatore fornisce un accesso raw alla lista che contiene valori nulli. Quindi, se usi un ciclo for (;;), preparati a filtrare i valori nulli.
• chiamata Compact() se/quando si desidera rimuovere tutte le null
• Se uno non chiama mai compatto durante una partita, io sono preoccupato per l'iterazione attraverso un gran numero di valori nulli. Quindi, per un'alternativa sperimentale alla compatta, vedi SparseListCleaningEnumerator: riduci automaticamente l'elenco ogni volta che viene enumerato, almeno per le situazioni a thread singolo: quando MoveNext si allontana da un elemento, fa capolino lo stack per vedere se l'indice è più basso e in tal caso assegna l'elemento all'indice inferiore, rimuovendolo dalla posizione corrente, che ridurrà l'elenco. Il bilanciamento potrebbe richiedere molte iterazioni e coinvolgere più mosse prima dell'ottimizzazione, a meno che lo stack non venga sostituito da una lista ordinata o lo stack sia ordinato occasionalmente. Se l'ultimo valore è nullo, questo non funzionerà, perché l'indice sarà sepolto nello stack dell'indice libero (sostituendo lo stack con qualcosa ordinato eviterebbe questo).

Ho implementato questo (non ancora testato) ma sto memorizzando riferimenti effettivi alle mie entità di gioco invece di ID, quindi sarà necessario adattarlo per int o Nullable in qualche modo. (Ok per essere sicuro di rispondere al requisito int/uint della tua domanda Ho aggiunto anche una SparseValueList <T> che è leggermente differente, usando il valore predefinito (T) invece di null. Ciò significa che non puoi usare 0 nell'elenco.) Potresti forse estrai la versione se non pensi di averne bisogno - la maggior parte dei giochi potrebbe non esserlo.

/// <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(); 
    } 
}