-5

コンピューターでスパース行列（0と1）を格納および操作する場合、マトリックスのスパース構造を利用する特殊なアルゴリズムとデータ構造を使用することが有益であり、多くの場合必要です。標準の行列構造とアルゴリズムを使用した操作は低速であり、大規模なスパース行列に適用すると大量のメモリを消費します。スパースデータは本質的に簡単に圧縮され、この圧縮によりほとんどの場合、メモリ使用量が大幅に削減されます。

行数が事前にわかっている2次元マトリックスが与えられます（30〜256の任意の数を選択できます）。列の数は非常に多いです。あなたは106列を考えることができます。各列には、1の値が1つだけあります。

この行列のスペースの複雑さを最小化するアルゴリズムを記述します。アルゴリズムがどのように機能するかを示したり、プログラムを作成したりすることもできます。

4

4 に答える 4

2

ヒント（これは宿題用です）：各列には「1」のフィールドが1つだけ含まれているため、各列にこれが当てはまる行を格納するだけで十分です。次に、行数が256未満であることを考慮して、この情報を格納するための適切な方法を考えてください。

于 2009-10-23T20:15:09.883 に答える
0

スパース行列は、CSに2つの異なる方法で格納されます。隣接行列または隣接リスト：行列を使用したいと思うので、いくつかのオプションがあります：CSR、ギザギザの対角線、CSCなど：アルゴリズムを学ぶためにウィキペディアをお勧めします。基本的に、マトリックスを3つの異なる1-d配列に分解します。

于 2009-10-24T05:16:19.557 に答える
0

あなたは、（たとえば）有限要素コードに現れる「一般的な」スパース行列よりもはるかに、厳しく制約された問題に取り組んでいます。特に、ほとんどの場合、人々が利用できないこれらのアイテムを利用することができます。

  1. 行数は一定であり、選択することができます。
  2. 行列の任意のセルに表示される数は、1または0のいずれかです。
  3. 各列には、ゼロ以外の値が1つだけ含まれています。

ここで一時停止して、この行列が1つの非常に一般的なケースである順列行列でこの形式に近い形で表示されると言いましょう。ただし、これらの場合は常に正方行列（列と同じ行数）です。

これは、実装が簡単で、サイズN x M（N行、M列）の行列を格納するために必要な正確なバイト数を簡単に書き留めることができる非常に基本的な圧縮スキームです。N = 256とします。これは、行を0〜255の数値として表すことができることを意味します。これは、正確に符号なしの8ビット数値です。行列を符号なし8ビット（1バイト）整数の1x M配列として格納します。ここで、インデックスiの値は、列iの値1を含む行番号です。値自体を格納する理由はありません（常に1であるため）。また、配列インデックスとして表すため、列番号を明示的に格納する必要はありません。

「高密度」NxMマトリックスが4バイト整数を格納するとします。このようなマトリックスには、N * M*4バイトのメモリが必要です。私が説明した圧縮では、Mバイトのメモリしか必要としません。これは、説明したように、元のメモリの1/1024です。

于 2009-11-01T18:34:04.097 に答える
0

スパース行列を表すために必要なスペースを最小限に抑える簡単なアルゴリズムを作成しました。役に立つと思います:)。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace sparse_matrix
{
    class Program
    {
        static void Main(string[] args)
        {
            /*
             * In this algorithm I store all the Sparse Matrix into single diminsion matrix of type byte, each row
             * in this matrix has a number that represent the position of the "1" in the original Sparse matrix.
             * By this way, I save a lot of space... and store the same matrix with the minimum space(I could reach)
             * Since I treat the digits as bits, and stored them into the byte, since the biggest number I will reach
             * will not exceed 255 bit.
             * I read about the byte data type from here:(http://msdn.microsoft.com/en-us/library/5bdb6693.aspx)
             * In this program, I run it on a (3 * 3) matrix, however it can work the same for (255 * 10^6)
             */
            int matrixRows = 3;
            int matrixColumns = 3;
            int[,] matrix;
            matrix = new int[matrixRows, matrixColumns];
            matrix[0, 0] = 0;
            matrix[1, 0] = 0;
            matrix[2, 0] = 1;
            matrix[0, 1] = 1;
            matrix[1, 1] = 0;
            matrix[2, 1] = 0;
            matrix[0, 2] = 0;
            matrix[1, 2] = 1;
            matrix[2, 2] = 0;

            byte []x = new byte [matrixColumns];
            Console.WriteLine("The Original Sparse Matrix:\n");

            for (int i = 0; i != matrixColumns; i++)
            {
                for (int j = 0; j != matrixRows; j++)
                {
                    if (matrix[j, i] == 1)
                    {                        
                        x[i] = (byte)j;
                    }
                    Console.Write(matrix[i, j] + " ");
                }
                Console.WriteLine();
                Console.WriteLine();
            }
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine("The new representation for the Sparse matrix:\n");
            for (int k = 0; k != matrixColumns; k++)
            {
                Console.WriteLine(x[k] + "\n");
            }
        }
    }
}

フィードバックをお寄せいただければ幸いです。

于 2009-10-26T23:02:34.000 に答える