2016-02-22

python networkxでグラフ書く

pythonでグラフ書くのが楽過ぎたので感動ついでに。
(参考：Amazon.co.jp： IPythonデータサイエンスクックブック ―対話型コンピューティングと可視化のためのレシピ集: Cyrille Rossant, 菊池彰: 本)

例：10頂点の完全グラフ

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

n = 10
adj = [(i,j%n) for i in range(n) for j in range(i+1,n)]    #辺のリスト
g = nx.Graph(adj)
nx.draw_circular(g)     #頂点をサイクル上に並べてグラフを描画
plt.savefig("compGraph.png")   #描画したやつを保存

んでできたのがこれ。
f:id:g0nChang:20160221234833p:plain
グラフ描画がたったこれだけで済むなんて!!!!
学生のころは

　・graphvizインストールして
　・C言語で隣接行列書いて
　・隣接行列からgraphviz用グラフ描画言語を作って
　・コマンドプロンプトで専用コマンド叩いて完成

というスーパーめんどくさい方法とっていたのでかなり感動した。

ランダムグラフ描画も簡単。(参考：自分のためのnetworkXメモ - 何かを書き留める何か)

#n=20, p=0.3
rg = nx.fast_gnp_random_graph(20, 0.3)
nx.draw_circular(rg)

f:id:g0nChang:20160221235932p:plain

やりたいことに対して、最も効率的な手段を選ぶって大事だなって思いました。

2016-02-08

連分数から近似分数を求める

前回の記事の続きです。

前回は $\sqrt{2}$ の連分数を求めるところまで説明しました。

ただ、連分数だけでは使い勝手が悪いです。見た目も気持ち悪いですし、近似分数がまだ求まっていません。今回は連分数から近似分数を求める話をします。

無理数を $\omega$ とし、 $\omega$ の連分数展開を $[a_0,a_1,a_2,...]$ としましょう。 $\omega$ は $\sqrt{2}$ や $\sqrt{3}$ だと思ってください。 $[a_0,a_1,a_2,...]$ は数列と見ることができますね。連分数展開から得られた数列の第 $i$ 項目までを使って得られた近似分数を $\gamma _i = \frac{p_i}{q_i}$ と表記し、第 $i$ 近似分数と呼びます。今後は $p_i,q_i$ がどのように求まるかを実際に計算をしながら見ていきます。

ためしに第0近似分数を求めてみましょう。といっても簡単ですね。第0近似分数は $a_0$ のみから得られる近似分数なので、

$\gamma _0 = \frac{a_0}{1}$

となります。よって、

$p_0=a_0, q_0=1$ ・・・(1)

です。第1近似分数はどうでしょうか。

$\gamma _1 = a_0 + \frac{1}{a_1}$

$\gamma _1 = \frac{a_0 a_1 + 1}{a_1}$

ということで、(1)式を使うと、

$p_1 = p_0 a_1 + 1, q_1 = q_0 a_1$ ・・・(2)

となります。ちょっとくどいですが、第2近似分数まで求めてみます。

$\gamma _2 = a_0 + \frac{1}{a_1 + \frac{1}{a_2}}$

$\gamma _2 = a_0 + \frac{a_2}{a_1 a_2 + 1}$

$\gamma _2 = \frac{a_0(a_1 a_2 + 1) + a_2}{a_1a_2 + 1}$

$\gamma _2 = \frac{a_2(a_0 a_1 + 1) + a_0}{a_1a_2 + 1}$

$\gamma _2 = \frac{a_2p_1 + p_0}{a_2q_1 + q_0}$ . ((1),(2)より)

ということで、

$p_2 = a_2 p_1 + p_0, q_2 = a_2 q_1 + q_0$

となります。なにかそれっぽい漸化式が出ましたね。偶然出てきた感じもしますが、この漸化式は一般に成り立ちます。すなわち、第 $i$ 近似分数の $\gamma_i = \frac{p_i}{q_i}$ は

$p_i = a_i p_{i-1} + p_{i-2}, q_i = a_i q_{i-1} + q_{i-2}$

となります。証明はこの記事ではしません。(次の記事でやるかも)

以上、この漸化式を解くことで連分数から近似分数を得ることができます。試しに $\sqrt{2}$ の第4近似分数までを求めてみましょう。 $\sqrt{2}$ の連分数展開は $[1,2,2,2,...]$ でした。

	分子	分母	値	誤差
$\gamma_0$	1	1	1	約0.41
$\gamma_1$	2*1+1=3	2*1	1.5	約0.11
$\gamma_2$	2*3+1=7	2*2+1=5	1.4	約0.01
$\gamma_3$	2*7+3=17	2*5+2=12	1.4166...	約0.002
$\gamma_4$	2*17+7=41	2*12+5=29	1.4137...	約0.0004

前の記事で書いた41/29が確かに $\gamma_4$ に出てきました。
誤差を見るとすごいですね。どんどん小さくなっています。

今回はこのへんで終わりにしたいと思います。次回は今回省略した証明の話か、最良性の話をできればなと思います。

[2016/2/14 追記]
pythonのMatplotlibで遊ぶついでに誤差をグラフにしてみました。
緑の直線が $\sqrt{2}$ 、青の折れ線が第 $i$ 近似分数の値です。
第4近似分数あたりからほぼ誤差がなくなっていることが視覚的にもわかると思います。
f:id:g0nChang:20160214190418p:plain

参考：
www.amazon.co.jp

2016-02-02

【メモ】C#でエクセルいじる(環境：Visual Studio)

C#でエクセル弄れたのでメモを残しておきます。人がわかるように書いてないです。一ヶ月後の私がこれ読んで役に立つか、とかも考えてないです。お察しください。
最初に「参照の追加」からMicrosoft Excel 15.0 Object Libraryを追加します。
Microsoft.Office.Interop.Excelがusingできるようになるのでusingします。これでExcelが弄れるようになりました。

書いたのが以下のソース。readFileName(エクセルファイル)の内容をwriteFileNameへコピーするだけです。例外処理とかは書いてないです・・・。

            //報告エクセル操作用オブジェクト
            Application xlAppR = new Application();
            Workbook xlBookR = xlAppR.Workbooks.Open(readFileName);
            Worksheet xlSheetR = xlBookR.Sheets[1];

            //更新エクセル操作用オブジェクト
            Application xlAppU = new Application();
            Workbook xlBookU = xlAppU.Workbooks.Open(writeFileName);
            Worksheet xlSheetU = xlBookU.Sheets[1];

            //報告内容を更新エクセルに書き込む
            Range xCellsR = null;
            Range xCellsU = null;

            xCellsR = xlSheetR.Cells;
            xCellsU = xlSheetU.Cells;
            int i=1;
            xCellsU[1, 1].Value = "aaa";
            
            //セルが空でない間、回る
            while (xCellsR[i, 1].Text.ToString() != String.Empty)
            {
                xCellsU[i, 2].Value = xCellsR[i, 1].Value;
                i++;
            }

            //解放をしないといけない
            xlBookR.Close(); xlBookU.Close();
            xlAppR.Quit(); xlAppU.Quit();
            Marshal.FinalReleaseComObject(xlAppR);
            Marshal.FinalReleaseComObject(xlAppU);
            xlAppR = null; xlAppU = null;

最後にオブジェクトの解放が必要です。いつまでも読み込み状態になって少し困りました。
エクセルでなくてもファイルを弄るときはだいたい必要。
上のコードだとメソッド終了後に「保存しますか？」ってダイアログが出てしまいますが、勝手に保存してくれるようにもできるみたいです。

最初のオブジェクトの用意とか最後のクローズ処理とかは共通モジュールにしたほうがいいかも。
参考サイトはいっぱいあったんですがメモり忘れました。

2016-01-31

連分数

連分数の話を書きます。連分数とは分母に更に分母が含まれている分数のことです。

たとえばこんなのです。

$a_0+\frac{1}{a_1+\frac{1}{a_2}}$

この例のように、分子がすべて1であるような連分数を正則連分数といいます。

上のように馬鹿正直に分数として書いてしまうと非常にめんどくさいので、正則連分数は ${[a_0,a_1,a_2]}$ と表記されることが多いようです。

本記事では正則連分数以外を扱いません。そこで正則連分数のことを単に連分数と呼ぶことにします。

参考：連分数 - Wikipedia

※正則連分数を単純連分数と表記するものもありましたが、ここではwikiに従います。

■連分数１_連分数イントロ
無理数というのがあります。これは小数点以下が不規則(循環せず)に、無限に続く数です。また、分数で表現できないという特徴があります。
代表的な無理数は $\pi、\sqrt{2}、\sqrt{3}$ などです。中学、高校くらいで習ったと思います。

コンピュータは有限桁の数しか扱えないので、これらの数をコンピュータ上で使おうとすると近似値を扱うしかありません。

ここで連分数が登場します(※1)。連分数は無理数を分数へ近似します。そして、この分数は無理数の良い近似となります。
※1. 説明上こんな風に書きましたが、実際にコンピュータ上で無理数を扱うのに連分数が使われているかは知りません。

$\sqrt{2}$ を例に説明します。
$\sqrt{2}$ は1.41421...と続く無理数です。 $\sqrt{2}$ の近似例として、
141/100=1.41(誤差：約0.004)
というのを見てみましょう。分母分子共に3桁の数で、誤差は約0.004です。

さて、ここで「もっと良い $\sqrt{2}$ の近似分数はないのか？」という疑問が出ます。
さきほどの例では分母が100で分子は141ですね。これは共に三桁の数です。
これよりも分母分子がより小さく、誤差もより小さければ嬉しいですよね。
なんというか「完全勝利！」という気分になれます。

実は、連分数を使えばこの嬉しい近似分数を得ることができます。
実際に連分数を使うと(例えば)次のような分数が得られます。
41/29=1.4137...(誤差：約0.0004)
前の単純な近似分数よりも小さい分母分子(どちらも2桁!)で、より良い近似が得られていることが分かります。さらに驚くことに、これよりも良い近似分数(分母分子が41,29より小さく、誤差も0.0004より小さい分数)はないことが証明されています。
つまり連分数から得られた近似分数が最良の近似分数となります。連分数に勝てる近似分数はないわけです。
「最良の」と言えてしまうことがすごいですよね。近似分数界の羽生善治です。湘北に負ける前の山王工業です。
数学はこういう風に「オラッ！俺が最優秀者様じゃ！ひざまづけ！」って言えるところが本当に面白いと思います。

■連分数２_連分数の計算方法
有理数の連分数展開はこちらを参照するのがよいかと思います。
ということで無理数の連分数展開の説明をします。

$\sqrt{2}$ で考えてみましょう。(参考)
便宜のため、 $x = \sqrt{2}$ とします。

$x^2 = 2$

より

$x^2 - 1 = 1$
$(x-1)(x+1)=1$
$x-1 = \frac{1}{x+1}$
$x = 1 + \frac{1}{x+1}$ (①)

さて、ここで右辺の $x$ に①を代入します。

$x = 1 + \frac{1}{1 + (1+\frac{1}{x+1})}$

$x = 1 + \frac{1}{2+\frac{1}{x+1}}$

またまた右辺の $x$ に①を代入します。同様の操作を繰り返すことで、 $\sqrt{2}$ の連分数展開

$[1,2,2,2,...]$

を得ます。今回は $\sqrt{2}$ を例に説明をしました。これに対して $\pi、e$ などは超越数と呼ばれ、展開の仕方が異なるみたいです。本記事では扱いません。

本当はここから分数を求める話をしたかったのですが、疲れたので終わりにします。

また気力があるときに書こうと思います。

2016-01-24

Javaで"//"を区切り文字として文字列を分割する

Java

流れは以下の通り。

Pattern ptn = Pattern.compile([区切り文字の正規表現]);
String strs = ptn.split([分割したい文字列]);

Stringクラスにもsplitメソッドがあるのでそっちを使ってもいいと思います。
違いはよく知らん。

で、ちょっとあるファイルの絶対パスをディレクトリの配列にしたいな、と思うことがあった。
例えば
　C:\hoge\hoge1\hoge2\hoge3\hage.txt
だったら、これを
　{C:, hoge, hoge1, hoge2, hoge3, hage.txt}
っていう文字列の配列にしたかったんです。

まぁ"\"で分割すればいいな。と思って以下のようなコードを書いたんです。