是否已經在.NET庫中實現了像稀疏數組(其中大多數索引爲空)的O(1)訪問和O(1)訪問下一個(和前一個)元素的數據結構?.NET庫中是否有稀疏的數組實現?
回答
我不知道任何內置的集裝箱像你想要的,但作爲一個變通方法,您可以使用以下物品的Dictionary
:
class Entry<T>
{
int previdx, nextidx;
T data;
}
(字典在.NET中有O(1)查找,因爲它是基於散列表的)。對於插入爲O(log n),我們需要保留已經存在的索引的排序列表(這不是開箱即用的,但是can be easily emulated)
我把一個list of the lists in dotnet放在一起前。那裏沒有稀疏的名單。
無論如何我都會提到它,因爲如果你決定自己開發一個,它可以是一些幫助。
感謝分享。 – NoChance
下面是基於字典的稀疏陣列(主要是未經檢驗的,我只是把它一起閱讀這個問題後):
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
的實現作爲一個練習讀者:-)
幾年前(對不起,我遲到了這個問題!)我根據我的"AList" concept實施了一個稀疏集合。它叫做SparseAList,它可能比任何你可能推出的「簡單」解決方案都要好。例如,@NathanPhilips的解決方案有Insert
和RemoveAt
方法調用ToDictionary
。 Enumerable.ToDictionary
是一個O(N)方法 - 它從頭開始重新生成整個字典 - 所以效率不高。
SparseAList相比之下,基於B+ tree,因此它具有高效的O(log N)插入,查找和刪除功能,並且它還可以高效地使用內存。它包含在Loyc.Collections.dll的LoycCore中,可在NuGet和GitHub上獲得。
- 1. Node.js中JavaScript/ECMAScript數組是否「稀疏」?
- 2. Haskell中的稀疏數組?
- 3. 稀疏實現/ scikit學習
- 4. 元組的稀疏數組
- 5. Scipy稀疏...數組?
- 6. 是稀疏數據
- 7. 稀疏三元組稀疏矩陣matlab
- 8. 稀疏數組的長度
- 9. 稀疏矩陣的pLSA實現
- 10. R中是否有對dist函數的稀疏支持?
- 11. 極其稀疏數組
- 12. 填充稀疏數組
- 13. Python中是否支持稀疏矩陣?
- 14. matlab中的稀疏矩陣數組
- 15. 三維稀疏矩陣實現?
- 16. 稀疏束調整實現c/C++
- 17. 可可的NSMutableArray是否稀疏?
- 18. Incanter是否支持稀疏矩陣?
- 19. Java ArrayList是否支持稀疏標記?
- 20. 實現具有稀疏通用功能的子類
- 21. 的Fortran:稀疏數組或列表
- 22. OpenACC - 稀疏矩陣庫
- 23. 實現3維稀疏表的構造函數
- 24. 自動完成對'組織稀疏,tree`和'有機匹配,稀疏tree`
- 25. 是否有org.apache.commons.lang.StringEscapeUtils for .Net的實現?
- 26. 是否有.NET的XQuery 3.0實現?
- 27. 是否有Java或.NET的R實現?
- 28. 從npy文件加載稀疏數組
- 29. 排列密度和稀疏數組
- 30. Java中的稀疏矩陣實現和操作
請參閱http://stackoverflow.com/questions/756329/best-way-to-store-a-sparse-matrix-in-net。或者你可以嘗試Math.Net:http://numerics.mathdotnet.com/ –