同じグラフを二つの形で保存する
頂点数が同じでも、辺が少ないグラフと多いグラフでは適した表現が変わります。この実験では頂点200個の有向グラフを作り、隣接行列とCSR形式の隣接リストへ保存します。自己辺と重複辺は作りません。行列は一組の頂点へ1バイト、CSRは行の開始位置と行先を32ビットの整数で持ちます。二つの表現から各頂点の隣接先を取り出し、全て一致することを先にassertします。
容量を比較する前に、保存する情報を揃える必要があります。片方だけ辺の重みや逆方向の辺を持てば、別の仕事をしているためです。今回は重みのない有向グラフです。無向グラフなら一本の辺を二方向へ保存する規則などを別に決めます。グラフの数学的な辺数、保存する参照の本数、確保したバイト数を同じ数だとみなさないことが、実験の最初の目標です。
論理容量を式で予測する
頂点数V=200なので、行列の論理量はV²=40,000バイトです。辺数EのCSRでは、V+1個の開始位置とE個の行先を持ち、32ビットなら4(V+1+E)バイトです。自己辺を除いた最大辺数は200×199=39,800で、密度1%ならE=398、CSRは2,396バイトと予測できます。密度10%ではE=3,980、16,724バイトになります。
密度50%ではE=19,900、CSRは80,404バイトとなり、1バイト行列より大きくなります。疎なグラフならリストが小さい、という説明の条件が数値で見えます。もし行列を1ビットへ詰めれば行列の容量はさらに変わります。この実験の1バイトという選択は、全ての隣接行列の唯一の表現ではありません。使用する要素型を式とコードへ明記し、名前だけの比較にしないでください。
| 密度 | 辺数 | 1バイト行列 | 32ビットCSR |
|---|---|---|---|
| 1% | 398 | 40,000 B | 2,396 B |
| 10% | 3,980 | 40,000 B | 16,724 B |
| 50% | 19,900 | 40,000 B | 80,404 B |
実行条件と乱数を固定する
コードをgraph.pyへ保存し、Linux上のPythonで実行します。標準ライブラリだけを使います。乱数seedは7で、各密度について候補辺から重複なしに指定本数を選び、行先の順序を揃えるため整列します。CSRの整数配列のitemsizeが4バイトであることも検査します。異なる処理系で型幅が変わった場合、式だけを残して黙って続けず、型か予測式を修正してください。
入力候補の全辺リストと、選ばれた辺のリストも実験用のメモリを使います。そのため、最後に表示するプロセスのピークRSSは、片方の表現だけの費用ではありません。この小例は各表現の論理量とオブジェクトのサイズを比較し、RSSという別の尺度が同じ値にならないことを確認するための構成です。表現単独のRSS差を厳密に比べるなら、独立した子プロセスなどへ測定範囲を分ける必要があります。
全ての行の同一性を確認する
行列はi×V+jの位置を1にし、CSRは行iの行先をcolumnsへ追加した後に次の開始位置をoffsetsへ入れます。行iの範囲はoffsets[i]以上offsets[i+1]未満です。辺がない行でも、二つの開始位置が同じになるだけで表現できます。末尾の開始位置がEになることと、行先の合計本数がEになることを確認します。開始位置がV個だけでは最後の行の終端が分からないため、V+1個を使います。
容量の数値を出す前に、全200行で隣接先の配列が一致することをassertします。容量が小さくても辺を落としていれば良い表現ではありません。出力には頂点数、辺数、論理バイト数、sys.getsizeofによるオブジェクトのサイズ、プロセスのピークRSSを別々の項目で残します。これらを一列のメモリ量へ混ぜず、式で予測した値がどの項目に対応するかを説明してください。
import array,random,resource,sys
n=200;rng=random.Random(7)
for fraction in [0.01,0.1,0.5]:
pairs=[(i,j) for i in range(n) for j in range(n) if i!=j];edges=sorted(rng.sample(pairs,int(len(pairs)*fraction)))
matrix=bytearray(n*n);offsets=array.array('I',[0]);columns=array.array('I');cursor=0
assert offsets.itemsize==columns.itemsize==4
for i in range(n):
while cursor<len(edges) and edges[cursor][0]==i:
j=edges[cursor][1];matrix[i*n+j]=1;columns.append(j);cursor+=1
offsets.append(len(columns))
for i in range(n):assert [j for j in range(n) if matrix[i*n+j]]==list(columns[offsets[i]:offsets[i+1]])
logical_csr=4*(n+1+len(edges));logical_matrix=n*n
assert logical_csr==offsets.itemsize*len(offsets)+columns.itemsize*len(columns)
print('vertices=',n,'edges=',len(edges),'matrix_bytes=',logical_matrix,'csr_bytes=',logical_csr,'objects_bytes=',sys.getsizeof(matrix),sys.getsizeof(offsets)+sys.getsizeof(columns),'process_peak_rss_KiB=',resource.getrusage(resource.RUSAGE_SELF).ru_maxrss)
print('same directed graph, no self loops or duplicate edges; all rows matched')
読み取れる結果と読めない結果
論理式の予測はコードの配列長と型幅へ対応するので、この環境でも一致するはずです。一方、sys.getsizeofはオブジェクトの管理領域や確保の余分を含み、論理量より大きくなります。行列とCSRを作る順序でピークRSSの時点も変わり得ます。Linuxのru_maxrssはこのコードではKiBとして表示しますが、別OSでは単位が違う場合があります。実行したOSとPython版を結果と一緒に保存します。
この実験は、走査や一点の辺存在確認の時間を測っていません。行列なら添字で一組を調べやすく、CSRなら存在する隣接先だけをたどれますが、その操作の速さを今回の容量の大小から実測したとは言えません。CPUキャッシュやPythonのループ費用も別の要因です。容量の比較から分かることを限定し、速度の比較が必要になったら、同じ問い合わせ集合と正しい答えを揃えた別の計測を設計します。
RSSを比較したい場合は、表現ごとに別プロセスを起動して同じ準備を行います。今回の一つのプロセスの値から、表現別の増分は算出しません。
構築の一時領域と保存量の境界
CSRを作るために全候補辺を先に列挙する今回のコードは、構築中の一時領域も二次に増えます。完成したCSRの保存量がO(V+E)でも、この生成手順のピーク全体が同じとは限りません。巨大な疎グラフへ広げるなら、辺の生成を逐次にする、既存の辺列を使うなど、構築の方式も変える必要があります。
その際は、元のグラフが同じという検査を維持します。重複を除く処理や整列も別の時間と領域を使います。入力を読む、表現を作る、保持する、問い合わせるという四段階を分ければ、保存形式の比較がどの段階を対象としたかが分かります。今回のRSSを完成後のCSRだけの理論容量と比較して差を全て無駄と呼ぶのは誤りです。必要な一時データと測定範囲が異なるからです。
再実行時には同じPython版、型幅、頂点と辺の条件を揃えます。値が変わった場合、まず論理式の計算が変わったのか、オブジェクトの管理領域やプロセス全体が変わったのかを分けて調べてください。
演習:条件を変えて境界を計算する
課題はV=100、E=500の有向グラフについて、今回と同じ型で論理容量を求めることです。解答は行列10,000バイト、CSRは4×(101+500)=2,404バイトです。次にE=3,000ならCSRは12,404バイトとなり、行列より大きくなります。頂点数を固定して辺数だけ増やすと、どこで大小が変わるかを式から求め、実行の密度をその前後へ変えて確かめてください。
追加課題では行列を1ビットで保存する案を考えます。100×100ビットは管理領域を除けば1,250バイトです。ただしビットの読み書きや末尾のマスク、配列の表現が変わります。型を変えた後も以前の速度やオブジェクトサイズをそのまま引用しないようにします。実験終了後に残るファイルは保存したコードと結果だけで、ネットワークやDBの資源を作りません。入力、意味の一致、容量の式、実測の範囲をセットで説明してください。