今回は、PythonでSparse Matrixを実装する際に使用するデータ構造について紹介します。
さっそく始めてみましょう。
この記事もチェック：PythonでMax Heapデータ構造を実装する方法
スパースマトリクスとは？
スパース行列とは、ゼロの要素を多く含む行列の一種です。
つまり，疎行列のほとんどの項目は 0 であり，そのため，疎行列が占めるメモリのほとんどは 0 で構成されています．例えば、次のような行列がスパース行列です。
A = [
[0, 4, 0, 0],
[2, 0, 0, 5],
[0, 0, 0, 0],
[0, 0, 0, 1]
] |
見ての通り、4つの項目を除いて残りは0であり、この冗長な0がメモリ上の大きなスペースを占有しています。
スパース行列は，このような行列を格納するための最適化された方法です．基本的には、0以外の項目の順序付きリストです。
スパース行列の各行には、ゼロでない要素の行と列、およびゼロでない要素そのものが格納されます。
つまり、上の行列Aに対して、そのスパースな対応表は次のようになります。
A = [
[0, 1, 4],
[1, 0, 2],
[1, 3, 5],
[3, 3, 1]
] |
最初の行の要素は0、1、4なので、項目4はインデックス0、1、同様に、2はインデックス1、0、などです。
このように、通常の行列よりも少ないスペースで、しかも行列が巨大な場合は、スパース行列の方が大幅に少ないスペースですむことがわかります。
この行列をスパース行列として利用するには，クラスで実装し，入力，印字，加算，減算，乗算などのメソッドを定義する必要があります．
Pythonで作る疎行列
Pythonの疎行列のクラス定義を見てみましょう。
class Sparse:
def __init__(self, rows, columns):
self._matrix = []
self._num = 0
self._rows = rows
self._columns = columns
def __repr__(self):
prnt = f"Shape: {self._rows} x {self._columns}
for lst in self._matrix:
prnt += lst.__repr__() + '
prnt += f"Total: {self._num}"
return prnt
def insert(self, row, column, value):
if row < 0 | column < 0 | row >= self._rows | column >= self._columns:
raise ValueError("Invalid row or column")
if(value == 0):
raise ValueError("Zeroes are not included in a sparse matrix")
filled = False
for i in range(self._num):
if(self._matrix[i][0] < row):
continue
elif(self._matrix[i][0] > row):
self._matrix.insert(i, [row, column, value])
self._num += 1
filled = True
break
elif(self._matrix[i][1] < column):
continue
elif(self._matrix[i][1] > column):
self._matrix.insert(i, [row, column, value])
self._num += 1
filled = True
break
else:
raise ValueError("The position is already filled")
if(filled == False):
self._matrix.append([row, column, value])
self._num += 1
return
def remove(self, row, column):
if row < 0 | column < 0 | row >= self._rows | column >= self._columns:
raise ValueError("Invalid row or column")
for i in range(num):
if(self._matrix[i][0] == row | self._matrix[i][1] == column):
return pop(i)
return None
def size(self):
return self._num
def shape(self):
return tuple((self._rows, self._columns))
def display(self):
print(self)
def add(self, obj):
if(isinstance(obj, Sparse) != True):
raise TypeError("add() method needs an object of type Sparse")
if(self.shape() == obj.shape()):
result = Sparse(self._rows, self._columns)
else:
raise ValueError("Invalid row or columns")
i = 0
j = 0
k = 0
while((i < self._num) & (j < obj._num)):
if(self._matrix[i][0] < obj._matrix[j][0]):
result._matrix.insert(k, self._matrix[i])
k += 1
i += 1
elif(self._matrix[i][0] > obj._matrix[j][0]):
result._matrix.insert(k, obj._matrix[j])
k += 1
j += 1
elif(self._matrix[i][1] < obj._matrix[j][1]):
result._matrix.insert(k, self._matrix[i])
k += 1
i += 1
elif(self._matrix[i][1] > obj._matrix[j][1]):
result._matrix.insert(k, obj._matrix[j])
k += 1
j += 1
else:
result._matrix.insert(k, list([self._matrix[i][0], self._matrix[i][1], self._matrix[i][2] + obj._matrix[j][2]]))
k += 1
i += 1
j += 1
while(i < self._num):
result._matrix.insert(k, self._matrix[i])
k += 1
i += 1
while(j < obj._num):
result._matrix.insert(k, obj._matrix[j])
k += 1
j += 1
result._num = k
return result
def fast_transpose(self):
occurrence = []
index = []
for i in range(self._columns):
occurrence.append(0)
for i in range(self._num):
occurrence[self._matrix[i][1]] += 1
index.append(0)
for i in range(1, self._columns):
index.append(index[i-1] + occurrence[i-1])
result = Sparse(self._columns, self._rows)
result._num = self._num
for i in range(self._num): result._matrix.append(list())
for i in range(self._num):
result._matrix[index[self._matrix[i][1]]] = list([self._matrix[i][1], self._matrix[i][0], self._matrix[i][2]])
index[self._matrix[i][1]] += 1
return result
|
上の定義はかなり大きいので、各関数を一つずつ見ていくことにします。
1. 1. __init__ メソッド
各疎行列に対して，行と列の数が最初に必要となります．この値はコンストラクタに渡され，空の疎行列が作成されます．
2. repr` メソッド
これは、オブジェクトに対して print() が呼ばれたときに表示される文字列を返します。
今回の例では、実際の疎行列と同様に、行列の形状や大きさを表示します。
3. 疎な行列における挿入と削除
ある位置に 0 ではない項目を挿入するには、単純に行列を走査して新しい項目の正しい位置を見つけ、そこに挿入します。
まず行を比較し、行が一致すれば列を比較します。
これらのうちどちらかが異なっていなければなりません。
そうでない場合は例外が発生します。
この処理を行う前に、入力を検証する必要があります。
与えられた項目が 0 であってはいけませんし、位置が行列の内部になければなりません。
指定された位置の項目を削除するには、行列の中の位置を見つけて、行全体を飛び出させるという単純な手順で行います。
4. 2つの疎行列の足し算
2 つの疎な行列の加算は，2 つのソートされたリストのマージと非常によく似ています．
2 つの行列は基本的にリストであり，その中に行を表す他のリストが含まれています．そして，これらの内部リストは，各リストの1番目と2番目の項目（各値の行と列のインデックス）が昇順に並ぶという意味でソートされています．
ここでは、 i, j, k という 3 つのインデックスを作成します。
-
iは、最初の行列の次の項目のインデックスです。 - j` は、2 番目の行列の次の項目のインデックスです。
- k` は、結果行列の次の項目のインデックスです。
次に，最初の行列の i 番目の項目と，2 番目の行列の j 番目の項目を比較します．行と列のインデックスに基づいて、どちらか先に来るはずの項目が結果行列に挿入され、それぞれのインデックスがインクリメントされます。
もし、両方の項目の行と列のインデックスが同じであれば、それらを足し合わせる必要があります。
最終的に、入力行列の1つが完成します。
この時点で、もう1つの行列からすべての項目を結果行列に挿入するだけで、2つの行列の合計が得られます。
5. 疎行列の高速転置
疎行列の転置は簡単で、行と列の値を入れ替えてから、疎行列の行を並べ替えるだけです。
しかし、このような操作は非常に非効率的です。
疎行列の構成方法から、この行列を転置するもっと高速な方法があるのです。
まず、このアルゴリズムを補助する2つのリストを作成します。
最初のリストは occurrence と呼ばれ、各列のインデックスが疎行列に現れる回数を格納します。
つまり、このリストのサイズは、疎行列の列のサイズとなり、各インデックスはその列を表します。
最初は 0 で埋められ、その後、疎行列を走査して各項目の列の値を探し、 occurrence リストでそのインデックスをインクリメントします。
2 番目のリストは index リストと呼ばれます。
このリストには、元の疎行列に変換されたときの各項目の結果のインデックスを格納します。
つまり， index[i] には，元の行列の列インデックス i を持つ最初の項目の新しいインデックスが格納されます．これは，元の行列の列インデックスが 0 の最初の項目が，転置行列の 0 番目のインデックスに入ることを意味します．次に、 index[i] を計算するために、 index[i-1] と occurrence[i-1] を追加します。
この後，疎行列の各項目を調べ，その項目の列インデックスを求め，そのインデックスにある index リストの値を探し，その値を転置行列の新しいインデックスとして使用します．
この後、同じ列インデックスを持つ次の項目が転置行列の次のインデックスに移動するように、使用したインデックス値をインクリメントします。
こうすることで、疎な行列を非常に効率的に転置することができます。
出力
まず、疎な行列を2つ作成します。
ここで、加算と高速転置の演算を行う。
まとめ
行列のほとんどが 0 で埋め尽くされるような場合、スパース行列の方がはるかに少ないストレージで済み、効率的です。
これらが何であるか、どのように作成し、実装するかを議論し、最後に、コードを実行して得られる出力でそれを確認しました。