Geek asks and answers

Is there a sparse array implementation in the .NET library?

Is there an already implemented data structure in the .NET library that acts as a sparse array (where most indexes are empty) with O (1) access by index and O (1) access to the next (and previous) element?

+5
source share
4 answers

I don’t know any built-in containers as you want, but as a workaround you can use the Dictionaryfollowing elements:

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

(the dictionary in .NET has an O (1) search because it hashtable-based). In order for the insert to be O (log n), we need to save a sorted list of existing indexes (this does not exist out of the box, but it can be easily emulated )

+2

dotnet . .
, , .

+1

(, !) , "AList" , SparseAList, , , , "" , . , @NathanPhilips Insert RemoveAt, ToDictionary. Enumerable.ToDictionary - O (N) - " " - .

SparseAList , in contrast, is based on a B + tree , so it has efficient attachments (O), search and delete O (log N), and also uses memory efficiently. It is included in Loyc.Collections.dll in LoycCore , available on NuGet and GitHub.

+1
source

Here's a sparse array based on a dictionary (mostly unchecked, I just compiled it after reading this question):

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

The implementation is LinqUtils.Generateleft as an exercise for the reader :-)

0
source

More articles:


All Articles