Có thực hiện mảng thưa thớt trong thư viện .NET không?

Question

Có cấu trúc dữ liệu đã được triển khai trong thư viện .NET hoạt động như mảng thưa thớt (trong đó hầu hết chỉ mục trống) với truy cập O (1) bằng chỉ mục và truy cập O (1) tới phần tử tiếp theo (và trước đó) không?

Answer 1

Tôi không biết về bất kỳ container built-in như bạn muốn, nhưng như một cách giải quyết bạn có thể sử dụng một Dictionary các mục sau đây:

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

(từ điển trong .NET có O (1) tra cứu, vì nó có thể dựa trên hashtable). Để chèn vào là O (log n), chúng ta cần giữ một danh sách đã sắp xếp của các chỉ mục đã tồn tại (điều này không tồn tại ngoài hộp, nhưng can be easily emulated)

Answer 2

Tôi đặt cùng một list of the lists in dotnet một lúc trước đây. Không có danh sách thưa thớt ở đó.
Tôi đề cập đến nó anyway bởi vì nó có thể được một số trợ giúp nếu bạn quyết định phát triển một mình.

Answer 3

Dưới đây là một mảng thưa thớt dựa trên một từ điển (chủ yếu là chưa được kiểm tra, tôi chỉ cần đặt nó lại với nhau sau khi đọc câu hỏi này):

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

Việc thực hiện LinqUtils.Generate là trái như một bài tập cho người đọc :-)

Answer 4

Một vài năm trước (xin lỗi tôi đến muộn câu hỏi này!) Tôi đã triển khai một bộ sưu tập thưa thớt dựa trên số "AList" concept của mình. Nó được gọi là SparseAList và có lẽ nó tốt hơn bất kỳ giải pháp "đơn giản" nào mà bạn có thể tự cuộn. Ví dụ: giải pháp @NathanPhilips 'có các phương thức Insert và RemoveAt gọi ToDictionary. Enumerable.ToDictionary là một phương pháp O (N) - nó tái tạo toàn bộ từ điển "từ đầu" - vì vậy nó không hiệu quả.

SparseAList, ngược lại, dựa trên B+ tree, do đó, nó có hiệu quả O (log N) chèn, tra cứu và xóa bỏ, và nó cũng sử dụng bộ nhớ hiệu quả. Nó được bao gồm trong Loyc.Collections.dll trong LoycCore, có sẵn trên NuGet và GitHub.