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

Question

インデックスによる O(1) アクセスと次の (および前の) 要素への O(1) アクセスを使用して、スパース配列 (ほとんどのインデックスが空である) のように機能する .NET ライブラリに既に実装されているデータ構造はありますか?

Answer 1

あなたが望むような組み込みコンテナは知りませんが、回避策としてDictionary、次のアイテムのいずれかを使用できます。

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

(.NET の辞書には、ハッシュテーブル ベースであるため、O(1) ルックアップがあります)。挿入が O(log n) になるようにするには、既存のインデックスの並べ替えられたリストを保持する必要があります (これはそのままでは存在しませんが、簡単にエミュレートできます) 。

Answer 2

数年前、 「AList」コンセプトに基づいてスパース コレクションを実装しました。それはSparseAListと呼ばれ、おそらく自分でロールする「単純な」ソリューションよりも優れています。たとえば、@NathanPhilips のソリューションにはInsertとRemoveAtを呼び出すメソッドがありますToDictionary。Enumerable.ToDictionaryO(N) メソッドです。辞書全体を「ゼロから」再生成するため、効率的ではありません。

対照的に、 SparseAListはB+ ツリーに基づいているため、効率的な O(log N) の挿入、検索、および削除が行われ、メモリも効率的に使用されます。これは LoycCore の Loyc.Collections.dll に含まれており、 NuGet で入手できます (Loyc.Collections を検索してください)。

Answer 3

少し前にドットネットのリストのリストをまとめました。そこにはまばらなリストはありません。
自分で開発することに決めた場合に役立つ可能性があるため、とにかく言及します。

Answer 4

Dictionary に基づくスパース配列を次に示します (ほとんどテストされていないため、この質問を読んだ後にまとめただけです)。

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、読者の演習として残されています :-)