.NET库中是否有稀疏数组的实现？

Question

在.NET库中是否已经实现了类似于稀疏数组的数据结构（其中大多数索引为空），并且可以通过索引进行O(1)访问，同时可以通过O(1)访问下一个（和上一个）元素？

- zduny

---

请参见https://dev59.com/MHRA5IYBdhLWcg3w_DHF。或者您可以尝试Math.Net：http://numerics.mathdotnet.com/。 - Monroe Thomas

Answer 1

几年前，我根据我的"AList" concept实现了一种基于稀疏集合的算法。它叫做SparseAList, 可能比你自己编写的任何“简单”解决方案都要好。例如，@NathanPhilips的方案具有Insert和RemoveAt方法，它们调用ToDictionary。Enumerable.ToDictionary是一个O(N)的方法-它从头开始重新生成整个字典-因此不高效。

SparseAList是基于B+树的，因此它具有高效的O(log N)插入、查找和删除操作，并且还可以高效地使用内存。它包含在LoycCore中的Loyc.Collections.dll中，可在NuGet上获取（搜索Loyc.Collections）。

- Qwertie

Answer 2

我不知道是否有内置的容器符合你的要求，但是你可以使用以下项的字典作为解决方案：

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

在.NET中，字典（dictionary）具有O(1)的查找效率，因为它是基于哈希表的。要使插入具有O(log n)的时间复杂度，我们需要维护一个已存在索引的排序列表（这不是开箱即用的，但可以轻松地进行模拟，可以参考这里）

- Vlad

---

不错，但我认为实现起来并不容易。嗯，在我的情况下，我将只使用存储其索引的节点链表、插入排序和简单的数组（或字典）查找。O(n)的插入有点困扰我，但我认为这方面无法做些什么，也不是那么糟糕。 - zduny

我刚意识到对于快速插入，我们需要一个已排序索引列表，这样你可以在O（log n）时间内检查哪个索引将成为新索引的下一个/上一个。 - Vlad

Answer 3

我之前整理了一个dotnet中的列表清单，其中没有稀疏列表。
无论如何，我还是提一下，因为如果你决定自己开发一个，它可能会有所帮助。

- LosManos

Answer 4

这是一个基于字典的稀疏数组（大部分未经测试，我只是在阅读这个问题后把它组合起来的）：

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 的实现留给读者作为练习 :-)

- Nathan Phillips