¿Hay una implementación de matriz dispersa en la biblioteca .NET?

Question

¿Ya hay una estructura de datos implementada en la biblioteca .NET que actúa como matriz dispersa (donde la mayoría de los índices están vacíos) con O (1) acceso por índice y O (1) acceso al siguiente elemento (y anterior)?

Answer 1

No sé de ningún recipiente incorporados como usted quiere, pero como solución alternativa se puede utilizar un Dictionary de los siguientes elementos:

class Entry<T> 
{ 
    int previdx, nextidx; 
    T data; 
} 

(diccionario en .NET tiene O (1) búsqueda, ya que está basada en hashtats). Para que la inserción sea O (log n), necesitamos mantener una lista ordenada de los índices ya existentes (esto no existe de fábrica, pero can be easily emulated)

Answer 2

Configuré un list of the lists in dotnet por un tiempo hace. No hay una lista dispersa allí.
Lo menciono de todos modos porque puede ser de ayuda si decide desarrollar uno usted mismo.

Answer 3

Aquí hay una matriz dispersa basada en un diccionario (en su mayoría no probado, acabo de poner juntos después de leer esta pregunta):

using System; 
using System.Collections; 
using System.Collections.Generic; 
using System.Linq; 

namespace NobleTech.Products.Library.Linq 
{ 
    public class SparseList<T> : IList<T> 
    { 
     private T defaultValue; 
     private Dictionary<int, T> dict; 
     private IEqualityComparer<T> comparer; 

     public SparseList(T DefaultValue = default(T)) 
      : this(DefaultValue, EqualityComparer<T>.Default) 
     { 
     } 

     public SparseList(IEqualityComparer<T> Comparer) 
      : this(default(T), Comparer) 
     { 
     } 

     public SparseList(T DefaultValue, IEqualityComparer<T> Comparer) 
     { 
      defaultValue = DefaultValue; 
      dict = new Dictionary<int, T>(); 
      comparer = Comparer; 
     } 

     public int IndexOf(T item) 
     { 
      if (comparer.Equals(item, defaultValue)) 
       return LinqUtils.Generate().First(i => !dict.ContainsKey(i)); 
      return dict.Where(kvp => comparer.Equals(item, kvp.Value)) 
       .Select(kvp => (int?)kvp.Key).FirstOrDefault() ?? -1; 
     } 

     public void Insert(int index, T item) 
     { 
      if (index < 0) 
       throw new ArgumentOutOfRangeException("index", index, "index must be non-negative"); 
      if (index < Count) 
       dict = dict.ToDictionary(kvp => kvp.Key < index ? kvp.Key : kvp.Key + 1, kvp => kvp.Value); 
      this[index] = item; 
     } 

     public void RemoveAt(int index) 
     { 
      if (index < 0) 
       throw new ArgumentOutOfRangeException("index", index, "index must be non-negative"); 
      dict.Remove(index); 
      if (index < Count) 
       dict = dict.ToDictionary(kvp => kvp.Key < index ? kvp.Key : kvp.Key - 1, kvp => kvp.Value); 
     } 

     public T this[int index] 
     { 
      get 
      { 
       if (index < 0) 
        throw new ArgumentOutOfRangeException("index", index, "index must be non-negative"); 
       if (dict.ContainsKey(index)) 
        return dict[index]; 
       return defaultValue; 
      } 
      set 
      { 
       if (index < 0) 
        throw new ArgumentOutOfRangeException("index", index, "index must be non-negative"); 
       dict[index] = value; 
      } 
     } 

     public void Add(T item) { this[Count] = item; } 

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

     public bool Contains(T item) 
     { 
      return comparer.Equals(item, defaultValue) || dict.Values.Contains(item, comparer); 
     } 

     public void CopyTo(T[] array, int arrayIndex) 
     { 
      if (array == null) 
       throw new ArgumentNullException("array"); 
      if (arrayIndex < 0) 
       throw new ArgumentOutOfRangeException("arrayIndex", arrayIndex, "arrayIndex must be non-negative"); 
      for (int i = 0; i < array.Length - arrayIndex; ++i) 
       array[arrayIndex + i] = this[i]; 
     } 

     public int Count { get { return (dict.Keys.Max(i => (int?)i) ?? -1) + 1; } } 

     public bool IsReadOnly { get { return false; } } 

     public bool Remove(T item) 
     { 
      int index = IndexOf(item); 
      if (index < 0) 
       return false; 
      RemoveAt(index); 
      return true; 
     } 

     public IEnumerator<T> GetEnumerator() 
     { 
      return LinqUtils.Generate(i => this[i]).GetEnumerator(); 
     } 

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

La implementación de LinqUtils.Generate se deja como ejercicio para el lector :-)

Answer 4

Hace un par de años (lo siento, llegué tarde a esta pregunta!) Implementé una colección dispersa basada en mi "AList" concept. Se llama SparseAList, y es probablemente mejor que cualquier solución "simple" que pueda rodar usted mismo. Por ejemplo, la solución de @NathanPhilips tiene Insert y RemoveAt métodos que llaman al ToDictionary. Enumerable.ToDictionary es un método O (N) - regenera todo el diccionario "desde cero" - por lo que no es eficiente.

SparseAList, por el contrario, se basa en el B+ tree, por lo que tiene inserciones O (log N) eficientes, búsquedas y eliminaciones, y también utiliza la memoria de manera eficiente. Se incluye en Loyc.Collections.dll en LoycCore, disponible en NuGet y GitHub.