さて,Permutationクラスでは

さて,Permutationクラスでは長さが13位上の置換を生成できないというのはやむを得ないとして,ELSIEをその代用とすることが果たして可能なのか?ELSIEの論理では行列のセルの値は整数であり,その絶対値が意味を持っていると考えられるから,値の範囲が異なる行列を比較することはそもそも不可能なのではないか?文字列を数値に置き換えることはできたとしても,2つの行列でまったく異なるコード系が使われている場合には対処できないと思われる.たとえば,S4の2つの部分群は位相同型であったとしても,数値の範囲はまったく異なるはずだ.

サンプルを修正してテストしてみた.example0.maxの1をすべて3に書き直したサンプルはexample0.maxと同型と認定された.これと同型のexample1.maxでも同じ結果になった.別の数字を入れたもの,同じ数字でも値を変えたものは見破られた.これはもしかすると使えるかも知れない.int MatrixIsomorphism(int N, ISOMORPH *p0, Mat& d0, ISOMORPH *p1, Mat& d1)の動作をチェックしてみよう.

この関数は与えられた2つのマトリックスd0, d1からISOMORPHを生成/検定している.ELSIEが使えそうな見込みが出てきたので,準同型検定にプロジェクトとして組み込むことにする.⇒ElsieComeBackプロジェクトを準同型検定CSに組み込み,DLLを生成するような構成とした.これで,C#からELSIEの関数が呼び出せるようになればよいのだが…

S4ではエラーが出てしまうので,A4を生成するようにしてみたが,かなり時間が掛かる.時間が掛かるだけでなく,例外が発生した.OutOfMemoryだ.

image

ヒープを大きくするなどなにか対策はあるのかも知れないが,やむを得ない.⇒A4の群検査が失敗したあと,もう一度ボタンを押してA4を再検査しようとしたら,「群A4は結合法則を満たさない:A=b B=b C=f (AB)C=f A(BC)=a」で抜けてしまった.これはなぜか?⇒多分乗積表が作り切れなかったのだろう.A4を群として構築したことはこれまでなかったのだろうか?もう少し小さいサンプルで試してみよう.

V4を初期生成して群の検査でエラーになった.「インデックスが配列の範囲外です」

image

自己同型検定→群同型判定で例外が発生している.置換のダンプで失敗しているようだ.⇒VBのUBoundでは最大インデックスを返していたので,その値で配列にアクセスできたが,GetLengthでは長さを返しているので,一つ小さくする必要がある.⇒UBoundが使われていた箇所を点検する必要がある.⇒片付けた.

メモリ不足はPermutationで起きている.プロセスメモリの4GBをほぼ使い切っているが,全メモリ16GBのうち,まだ5.6GBは残っている.⇒Permuteの入口でダンプしたり,DoEventsを実行したりすると,このメモリ不足は発生しなくなる.ダンプを実行した場合には,メモリ使用量はほとんど増加しないが,処理は相当遅くなるものと推定される.DoEventsを実行した場合には,メモリ使用量は増加の傾向が見られるが,その傾きはきわめて緩やかで,おそらくA4の置換をすべて列挙するまで停止することなく走り続けることができそうだ.

これはどういうことかというと,4GBのメモリを食っているのは一重にOSのメモリ管理の非力の所為であると言って過言ではない.つまり,GCにはそれなりの時間が掛かるため,完全なガベージコレクションができていないということを意味する.これは前々から分かっていたことだが,64ビットになって2GBの制約から解放されたにも掛かわらず,ほとんど進歩していないと断じても間違いではない.我々の参照管理を適用すれば,100%の完全なガベージコレクションを実現可能であることを考えると,これは現行のOSの大きな欠陥とみなしても差し支えないと思う.この意味では我々がやってきたことは間違っていなかったと断言できる.⇒いや,そこまで言うのは言い過ぎかもしれない.

メモリ使用量の増加の傾きが小さいのは,単純に時間が掛かっているというだけだろう.いずれにしてもメモリを実消費していることは間違いないのだから,いつかはメモリ不足の状態になるに違いない.24!というのはとてつもなく大きな数である.620448401733239439360000x1行分のメモリということになれば,GBでは到底追いつけないことは確かだ.置換を生成するだけでよいのなら,必ずしもメモリは必要ない.その都度消費してしまえばよいというだけの話だ.

つまり,Permuteの中で実質的な検査を行うことができれば,メモリの浪費は防ぐことができる.もし,「自己同型」というのが,「恒等写像以外の同型写像を一つでも持つ」ということでよいのなら,おそらく検査にそれほどの時間を費やす必要もなくなるのではないだろうか?もちろん,同型でない場合には最後までやらなくてはならないことになってしまうが,それもある程度までは事前検査で弾くことは可能であると思われる.A4の場合は,m=479001600なので,メモリへの書き込みを実施しなければそこそこの時間で完了する.

ただし,さすがに479001600x12のマトリックスは生成できない.

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA