2012-07-01 60 views
5

是否已經在.NET庫中實現了像稀疏數組(其中大多數索引爲空)的O(1)訪問和O(1)訪問下一個(和前一個)元素的數據結構?.NET庫中是否有稀疏的數組實現?

+0

請參閱http://stackoverflow.com/questions/756329/best-way-to-store-a-sparse-matrix-in-net。或者你可以嘗試Math.Net:http://numerics.mathdotnet.com/ –

回答

2

我不知道任何內置的集裝箱像你想要的,但作爲一個變通方法,您可以使用以下物品的Dictionary

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

(字典在.NET中有O(1)查找,因爲它是基於散列表的)。對於插入爲O(log n),我們需要保留已經存在的索引的排序列表(這不是開箱即用的,但是can be easily emulated

+0

不錯,但我認爲不容易實現。那麼,我想我的情況下,我將只使用存儲其索引,插入排序和簡單的數組(或字典)查找節點鏈表。 O(n)插入有點讓我煩惱,但我認爲不能做任何事情,畢竟它也不是那麼糟糕。 – mrpyo

+1

@mrpyo:我剛剛意識到,爲了快速插入,我們需要一個索引的排序列表,以便您可以在O(log n)時間檢查哪個索引將成爲新索引的next/prev。 – Vlad

1

我把一個list of the lists in dotnet放在一起前。那裏沒有稀疏的名單。
無論如何我都會提到它,因爲如果你決定自己開發一個,它可以是一些幫助。

+0

感謝分享。 – NoChance

0

下面是基於字典的稀疏陣列(主要是未經檢驗的,我只是把它一起閱讀這個問題後):

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的實現作爲一個練習讀者:-)

1

幾年前(對不起,我遲到了這個問題!)我根據我的"AList" concept實施了一個稀疏集合。它叫做SparseAList,它可能比任何你可能推出的「簡單」解決方案都要好。例如,@NathanPhilips的解決方案有InsertRemoveAt方法調用ToDictionaryEnumerable.ToDictionary是一個O(N)方法 - 它從頭開始重新生成整個字典 - 所以效率不高。

SparseAList相比之下,基於B+ tree,因此它具有高效的O(log N)插入,查找和刪除功能,並且它還可以高效地使用內存。它包含在Loyc.Collections.dll的LoycCore中,可在NuGet和GitHub上獲得。