cacheは、データをキャッシュするためのキャッシュ。cacheはプロセッサによって実行される命令をキャッシュするためのキャッシュ。命令をキャッシュするとはどういうことか?ストアドプログラム方式では実行されるプログラムもメモリに格納されているため、プロセッサは実行する命令をメモリから読まなければいけない。よってプロセッサから見ると命令もある種のデータなのである。キャッシュサイズを参照Debian系マシンではlscpuコマンドでキャッシュサイズを確認できる。L1-L3トータルで3MB以上ある。予想してたよりも容量大きい。3072Kキャッシュヒット率を計測Linuxのパフォーマンス解析ツールperfを使って、キャッシュヒット率を計測してみた。例として、以下の2つの方法で行列の掛け算を行ったときのキャッシュヒット率を計測する。0;}プログラムAとプログラムBの違いは、multiply関数のループの部分だけである。jの順でループを回す。大した違いは無さそうであるが、キャッシュのヒット率によって大きな違いが生じる。コンパイルは以下のように行った。1.184sとなった。約8倍ほどプログラムBの方が高速。それぞれのプログラムでキャッシュ参照数、キャッシュミス数などを以下のコマンドで出力してみた。./a結果は以下のとおり。プログラムAでは、プログラムBの約13.8倍のキャッシュミスが発生していた。メモリアクセスの回数が13.8倍多いということ。メモリアクセスがボトルネックとなって、1サイクルあたりの命令実行数にも差が生じていることが分かる。UNIX元気が出る動画(3)シゴトでココロおどろう「好きなことを仕事にする。「好きなことだけを続ける。「全ては後からついてくる。「目の前のことを全力でやってみてダメだったら次へ。「シゴトでココロおどろう。プログラム中国剰余定理のプログラム(連立合同式を解くプログラム)を書いてみた。中国剰余定理とは?2で割ると1余り、3で割ると2余り、5で割ると3余る数なーんだ?というような問題を考える。この問題を式で表すと、以下のような連立合同式になる。法が互いに素であれば、法の総積を法としてxは一意に定まる。以下ではそのようなxを効率的に求めることを考える。法が互いに素な場合の解法は、以下のとおり。m1)を解きたいとする。m0とすれば、xは上の方程式の解である。これは以下のように確認できる。m1が互いに素ではない場合を考える。この場合は、m0、m1が互いに素になるように素因数を片方に寄せればよい。...と素因数分解されるとする。素因数pkの個数を考える。m0の方がm1よりpkを多く持っていれば、pkはすべてm0に寄せる。ない場合は、pkはすべてm1に寄せる。m1が互いに素な場合に帰着する。mod]テストテストコード。success"サンプル標準入力から連立合同方程式を受け取って、解くプログラム。解を10個出力するようにしている。235383113143173203233263293次に、法が互いに素ではない連立式を解いてみる。漸化式を解く5つの方法を纏めた以下のページがなかなかよかった。前のk項の線形結合の場合に、どのように一般項を導出すればよいかが記載されている。sequenceなので高校数学で習う。anはp(n)より1つ高次の多項式になるらしい。4.は高校のとき習った。特性方程式を解けばいい。母関数を使って一般項を出す方法も紹介されている。4.と5.の方法を使ってフィボナッチ数列の一般項を求めてみた。解くほうが断然楽だった。最近知ったちょいテクをメモっておく。Nで計算することを考える。1であれば、分子に2の逆元をかければいい。2を計算すればよい(※)。dのいずれかは必ず2で割り切れるので、予め割れる方を割っておけば赤字のテクニックを知らなくても計算できる。