.NETライブラリにスパース配列の実装はありますか？

Question

インデックスによるO（1）アクセスと次の（および前の）要素へのO（1）アクセスで、スパース配列（ほとんどのインデックスが空である）のように動作する.NETライブラリのデータ構造は既に実装されていますか？

Answer 1

あなたが望むように私は、任意の組み込みのコンテナを知りませんが、回避策としては、以下の項目のDictionaryを使用することができます。

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

（.NETの辞書はOを持っている（1）ルックアップ、それはハッシュテーブルベースです）。 O（log n）を挿入するには、すでに存在するインデックスのソートされたリストを保持する必要があります（これはすぐには存在しませんが、can be easily emulated）

Answer 2

私はlist of the lists in dotnet前。そこにスパースリストはありません。
自分で開発することを決めた場合は、何らかの援助ができるので、とにかく言及します。ここで

Answer 3

は（私はこの質問を読んだ後、それを一緒に入れて、主にテストされていない）辞書に基づいて、スパース配列です：

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

LinqUtils.Generateの実装は

:-)読者の演習として残して

Answer 4

数年前（申し訳ありませんがこの質問に遅れています）私は"AList" conceptに基づいて疎なコレクションを実装しました。それはSparseAListと呼ばれ、おそらくあなたが自分自身を回すかもしれない "シンプル"な解決策より優れています。たとえば、@ NathanPhilipsのソリューションはInsertとRemoveAtのメソッドを呼び、ToDictionaryを呼び出します。 Enumerable.ToDictionaryはO（N）メソッドです。辞書全体を "ゼロから"再生成するので、効率的ではありません。

SparseAListは、対照的に、B+ treeに基づいているので、（Nログ）挿入、検索および削除効率的なOを有し、そしてそれはまた、メモリを効率的に使用します。 Loyc.Collections.dllにはLoycCoreが含まれています。これはNuGetとGitHubで利用できます。