Data Structures for storing Sparse Matrix

Am intalnit urmatoarea problema, ai de exemplu o foaie de excel, un fisier excel este o arhiva care contine XML-uri, parsezi fisierele din aceasta arhiva si vrei sa stochezi un sheet intr-o structura de date, un sheet este o matrice destul de mare care contine in mare parte celule empty si stocarea intr-o matrice normala ar fi ineficienta din punct de vedere al memoriei avand in vedere ca ar trebui sa aloci memorie pentru celule empty, solutia este un sparse matrix, intrebarea este ce structuri de date ai putea folosi sa reprezinti un sparse matrix.

Cea mai simpla cred ca ar fi jagged array, un jagged array este o matrice in care fiecare row poate avea un numar diferit de elemente.

int[][] jaggedArray2 = new int[][] 
{
    new int[] {1,3,5,7,9},
    new int[] {0,2,4,6},
    new int[] {11,22}
};

O alta solutie ar fi Dictionary of keys:

   public class SparseMatrix<T>
    {
        public int Width { get; private set; }
        public int Height { get; private set; }
        public long Size { get; private set; }

        private Dictionary<long, T> _cells = new Dictionary<long, T>();

        public SparseMatrix(int w, int h)
        {
            this.Width = w;
            this.Height = h;
            this.Size = w * h;
        }

        public bool IsCellEmpty(int row, int col)
        {
            long index = row * Width + col;
            return _cells.ContainsKey(index);
        }

        public T this[int row, int col]
        {
            get
            {
                long index = row * Width + col;
                T result;
                _cells.TryGetValue(index, out result);
                return result;
            }
            set
            {
                long index = row * Width + col;
                _cells[index] = value;
            }
        }
    }

Cea de-a doua structura de date este mai eficienta, operatiile frecvente a caror complexitate(O(n)) trebuie luata in considerare sunt operatiile de inserare, cautare in structura de date si un dictionar(hashtable) are complexitatea la cautare O(1), dar celulele in XML-ul din arhiva excel pot fi in alta ordine decat cea din sheet-ul deschis in excel, asa ca structura de date ar trebui sa construiasca si ordinea celulelor, aceasta ordine poate fi creata prin sortare sau eventual sa combini cu o alta structura de date care pastreaza ordinea ca un binary tree, ceea ce presupun ca face urmatoarea structura de date din .NET, SortedDictionary, cred ca cel mai interesant este de testat timp-ul de executie a operatiilor pe aceste structuri de date cu diverse set-uri de date.

Subiectul sparse matrix si structurilor de date existente folosite la reprezentare acesteia este dezbatut si pe wikipedia https://en.wikipedia.org/wiki/Sparse_matrix.

4 Likes