読者です 読者をやめる 読者になる 読者になる

inline_table ― ソースコードに ASCII テーブルを埋め込むための Python モジュール

Python 手慰み 計算機

inline_table という名前のソースコードに ASCII テーブルを埋め込むための Python モジュールを作ってみました。

GitHub - fjkz/inline_table: Python module for embedding text tables into source-code

以下のように reStructuredText で書かれたテーブルをソースコードに埋め込むことが出来ます。

>>> import inline_table
>>> t1 = inline_table.compile('''
...     === === ====
...      A   B   AB
...     === === ====
...      1   1  '1'
...      1   2  '2'
...      2   1  '2'
...      2   2  '4'
...     === === ====
...     ''')
>>> t1.select(A=1, B=2)
Tuple(A=1, B=2, AB='2')

if 文を並べるよりコンパクトで読みやすいと思うのですが、どうでしょう?

テーブルに値を渡すこともできます。関数なども渡せるので便利かと思います。

>>> t2 = inline_table.compile('''
...     === =====
...     key value
...     === =====
...      1   a
...      2   b
...     === =====
...     ''',
...     a='A', b='B')
>>> t2.select(key=1)
Tuple(key=1, value='A')

2017-02-18

条件式を書けるようにした。

>>> t = inline_table.compile('''
...     ======== =====
...     In(cond)  Out
...     ======== =====
...      I <  0    0
...      I >= 0    1
...     ======== =====
...     ''')
>>> t.select(In=-1)
Tuple(In=-1, Out=0)
>>> t.select(In=1)
Tuple(In=1, Out=1)

ソフトウェアの拡張と劣化

計算機 考察

デカルトの『方法序説』に面白いことが書いてあった:

たくさんの部品を寄せ集めて作り,いろいろな親方の手を渡ってきた作品は,多くの場合,一人だけで苦労して仕上げた作品ほどの完成度が見られない.たとえばよくあることだが,一人の建築家が請け負って作りあげた建物は,何人もの建築家が,もともと別の目的で建てられた古い壁を生かしながら修復につとめた建物よりも,壮麗で整然としている.同じく,はじめは城壁のある村落にすぎなかったのが時とともに大都市に発展していった古い町は,一人の技師が思い通りに平原に線引きした規則正しい城塞都市にくらべると,ふつうひどく不揃いだ.

400年前に言われたことだがこれはデカルトの時代に限った話ではなく,現代でも正しい.どの時代でも成り立つ普遍的な事実なのであろう.しばしばソフトウェアは建築に例えられるが,ソフトウェアでもデカルトが言っていることが成り立つ.一般に一人で組んだソフトウェアの方が,多くの人が拡張していったソフトウェアよりも完成度が高い.多くの人が手を加えれば加えるほど,ソフトウェアは醜いものになっていく.

手を入れる人の数が多いと設計の一貫性が保てなくなるからである.良いソフトウェアは設計が一貫している.設計が一貫していない乱雑なソフトウェアは悪いソフトウェアだ.たった一つの設計思想のもとに整然と組まれたソフトウェアは美しい.設計思想がないパッチワークのようなソフトウェアは美しくない.

ただし,手を加える人もソフトウェアを醜くしようと思って手を加えているわけではない.古い設計のままでは新しい要求を叶えられないから,仕方なく手を加えているのである.要求が一貫しているなら設計も一貫したものになるだろう.だが,要求は一貫したものではなく,時々に応じて変わっていく.変化する要求に応じて随時ソフトウェアを更新していけば,ひどい異臭を放つ代物になっていくのも仕方のないことだ.まして,一度書いたところは触ってはいけない・デグレードは絶対に許さないといった縛りがあるならば,なおのことである.古いコードは新陳代謝なしに残っていて,癌細胞のように拡張されるコードとのキメラを形成する.手を加えた人に対してコードを汚したと非難するのは酷だろう.

では,一切何にも手を触れなければソフトウェアが劣化しないかというと,そうでもない.ソフトウェア自体は変わらなくても,周囲の世界の方が変わっていくから,相対的にソフトウェアは劣化していく.陳腐化ともいう.ソフトウェアに対する要求というのは変わっていくので,手を加えなければ,要求を満たさなくなっていく.Windows 2000 でしか動かないアプリケーションがあったとしても,そんなものにはもはや価値はない.

ソフトウェアが劣化していくのは避けようがない.デカルトのように,すべてを一旦全否定して,全く新しく自分が信じられるものを作り上げると野心的なことが言えれば良いのだろうけれども,そういうわけにはいかないのだ.そのため,いかにしてソフトウェアの劣化を緩やかにして,ソフトウェアを延命させるかということが課題になる.

銀の弾丸はないのだけれども,効果的な方法というは知られている.次回はそれについて考えてみたい.

ttap: ファイルシステム階層によるテスティングフレームワーク

Python 手慰み 計算機

実行可能なテストスクリプト群のディレクトリ構成を定義して、整理するためのフレームワークを作りました。半年ほど前に作ってたやつです。*1塩漬け期間を経たのでリリースとします。

システムテストを自動化するときに使用することを想定しています。ユニットテストに関しては、便利なフレームワークが既に多くあるので、それらを使えばそれなりに整理された状態を保つことができます。しかし、システムテストに関しては、システム固有の処理があるので、フレームワーク化するのは難しいと思っています。シェルスクリプトなどを駆使して自動化テストを手組せざるを得ない。

しかしながら、スクリプト群は増え続けて混乱しがちなので、それらを整理できたらいいのにと思いました。そこで、スクリプト群のディレクトリ構成を定義するツールがあれば便利と思い、作成しました。ttap という名前です。

以下のように、スクリプト群は木構造に配置されます。

$ ttap --tree ./sample
sample
├── test-before-after
│   ├── before1.sh
│   ├── before2.sh
│   ├── test1.sh
│   ├── test2.sh
│   ├── after2.sh
│   └── after1.sh
├── test-init-final
│   ├── init1.sh
│   ├── init2.sh
│   ├── test1.sh
│   ├── test2.sh
│   ├── final2.sh
│   └── final1.sh
└── test-simple
    ├── test_not_ok.sh
    └── test_ok.sh

ttap はディレクトリ構成から、スクリプトの実行順序を計画し、実行します。

$ ttap --format tap ./sample
ok 1 test-before-after/before1.sh.1
ok 2 test-before-after/before2.sh.1
ok 3 test-before-after/test1.sh
ok 4 test-before-after/after2.sh.1
ok 5 test-before-after/after1.sh.1
ok 6 test-before-after/before1.sh.2
ok 7 test-before-after/before2.sh.2
ok 8 test-before-after/test2.sh
ok 9 test-before-after/after2.sh.2
ok 10 test-before-after/after1.sh.2
ok 11 test-init-final/init1.sh
ok 12 test-init-final/init2.sh
ok 13 test-init-final/test1.sh
ok 14 test-init-final/test2.sh
ok 15 test-init-final/final2.sh
ok 16 test-init-final/final1.sh
not ok 17 test-simple/test_not_ok.sh
ok 18 test-simple/test_ok.sh
1..18

スクリプト群が木構造に整理されることを強制するので、柔軟性は欠けるがその分、散らかりにくくなるだろうという寸法です。それぞれのスクリプトは、シェルスクリプトベタ書きでもいいですし、既存のフレームワークを使ってもいいです。既存のテスティングフレームワークよりも、もう少しメタなところを上手くすることを狙ったものです。

といった機能があります。

今回作った実装がいいかは分からないですが、コンセプトのアイデアはそんなに悪くないのではないかと思っています。よろしければ試してみてください。

『方法序説』を読んだ

所感 a.k.a. poem

デカルトの『方法序説』を読みました。昔読んだはずなのに全然覚えてなくて、びっくりした。

デカルトといえば『我思う故に我あり』の言葉で有名な昔の学者です。それ以外にもデカルトの影響は現代にも強く残っていて、ax + b = c というように、未知数を x, y, z, 既知数を a, b, c と置く中学生の時分に習う方程式の表記法は、デカルトが考案したものです。他には、平面上のある点を表すのに、x 座標、y 座標の値を用いて表す正規直交座標系もデカルトの発明です。

方法序説』は、有名な『我思う〜』が出てくるデカルト著作です。元は『理性を正しく導き、学問において真理を探求するための方法序説』という長いタイトルですが、略して『方法序説』という名で知られています。偉大な学者が、学問に取り組んだ際の方法論を語った文章です。タイトルがいかついですが、ただのエッセイです。女子供でも読めるようにラテン語ではなくてフランス語で書かれていて(私は古典フランス語は読めないので、日本語訳を読みましたが)、頭が湧いてくるような小難しいことも書かれていないです。

しかし、本書は偉大な学者の奥義の開陳であり、面白いことが書かれています。書かれていることは、現代の我々からしたら普通のことです。それはつまり、今日の学問はデカルトが語った方法論で行われているのです。当たり前を作ったというのは、人の業績の中で最も偉大なことです。当たり前になりすぎて意識しないような今日の常識がどこから始まったのかを知り、今日の常識を再考するというのは、私は面白いことだと思っています。

もちろん、この本を読んでも現代の問題の解は載ってないです。

自分の愛読する著書の中に(中略)著者が何も言っていない、おそらくけっして考えたことのないような、いくつもの難問の解決をそこに見出す

といった態度は本書でも批判されています。衒学ぶって、本書の内容を振りかざしてもそれだけでは役にはたたないので注意したい。問題の解決や真理に至る方法論は参考になるし、条件付きだが正しいことが書いていると思います。しかし、その方法でデカルトが得た答えは、昔の人の話なので現代では必ずしも正しくはないです。

さて、デカルトの方法というのは、以下の4つの規則に従えば確実な原理が得られるというものです。

  1. 『明証的に真であると認めるのでなければ、どんなことも真として受け入れないこと』
  2. 『検討する難問の一つ一つを、できるだけ多くの、しかも問題をよりよく解くために必要なだけの小部分に分割すること』
  3. 『思考を順序にしたがって導くこと』
  4. 『すべての場合に、完全な枚挙と全体にわたる見直しをして、なにも見落とさなかったと確信すること』

つまり、数学的な方法を一般化して適用するということです。科学の方法としては原始的ですが、蔑ろにはできない基本的な方法です。

しかし、上記のようなことを言っていたら何も進まないし、我々は不確実な日常を生きなければなりません。不確かな土台の上に日常がなりたっていたとしても、明日は来るのです。そこで、デカルトは生活の上の原則、つまり道徳として3つの格率を挙げています。

  1. 『わたしの国の法律と慣習に従うこと』
  2. 『自分の行動において、できるかぎり確固として果断であり、どんなに疑わしい意見でも、一度それに決めた以上は、きわめて確実な意見であるときに劣らず、一貫して従うこと』
  3. 『運命よりむしろ自分に打ち克つように、世界の秩序よりも自分の欲望を変えるように、つねに努めること』

デカルトの偉いところは、理性では確実な真理を追求しつつも、その裏で不確実な世界の中で幸福な生活を送ることもちゃんと考えているところです。私はこの点が本書で最も重要だと思いました。

方法序説 (岩波文庫)

方法序説 (岩波文庫)

無向ネットワークのリンクの結合度

ノート 手慰み

ネットワークサイエンスについて勉強している。

ノード間のリンクの結合の強さを表す尺度を思いついた。既に発見されているかもしれないが記録しておく。*1

仮説1: リンクに重みが予め付加されていない場合でも、ネットワークの構造からリンクの結合度を表すことができる。

重み付きネットワークであれば、どのリンクが重要かという問について悩む必要はない。大きい重みが付けられているリンクが重要なリンクであろう。もちろん何をもって重要とするかによって、どのリンクが重要かは変わってくるだろうが、(変な言葉だが)重みによってウェイトがつけられるのは間違いないだろう。

一方、リンクに重みが明に付加されていないネットワークであっても、すべてのリンクが等しく重要であるということはないだろう。重要なリンクもあればそうでないリンクもある。非重み付きネットワークであっても、リンクの重要度、言い換えると結合の強さというのが存在するはずだ。そして、それはネットワークの構造から計算できるに違いない。

ネットワークサイエンスを学んでいると、クラスタリング係数 (Transivity) というものが登場します。実在するネットワークは一般に、一部のノードが密にリンクを張っていて、クラスタを作っています。家族だとか、サークルだとか、互いに見知り合った集団のことです。コミュニティともモジュールとも呼び方はいろいろあるかと思います。クラスタリング係数はクラスタリングが起こっている度合いを示す指標です。

仮説2: クラスタ内のリンクは結合度が高い。

結合度、結びつきの強さを考えます。厳密な定義はまだできないですが、リンクの重みと同じイメージです。結合が強いリンクがあるところにクラスタができるのか、クラスタがあったらリンクが強くなるのかはわかりませんが、感覚的にクラスタ内の結合は強いと思われます。

クラスタを作るようなリンクは結合度が高いとすると、次の仮説が得られます。

仮説3: 共通のノードに接続している2つのノード間のリンクは結合度が高い。

共通の知り合いが多い二人組は強い関係にあるということです。例えば夫婦とかです。

f:id:fjkz:20161202215436p:plain

図の上と下のノードは4つの共通のノードにリンクしています。点線のリンクは強いリンクであると考えられます。

このような考え方で、リンクの結合度を表す値が定義できるのではないだろうか。そうすると、重みなしネットワークから、重みつきネットワークを生成できる。何かしら新しいものが見えてきそうだ。

だが、上のコンセプトの元でも、結合度の定義は幾通りも考えれる。単に共通のノードの数としてもいいし、次数を用いて [0, 1] の区間の値を持つように規格化してもいい。どのような定義が適切かはデータを元に決めるしかない。

仮説4: よいノードの結合度の定義は2つのノードが結合している確率と強い相関をもつ

結合度の強いリンクというのは生じやすくて、切れづらいと考えれる。任意の2つのノード間にリンクが貼られている確率が高い条件というものがあったとき、その条件下で結合している2つのノードは結合度が強いと言えるのではないだろうか。

例えば、上の図でいうと、2つのノードが共通にリンクを張っているノードの数と、その2つのノード間にリンクがある確率に強い相関があるとすれば、2つのノードが共通にリンクしているノードの数が2つのノード間の結合度を示していると言えるでしょう。

ただ、この考えでいくと、結合度はリンクがないノード間にも定義できなければならなくなる。統計値を得やすいという利点はあるが、そのように定義された結合度が適切なのかはよくわからない。

副作用として、確率的にそこにリンクがあって然るべきなのに、リンクがないという状況があれば、リコメンデーションに利用できるだろう。Facebook のもしかして友達?という通知はそういう戦略なのかもしられない。

以上、ただの思いつきです。気が向けば上記の方針で適切な結合度を探すことをしてみる。クラスの依存関係のグラフは有向グラフだからちょっと取り扱いにくい……。無向グラフで、ベンチマークがしやすいような適当なサンプルデータはないのだろうか?


追記 2016-12-03

Ahn, Bagrow, Hehmann の link-clustering algorithm のアイデアに似ている。こちらは2つのリンクの類似度というのを求めている。

Link communities reveal multiscale complexity in networks : Nature : Nature Research

*1:もし既存の研究を見つけたら後から追記します。似ているが、異なるものはありました。

クラスの依存関係グラフ 4

手慰み 計算機 ノート

Java および Scala のクラスの依存関係のグラフについて調べている。

今回はクラスタリング係数を見てみる。

クラスタリング係数とは、あるノードにリンクしたノード群が互いにリンクしている割合を表します。C で表します。ノードごとに値を持ち [0, 1] の範囲を取ります。あるノードで C=0 であれば、そのノードにリンクしているノード同士は互いにリンクしていなく、C=1 であれば、そのノードにリンクしているノード同士はすべてリンクしています。

f:id:fjkz:20161127005456p:plain

現実のグラフは全体としては非常に疎であるが、知り合いが共通しているような部分的に密となるようなクラスタを作っていることが知られています。Twitter とかで、○○クラスタに属している人と言いますが、あのクラスタです。このとき、クラスタリング係数は値を持つことになります。

Apache Spark が依存する 214 個の JAR パッケージに含まれるクラスの依存関係のグラフを対象とします。

クラスタリング係数の分布は以下の

平均値は C = 0.53 C = 0.46 でした。クラスの依存関係グラフはクラスタリング性を持っていると言えるでしょう。*1

次数とクラスタリング係数の関係の散布図を描いてみました。

入力次数とクラスタリング係数の関係です。k_in は入力次数です。

f:id:fjkz:20161127030859p:plain

出力次数とクラスタリング係数の関係です。k_out は出力次数です。

f:id:fjkz:20161127030905p:plain

入力次数の方はっきりと、k^-1 に比例するように分布しています。出力次数の方もそういう傾向が見えないこともないですが、あまり出力次数とクラスタリング係数に強い関係はなさそうです。

この結果の何が興味深いのかというと、ネットワークの模型のひとつである Hierarchical Network モデルでは C(k) ∝ k^-1 の関係が成り立ちということが知られています(Hierarchical Network モデルについてはいつかまとめる)。ソフトウェアモジュールの成り立ちを考えると、ソフトウェアモジュールの依存関係は Hierarchical Network モデルでうまく説明できそうだと予想できます。入力次数とクラスタリング係数の関係が Hierarchical Network モデルと一致しているという事実は、この仮説を支えていると言えるでしょう。

*1:graph_tool で計算したが、なんか結果が胡散臭い。別の小さな系について、gephi で計算したものと、graph_tool で計算したもので違う値となった。傾向は同じなので、議論には差し支えないと思う。gephi だと遅すぎて今回のようなエッヂが100万を超えるようなのものの計算ができない……どうしたものか。速くて、Python で使えて、安定しているツールはないのだろうか。

→ igraph で計算しなおした。C = 0.46 は igraph の値。igraph も nan になる結果が混じってたり、ちょっと怪しいけれど

クラスの依存関係グラフ 3

手慰み Java 計算機

Java および Scala のクラスの依存関係のグラフについて調べている。

驚くべきことに(まあ予想はしていたけれども)、クラス間の依存関係のグラフはスケールフリーネットワークの性質を持つことが明らかになりました。スケールフリーネットワークでは、ノードの次数がべき乗則に従います。

勉強しながら調べているので、次数の非常に大きいクラス、例えば java.lang.Object クラスの存在がべき乗則で現れうるクラスなのかべき乗則でも説明できないほど例外的に次数の大きいクラスか、よくわからないと前回・前々回に素人っぽい言及をしました。

プロットの仕方を工夫すると、次数が大きいところも綺麗に図がかけることがわかったので、今回は次数が大きいところでもべき乗則が成立しているかどうかを検証します。

f:id:fjkz:20161112185046p:plain

上は前回載せた図で、次数の分布を示しています。これは、Bin の幅が 1 のヒストグラムです。次数が大きいところはサンプルが少ないのでガタガタになっていてべき乗則なのかどうかよく分からなくなっています。

そこで、Bin の幅を 1 に固定せずに、対数プロットしたときに Bin の幅が同じにやるようなヒストグラムを書きます。つまり、1 つめの Bin は次数が 1 のノードの割合、2 つめの Bin は次数が 2 か 3 のノードの値、3 つめは 4, 5, 6, 7 のいずれか、N つめは log2(N-1) から log2(N)-1 となります。

上のような Log-Bin で書いたヒストグラムが下の図です。

f:id:fjkz:20161123191256p:plain

次数が高いところは前の図ではが省きました、Log-Bin で描くと次数が高いところまでグラフに含められるようになりました。

入力次数は、次数が大きいところまで、きれいなべき分布になっていることが分かります。次数が 10^5 といった非常に大きな値を持つノードは、java.lang.Object クラスなのですが、この存在もべき乗則に従うことが分かりました。

出力次数は、次数が小さいところはよくわからない分布をしていますが、次数が大きいとべき乗則っぽい分布になっています。

積分布を描いても、次数の高いところが上手く表現できます。

下の2つの図は、次数 k に対して、次数が k を超えるノードの割合を示しています。上の図が入力次数、下の図が出力次数です。*1

f:id:fjkz:20161123192131p:plain f:id:fjkz:20161123192136p:plain

Log-Bin だとプロットの数が減るのでデータが丸められてしまっている不安がありますが、累積分布ではプロットの数は減りません。

さて、入力次数の方に関しては、きれいなべき乗則になっています。グラフの傾きは -1 です。累積分布の場合は傾きは べき指数 + 1 になります。累積なのに、k が小さいところの P が 1 になっていませんが、それは k = 0 のノードがいるからです。また、ヒストグラムを描いたときには気付かなかったが、次数が 10 以下のところで傾きが少し緩くなっています。べき乗則に従うと言われるデータは一般的にこうなっています。次数が大きいところはちょっとガタガタっとなっていますが、k = 10^4 に何か意味があるとは思えないので、ノイズでしょう。

出力次数の方が、k = 30 から k = 200 まではべき乗則に従っています。k が小さいところは謎の分布なのは、Log-Bin の図の方が分かりやすいです。

出力次数の次数が大きいところは、ガタガタしてわかりづらいが、グラフの傾きが急になっているようにも見えます。ソフトウェアを作る視点で考えると、出力次数は、ソースコードを書く人間が決めることで、あまりに依存先が多いクラスというのは作らないものなので、上限値があることが予想されます。べき乗則に従うということはサンプル数を増やせば、想像を絶する巨大なクラスが現れるということを意味していますが、おそらくありえないでしょう。10^3 のオーダーが上限なのではないかと推測されます。このことに関しては、ソフトウェア特有の現象なので、もう少し調べる価値がありそうです。

今はべき指数は目分量で見ているので、次回は定量的にべき指数を計算してみようと思う。

参考

Network Science

Network Science

*1:積分布の図は matplotlib で描きました。他の図は gnuplot で描いています。gnuplot が慣れているので、なんとなく guplot を使っていましたが、 matplotlib の方が使いやすいですね。