tag:blogger.com,1999:blog-76689403949325866772024-02-20T18:54:10.237+09:00さむしんぐあずあめも。何も目指さないメモ的な何か。Anonymoushttp://www.blogger.com/profile/17682850078090291459noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-7668940394932586677.post-24498566550950129192012-03-03T23:30:00.000+09:002012-03-03T23:38:02.715+09:00HomebrewでインストールしたJenkinsのHTTP listen portを変更する方法Homebrewでインストールする方法自体は<a href="http://www29204u.sakura.ne.jp/?p=44" target="_blank">このあたり</a>を参考に。<br />
<span style="font-family: Verdana, sans-serif;">~/Library/LaunchAgents/</span>にコピーした<span style="font-family: Verdana, sans-serif;">homebrew.mxcl.jenkins.plist</span>ファイルの中を見るとこんな感じになっている。<br />
<br />
<script src="https://gist.github.com/1966344.js?file=%E4%BF%AE%E6%AD%A3%E5%89%8D.xml">
</script>
<br />
<span style="font-family: Verdana, sans-serif;">jenkins.war</span>を<span style="font-family: Verdana, sans-serif;">-jar</span>オプションで起動しているので、これは<a href="http://winstone.sourceforge.net/" target="_blank">Winstone</a>をサーブレットコンテナとして動作している。なので、Winstoneの起動オプションを追加すればそれを読み取ってくれるようだ。以下はlisten portの変更を変更するオプションを追加したもの。<br />
<br />
<script src="https://gist.github.com/1966344.js?file=%E4%BF%AE%E6%AD%A3%E5%BE%8C.xml">
</script>
<br />
別途試していたScalatraが先に8080を使っていたので、とりあえず18080に引っ越してもらった。<br />
<br />
変更はプロセスの再起動後に反映される。<br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">launchctl unload ~/Library/LaunchAgents/homebrew.mxcl.jenkins.plist</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">launchctl load ~/Library/LaunchAgents/homebrew.mxcl.jenkins.plist</span><br />
<br />
本格運用するには不十分だろうが、とりあえず試してみるにはこれで十分かと。Anonymoushttp://www.blogger.com/profile/17682850078090291459noreply@blogger.com0tag:blogger.com,1999:blog-7668940394932586677.post-10505238710058340642012-02-28T12:53:00.000+09:002012-02-28T12:53:26.624+09:00mapBetween関数Scala版 その4(完結編)<a href="http://con-leche.blogspot.com/2012/02/mapbetweenscala-3.html">昨日のポスト</a>のコードに対して、<a href="https://twitter.com/#!/gakuzzzz" target="_blank">がくぞ</a>さんからまさにそれが欲しかったという修正を頂いたので掲載。<br />
<br />
<script src="https://gist.github.com/1929182.js?file=mapBetween.scala">
</script><br />
<br />
traitとして別途宣言せず、mapBetween関数が追加された無名クラスのインスタンスを返すようにimplicit conversionを定義する。(3〜7行目)<br />
Seqのサブクラスとして何が来ようと、そのクラスを拡張した形で無名クラスが定義されるため、返り値がmutableになってしまうこともない。何より大変シンプルになってわかりやすい。<br />
<br />
今度のseqToExtSeq関数の返り値は無名クラスのインスタンスになるため、返り値の型を明示できない。そのためか、main関数の後に定義すると、以下のようなエラーが出てコンパイル出来なかった。<br />
<br />
<blockquote class="tr_bq">
value mapBetween is not a member of scala.collection.immutable.Range.Inclusive Note: implicit method seqToExtSeq is not applicable here because it comes after the application point and it lacks an explicit result type<span class="Apple-tab-span" style="white-space: pre;"> </span>mapBetween.scala</blockquote>
<div>
順番が入れ替わっているのはそのため。<br />
<br />
とりあえず最初の手習いとしてはこれくらいにして、次は別のことをやってみる。</div>Anonymoushttp://www.blogger.com/profile/17682850078090291459noreply@blogger.com0tag:blogger.com,1999:blog-7668940394932586677.post-22959749528893304712012-02-27T21:45:00.000+09:002012-02-27T21:45:01.336+09:00mapBetween関数Scala版 その3<a href="http://con-leche.blogspot.com/2012/02/mapbetweenscala-2.html">前回</a>で関数の実装はまともになったので、クラスを拡張する方向に検討をしてみる。<br />
<br />
<script src="https://gist.github.com/1923244.js?file=mapBetween.scala">
</script>
<br />
とりあえずmapBetween関数をtraitにして分離。(20〜24行目)<br />
前回までは、型パラメタAを下限とする型パラメタTを関数の引数の型としていたが、traitにしたことでまたうまく関数の型推論ができなくなってかえって使いにくいため、Aそのものを引数の型に変更した。匿名関数が手軽に定義できる以上、JavaのComparatorのような問題は起きないと思って良いのかもしれない。<br />
<br />
使う際にはSeqのサブクラスをnewする時にwith ExtSeq[A]でtraitをミックスインする(3行目)ことで、mapBetween関数を呼び出すことができるようになる。(4〜6行目)<br />
ミックスインできるのはインスタンス化するときなので、生成されたインスタンスを返すRichIntクラスのtoメソッドは使えない。Rangeクラスのコンストラクタはfrom, to, stepの3つの引数を必ず要求するため、ちょっと使いにくい。<br />
<br />
そこで、Seqのサブクラスのインスタンスを trait ExtSeqをミックスインしたクラスのインスタンスに変換する、暗黙の型変換を行う関数を定義する。(14〜17行目)<br />
<br />
この暗黙の型変換は、mapBetweenオブジェクトのスコープ内で有効なため、Rangeクラスのインスタンスを普通に生成(8行目)しても、そのインスタンスに対してmapBetween関数を呼び出そうとすることで、コンパイル時に暗黙的にseqToExtSeq関数の呼び出しが加えられる。それによって、あたかもRangeクラスに元々mapBetween関数が定義されていたかのように見える。(9〜12行目)<br />
<br />
このseqToExtSeq関数を定義する際に注意することは、返り値をExtSeqにしなければならないのを誤ってSeqのインスタンスを返すように実装(例えば++=の代わりに++を呼んでしまった等)しても、コンパイルが通ってしまうことだ。そうした場合、実行時にseqToExtSeq関数が呼び出されると、Seqのインスタンスを本来の返り値の型であるExtSeqに暗黙的に変換しようとして、自分を再帰的に呼び出してしまい、無限ループに陥る。しかもタチの悪いことに、末尾最適化されてしまってスタックがオーバフローしないため、ただダンマリになってしまってしばらく何が起きたのかわからなかった。実装時はimplicit修飾子を付けないで実装して、後から修飾子を付けたほうが間違いが起こりにくいかも。<br />
<br />
ところで、immutableなパッケージでミックスインできるクラスが見つけられなかったためやむを得ずArrayBufferを使ってしまったが、このままでは暗黙の型変換をした後のインスタンスがmutableになってしまう。ココは改善する必要があるのだが、とりあえずノーアイディア。Anonymoushttp://www.blogger.com/profile/17682850078090291459noreply@blogger.com0tag:blogger.com,1999:blog-7668940394932586677.post-5406589508042804432012-02-24T11:55:00.000+09:002012-02-24T11:59:55.510+09:00mapBetween関数Scala版 その2<a href="http://con-leche.blogspot.com/2012/01/mapbetweenscala.html">前回</a>のコードを<a href="http://scala-users.org/shibuya/index.php?title=%E3%83%A1%E3%82%A4%E3%83%B3%E3%83%9A%E3%83%BC%E3%82%B8" target="_blank">rpscala</a>の方々に見て頂いたところ、「それ、slidingでできるよ!」と教えていただいたので修正。<br />
<br />
<script src="https://gist.github.com/1896735.js">
</script>
<br />
sliding関数は引数で指定された個数を1つのブロックとして、sliding windowを提供する。例えばSeq(1,2,3,4)に対してsliding(2)を呼び出すと、Seq(1,2),Seq(2,3),Seq(3,4)と返すIteratorが返される。sliding(3)ならSeq(1,2,3),Seq(2,3,4)となる。<br />
これはmapBetween関数でやりたいことほぼそのものなので、結果としてえらいシンプルになってしまった。<br />
<br />
前回適用する関数に対して型推論が効かないと愚痴ったが、これはカリー化することで対応できることを教えてもらった。カリー化前だと型パラメタAとTを同時に推論しなければならず、それが上手くいかない原因だった模様。カリー化することで先に型Aが決定するため、型Tが上手く推論できるようになるらしい。嘘かも。型推論はもうちょっとまともに勉強したいなぁ。。。Anonymoushttp://www.blogger.com/profile/17682850078090291459noreply@blogger.com0tag:blogger.com,1999:blog-7668940394932586677.post-80980135338037950562012-01-27T12:26:00.000+09:002012-01-27T12:44:12.097+09:00mapBetween関数Scala版dankogai先生の投稿 <a href="http://blog.livedoor.jp/dankogai/archives/51763038.html" target="_blank">algorithm - mapBetween - 配列の隣接する2項にそれぞれ演算を施した配列</a> にあるmapBetween関数をScalaで書いてみる。<br />
クラスを拡張する形で書きたかったのだが、いっぺんにやろうとするときっとこんがらがるのでとりあえずSeqを引数で受ける形で実装。<br />
<br />
<script src="https://gist.github.com/1686712.js?file=MapBetween.scala">
</script>
<br />
とりあえず動くけど、果たして効率の良い実装になっているのか。。。<br />
隣り合う2項に適用する関数のパラメタに、型を指定しなければコンパイルが通らない。第1引数Seqの型パラメタから推論して欲しいところだけどどうもそうはならないみたい。<br />
foldLeftの左項のタプルの1つめの要素で、Seq[B]()の代わりにNilを指定したかったのだが、型の不一致でこれもまたコンパイルが通らない。まぁこちらはなんとなく仕方がない気がする。Anonymoushttp://www.blogger.com/profile/17682850078090291459noreply@blogger.com0tag:blogger.com,1999:blog-7668940394932586677.post-41549322453061407912011-01-25T18:06:00.000+09:002011-01-25T18:06:06.710+09:00topコマンドのログ解析(Python手習い) その2その後OrderedDictというクラスがcollectionsモジュールにあることが判明したため、これを使ってもうちょっとマシなファイルハンドル操作を実装してみた。<br />
<br />
ついでにファイルオープン時に致命的なバグがあったため、合わせて修正。<br />
<br />
<pre class="brush:python">from collections import OrderedDict
from datetime import datetime, timedelta
from functools import reduce
from os.path import exists
from re import match, search, split
from sys import argv
from shutil import rmtree
from os import makedirs
MAX_FILE_HANDLE = 500
WORK_DIR = 'work'
if len(argv) != 3:
print("\nUsage:\npython", argv[0], "logfile yyyy/mm/dd")
exit()
rmtree(WORK_DIR, True)
if not exists(WORK_DIR):
makedirs(WORK_DIR)
mydate = datetime.strptime(argv[2], '%Y/%m/%d')
mydateStr = mydate.strftime('%Y/%m/%d ')
try:
f = open(argv[1])
mem = open(WORK_DIR + "/mem.log", 'w')
mem.write("time,mem av,mem used,mem free,mem shard,mem buff,mem actv, mem in_d,swap av,swap used,swap free,swap cached\n")
processes = OrderedDict()
maxtime = ""
for line in f:
line = line.strip()
if match(r"^\d\d:\d\d:\d\d", line):
if line[0:2] == "00" and timestamp[0:2] != "00":
mydate = mydate + timedelta(1)
mydateStr = mydate.strftime('%Y/%m/%d ')
timestamp = line[0:8]
elif match(r"^Mem", line):
data = split(r"\s+", line)[1:9:2]
elif match(r"^\d+k", line):
data = data + split(r"\s+", line)[0:5:2]
elif match(r"^Swap:", line):
data = data + split(r"\s+", line)[1:8:2]
prefix = mydateStr + timestamp
result = reduce((lambda x,y: x + ',' + y.rstrip('k')), data, prefix)
mem.write(result + "\n")
elif search(r"java", line):
data = split(r"\s+", line)
pid = data[0]
process = processes.get(pid)
if process == None:
while len(processes) >= MAX_FILE_HANDLE:
processes.popitem(last=False)[1].close()
filename = WORK_DIR + "/Pid-" + pid + ".log"
if exists(filename):
process = open(filename, 'a')
else:
process = open(filename, 'w')
process.write("time,PID,USER,PRI,NI,SIZE,RSS,SHARE,STAT,%CPU,%MEM,TIME,CPU,COMMAND\n")
else:
del processes[pid]
processes[pid] = process
prefix = mydateStr + timestamp
result = reduce((lambda x,y: x + ',' + y), data, prefix)
process.write(result + "\n")
if data[10] > maxtime:
maxtime = data[10]
maxpid = pid
print("maxpid:", maxpid)
finally:
if f != None:
f.close()
if mem != None:
mem.close()
map(lambda x: x.close(), processes)
</pre><br />
キモは51~63行あたり。<br />
<br />
OrderedDictは名が示すとおり、(key, value)セットの追加順序を記憶する辞書型である。ただし、一度追加した(key, value)は、valueの更新が行われても順序を入れ替えない。今回はLRUを実装しなければならないため、既に追加されている(key, value)にアクセスした場合は必ず一度削除してから再度追加するようにしている。<br />
<br />
さらに、もし管理しているファイルハンドルがMAX_FILE_HANDLEを超えそうになったら、一番使われていないファイルハンドルを取得しクローズ処理を行なっている(54行目)。popitemメソッドは、引数がtrueの場合はLIFO、falseの場合はFIFOとして動作する。<br />
<br />
前回バグっていたのを直したのは56~60行目あたり。前回はopen関数の第2引数を常に'w'と指定していたため、ファイルハンドルが増えたために一旦クローズしてしまったファイルについて、再度書きこみを行おうとした場合にクローズ前までのデータを消してしまっていた。オープン時にファイルが存在する場合は追記('a')するように修正。<br />
<br />
150MB程度のログファイルの処理に、僕の非常に非力なマシン(PentiumM 1.2GHz 752MB RAM)で約2分。生成されるファイル数は4,000あまりというところ。<br />
<br />
時間があったら、次はもう少しモジュール化してみたい。Anonymoushttp://www.blogger.com/profile/17682850078090291459noreply@blogger.com0tag:blogger.com,1999:blog-7668940394932586677.post-36889010762936493022011-01-24T12:04:00.001+09:002011-01-24T12:07:18.693+09:00topコマンドのログ解析(Python手習い)topコマンドのログをExcelでグラフ化できるようにCSV形式に変換するPythonスクリプトを書いてみた。とりあえず動いたが、色々知らないまま書いているのでたぶんもっと良い書き方があるはず。<br />
<br />
JavaのPID毎に別ファイルに出力するようにしたかったのだが、Windows上では500個ちょっとオープンしたところで"Too Many Open Files"エラーが出たため、500を超えたら一旦すべてクローズするように暫定対処した。できれば参照の少ないファイルから先にクローズしていくようにしたい。Javaで言うところのLinkedHashMapみたいなものは無いのだろうか。<br />
<br />
スクリプト言語としてはずいぶん昔にPerlを触った以来だが、やっつけで書きやすい割にPerlよりは可読性が高いように感じる。<br />
<br />
<pre class="brush:python">import sys
import re
from datetime import datetime, timedelta
from functools import reduce
if len(sys.argv) != 3 :
print("\nUsage:\npython", sys.argv[0], "logfile yyyy/mm/dd")
exit()
mydate = datetime.strptime(sys.argv[2], '%Y/%m/%d')
mydateStr = mydate.strftime('%Y/%m/%d ')
try :
f = open(sys.argv[1])
mem = open("mem.log", 'w')
mem.write("time,mem av,mem used,mem free,mem shard,mem buff,mem actv, mem in_d,swap av,swap used,swap free,swap cached\n")
processes = {}
maxtime = ""
for line in f :
line = line.strip()
if re.match(r"^\d\d:\d\d:\d\d", line) :
if line[0:2] == "00" and timestamp[0:2] != "00" :
mydate = mydate + timedelta(1)
mydateStr = mydate.strftime('%Y/%m/%d ')
timestamp = line[0:8]
elif re.match(r"^Mem", line) :
data = re.split(r"\s+", line)[1:9:2]
elif re.match(r"^\d+k", line) :
data = data + re.split(r"\s+", line)[0:5:2]
elif re.match(r"^Swap:", line) :
data = data + re.split(r"\s+", line)[1:8:2]
prefix = mydateStr + timestamp
result = reduce((lambda x,y: x + ',' + y.rstrip('k')), data, prefix)
mem.write(result + "\n")
elif re.search(r"java", line) :
data = re.split(r"\s+", line)
if data[0] not in processes :
processes[data[0]] = open("Pid-" + data[0] + ".log", 'w')
processes[data[0]].write("time,PID,USER,PRI,NI,SIZE,RSS,SHARE,STAT,%CPU,%MEM,TIME,CPU,COMMAND\n")
prefix = mydateStr + timestamp
result = reduce((lambda x,y: x + ',' + y), data, prefix)
processes[data[0]].write(result + "\n")
if data[10] > maxtime :
maxtime = data[10]
maxpid = data[0]
if len(processes) > 500 :
map(lambda x: x.close(), processes)
processes = {}
print("maxpid:", maxpid)
finally :
if f != None :
f.close()
if mem != None :
mem.close()
map(lambda x: x.close(), processes)
</pre>Anonymoushttp://www.blogger.com/profile/17682850078090291459noreply@blogger.com0tag:blogger.com,1999:blog-7668940394932586677.post-26610451835653061072010-08-17T20:47:00.003+09:002010-08-17T23:54:38.752+09:00コーディングイディオムの奇妙な慣習先日仕事で緊急に、他人の作ったVisual Basicのコードを改修するタスクを受け持った。<br />
<br />
恥ずかしながら、VBは人生初だったが、Visual Studio様とGoogle様のお力でなんとか凌いだ。確かに言語としての敷居は低い。出だしの瞬間的な生産性はかなり高めだ。静止摩擦係数が低いという感じか。静的に型宣言を要求されるため、Java使いには意外と馴染む。ただ、互換性維持のためなのだろうが、同じことを実現するための関数の系統がいくつもあって、どれを選択すべきなのかわからないことが多かった。MSDNを真面目に読めば書いてあるのかもしれないが。<br />
<br />
元のコードは典型的な要リファクタリングコードだった。マーチンファウラー先生曰く「臭う」箇所があまりに多くて鼻が麻痺しそうだった。処理はいくつかの関数に分けられていたが基本的に一本道であり、同じ処理がコードのあちこちに何度も出てくる。やたらとグローバル変数が宣言されている。ローカル変数のスコープが無意味に広い。if文のネストが尋常じゃなく深い。そして何よりも、テストコードが一切存在しなかった、いわゆる「レガシーコード」だ。<br />
<br />
いろいろ手をつけたかったが、最終的に断念した。期間があまりに短かった上、仕様が毎日どころか数時間毎に変更されていくためだ。修正箇所を極力限定的にし、テストの項目数を極小にしなければ、どう考えても納期に間に合わなかった。直したくて直したくてウズウズする気持ちを抑えて、最小限の修正で実装を終えた。<br />
<br />
結果、バグを作りこんでしまった。テストが甘かったといえばそれまでなのだが、初めから自分が書いていれば発生するはずのない類のバグだった。今回はあまりに酷い例だったが、経験上意外とこういうコードを書く人が多く見られるため、自戒も込めてメモを残しておく。<br />
<br />
<br />
<span class="Apple-style-span" style="font-size: x-large;">1. ローカル変数の宣言箇所</span><br />
<br />
これは本当に奇妙なのだが、変数の宣言をサブルーチンの先頭にまとめて行うコードを大変よく見かける。正直メリットを一切思いつかない。ひょっとすると、Cのようなガベージコレクタを持たない言語では、領域を確保した後に開放するのを忘れないようにするために、チェックする箇所を限定するという目的があるのかもしれない。しかしほとんどのローカル変数は対象外だし、Javaを含めてGCを持つ言語では百害あって一利もない。典型的な害は以下のような例だ。<br />
<br />
<pre class="brush:java">String var = null;
for (...) {
if (...) {
var = "foo";
}
System.out.println(var);
}</pre><br />
for文の中でしか利用しないにも関わらず、先頭で予め宣言したために変数varがfor文の外のスコープを汚染している。もっと問題なのは、変数varの値がループの1つ前の処理に依存していることだ。上記の例の場合、forループの初回はif文の条件に合致した場合、varの値は"foo"になるが、合致しなかった場合は宣言時に代入したnullになる。2回目もif文の条件に合致した場合は同じく"foo"になるが、合致しなかった場合は初回の結果に依存する。<br />
<br />
要するにfor文中の条件分岐のいずれかのルートで、varの代入を忘れると嘘の値になるという厄介なバグを作ることになる。今回僕が作りこんだバグはコレだ。正しく動作させるためには以下のようにする必要がある。<br />
<br />
<pre class="brush:java">String var;
for (...) {
if (...) {
var = "foo";
} else {
var = "bar";
}
System.out.println(var);
}</pre><br />
このような単純な例で見落とす可能性は低いが、このfor文の中の処理が長くなり、分岐が複雑多岐にわたるようになれば徐々に見落としが発生する可能性が増す。また、代入を忘れた場合もなんらかの値が入っているため、たまたま前ループで正しい値が代入されることでテストを通過してしまう可能性が高い。<br />
<br />
このような見落としがそもそも発生しないようにすることは簡単で、以下のようにすれば良い。<br />
<br />
<pre class="brush:java">for (...) {
String var;
if (...) {
var = "foo";
} else {
var = "bar";
}
System.out.println(var);
}</pre><br />
変数varをfor文の中で宣言するだけだ。変数がforループ中、毎回宣言し直されるため、前回の値が誤って代入されることは絶対にない。昔はループのたびに変数宣言が行われることによるパフォーマンスの劣化を懸念するような意見があったが、ハードウェアのスペックが十分高くなった現在では、パフォーマンス劣化の危険性がバグを作り込む危険性に吊り合わない。そもそも、現在のJava VMでは上記のように都度宣言する記述を行っても、コンパイラの最適化によってforループの外で宣言する形に修正されるため、パフォーマンスの劣化自体が発生しない。そしてコンパイラが自動的に実行する最適化は、人が都度あれこれ気を使って行う最適化よりも概ね正確で効果的だ。変数は常に最小のスコープで、使うときに宣言すべきだ。<br />
<br />
<span class="Apple-style-span" style="font-size: x-large;">2. 無意味な変数初期化</span><br />
<br />
1.で挙げた修正後のコードを、以下のように書く人もよく見かける。<br />
<br />
<pre class="brush:java">for (...) {
String var = "bar";
if (...) {
var = "foo";
}
System.out.println(var);
}</pre><br />
こちらについては、必ずしもマズいとは言い切れ無い。特に上記のような単純な場合はコード量を減らす効果がある。しかし、僕はこのような書き方はあまり好きじゃない(そもそも上記のような単純な例なら、三項演算子を使えという話になってしまうがそれは置いておいて)。なぜなら上記の場合、if文の条件に合致するときに変数varの値は一旦"bar"によって初期化され、その後"foo"という値になる。この動作は非常に奇妙に感じる。もっと極端な例では以下のようなコードも見たことがある。<br />
<br />
<pre class="brush:java">for (...) {
String var = "";
if (...) {
var = "foo";
} else {
var = "bar";
}
System.out.println(var);
}</pre><br />
変数varを宣言した際に、「とりあえず」空文字で初期化しておくのだ。この空文字が実際に使われることは一度もない。空文字の代わりにnullでも同じことだ。宣言時に即初期化しろという強迫観念のようなものが存在するのだろうか。<br />
<br />
このような記述は、コンパイラが持っている折角のチェック機構をひとつ潰すことになる。初期化を行わなかった場合、例えば以下のように記述すると、コンパイル時にエラーが発生する。<br />
<br />
<pre class="brush:java">for (...) {
String var;
if (...) {
var = "foo";
}
System.out.println(var);
}</pre><br />
なぜなら、if文の条件に合致しなかった場合に変数varの初期化が行われないため、後でvarを参照しようとしたときに困ってしまうからだ。else文でvarに明示的に値を代入しない限り、コンパイルは通らない。<br />
<br />
このような単純な例では恩恵が得られないように感じるかもしれないが、分岐が複雑になっていけばこれに救われる可能性が高くなってくる。ある分岐で、うっかりvarへの代入を忘れてしまったとき、とりあえずvarの初期化をしてしまっていると、そのとりあえずの値が採用されてしまい、コンパイル自体は通ってしまう。その分岐ルートをテストしなければ、間違いに気づかない。最悪、とりあえずの値が期待する値とたまたま一致していると、バグに気づかないことになる。宣言時に初期化を行わなければ、すべてのルートで代入が行われていない限りコンパイル自体が通らない。<br />
<br />
<br />
結局、1と2両方を心がけることで、作りこんでしまったバグをコンパイラが見つけてくれる。これを利用しない手はない。もしコーディング規約等でこれらの奇妙な慣習が義務付けられているのであれば、規約自体の見直しを行う時が来たということになるだろう。Anonymoushttp://www.blogger.com/profile/17682850078090291459noreply@blogger.com0tag:blogger.com,1999:blog-7668940394932586677.post-73389182344338041722010-08-04T09:47:00.000+09:002010-08-04T09:47:56.873+09:00クラッカー?日頃から常時iPhoneのネット接続に使っているイー・モバイルのポケットWiFiなのだが、<br />
なんか会社にいるときにふと見ると接続数のカウントがおかしい。1個多いのだ。<br />
変だなーと思って管理画面で調べてみたら、やっぱり僕の知らない接続がある。<br />
管理画面に表示されたMACアドレスが00:24:D6で始まっているので、どうやら<br />
Intel製の無線LANのようだ。たぶん普通のWindowsPCなんだろう。 <br />
<br />
昔オープンで使っていたら、知らない人に勝手に常時使われていたので<br />
一応暗号化は設定している。WPA/WPA2で暗号化方式はTKIP+AES。<br />
まぁキーが割と短いので総当りされた可能性はあるのだが、<br />
辞書に載っているような単語ではなかったので、かなり意図的な侵入の模様。<br />
そういえば最近WPAのクラック方法が発見されたというのがニュースに<br />
なってたなぁと思って調べてみたらあった。<br />
<br />
<a href="http://www.itmedia.co.jp/news/articles/0811/11/news083.html">http://www.itmedia.co.jp/news/articles/0811/11/news083.html</a><br />
<br />
WPAでTKIPの時にクラッキングできるのか?<br />
んー、でもこれは偽のパケットを挿入できるけれども傍受できるわけではない<br />
ようだなぁ。やっぱり総当りだったのか?まだ1ヶ月も経ってないのに。。。<br />
<br />
基本的にはiPhoneしかつないでないから今回は良いんだけど、<br />
パケット見られてたわけだよね。気持ち悪いなぁ。<br />
とりあえずSSIDを変えてステルスモードにし、WPA2 AESのみを受け付けるように<br />
設定を変更した。さらにパスワードを長いものに変更。<br />
MACアドレスフィルターも設定した。これでしばらく様子見。<br />
これでもダメだったらどうしよう?もう打つ手が無い。<br />
<br />
ちなみにiPhoneがSSIDステルス時に自動接続に対応していないと<br />
思って公開していたのだが、調べてみたらどうやら対応している模様。<br />
公開状態の時に一度でも接続してしまうと、ステルス化したときに自動接続<br />
してくれなくなるようだ。初めからステルス状態だとちゃんと探してくれる。<br />
<br />
それにしても、意図的にWiFiデータを傍受するのは犯罪じゃなかったっけ?<br />
ついこの間ドイツでGoogleのストリートビューカーが無線データを記録していて<br />
大問題になっていたような。よしんば偶然ハッキングできたからと言ってそれを<br />
使い続けるのはどう考えても非常識だと思う。<br />
<br />
・・・問題は、どうやら、犯人が、社内にいるようなんだよね。。。<br />
勤続10年ちょい。これまでに社員に盗まれたものの一覧。<br />
<br />
・傘<br />
・ノートPCのACアダプタ<br />
・WiFi パスワード<br />
<br />
どれも他人の物だとはっきり分かっていて犯行に及んでいるところが<br />
タチが悪いなぁ。しかもだんだんエスカレートしてる。<br />
次は現金かなぁ。現金に手を出されたら、さすがにオー人事 オー人事かなぁ。。。Anonymoushttp://www.blogger.com/profile/17682850078090291459noreply@blogger.com4tag:blogger.com,1999:blog-7668940394932586677.post-34673411146194113382010-05-10T16:04:00.009+09:002010-08-04T19:30:03.914+09:00ジェネリックスと可変長引数の微妙な関係Javaのジェネリックス(総称)は、利用することはあってもAPIとして公開することはあまりなかったためこれまで気づかなかったが、可変長引数と組み合わせた場合に少々面倒な問題を持っていることに気づいたのでメモしておく。<br />
<br />
JDK5でさまざまな新機能が追加されたが、ジェネリックスはその1つ。<br />
一言で言ってしまえば、クラスやインタフェース、メソッドに型をパラメタとして定義できる機能である。<br />
具体的な例とメリットはCollectionフレームワークでしばしば説明されている。<br />
<br />
java.util.List<E><e>の例を以下に示す。<br />
JDK5以前のコードは以下のような感じになる。<br />
<br />
</e><br />
<pre class="brush:java">public void processMyClasses(List list) {
for (Iterator iter = list.iterator(); iter.hasNext(); ) {
MyClass myClass = (MyClass) iter.next();
// myClass に対して何か処理
}
}</pre><br />
for文の中で、MyClassへの明示的なキャストを行っている。<br />
list引数の要素がすべてMyClassにキャストできるオブジェクトであることを期待して実装しているが、もし誤った要素が入っていれば、キャスト時にClassCastExceptionが発生してしまう。<br />
このバグはコンパイル時には発覚しない。実行して初めて(最悪の場合バグにヒットする処理が行われるまでかなりの時間が経ってから)問題があることが判明する。<br />
例外はここで発生するが、バグを作り込んだ箇所(おかしな要素をaddしたところ)は別の場所であり、デバッグがやっかいになる。<br />
もちろん例外が発生しないようにinstanceof演算子で型チェックすることができるが、冗長であり、可読性を下げることになる。またデバッグが困難であることに変わりはない。<br />
<br />
JDK5以降は、同じ処理を以下のように記述できる。<br />
<br />
<pre class="brush:java">public void processMyClasses(List<MyClass> list) {
for (Iterator<MyClass> iter = list.iterator(); iter.hasNext(); ) {
MyClass myClass = iter.next();
// myClass に対して何か処理
}
}</pre><br />
for文の中でMyClassへの明示的なキャストが必要なくなっているのがミソだ。型パラメタを指定することで、その型以外の要素がリストに含まれないことがコンパイル時に保証される。<br />
<br />
さらに、型パラメタを指定することで、同じくJDK5で導入された拡張for文を利用することができるようになる。<br />
<br />
<pre class="brush:java">public void processMyClasses(List<MyClass> list) {
for (MyClass myClass : list) {
// myClass に対して何か処理
}
}</pre><br />
型パラメタを指定しないList(原型)を使用すると、拡張for文の左側の型はMyClassではなくObjectでしか宣言できなくなる。<br />
後で明示的にキャストしなければMyClassのメソッドを使用することができない。<br />
バグ等による型保証の問題についても、通常のfor文と同様である。<br />
<br />
このようなList<E>の特徴は、型Eの配列(E[])と非常に似ている。しかし、ジェネリックスと配列では、2つの点で大きく異なる。<br />
<br />
1つはジェネリックスはerasureで実装されているという点である。つまりジェネリックスによる型チェックはコンパイル時に行われ、その後抹消される。コンパイルされた後のバイトコードにはその情報は残らない。これはバイトコードをデコンパイルするとはっきりするだろう。上記の例でいうと、デコンパイルされたコードのListはすべて原型が用いられ、明示的なキャストが自動的に追加される。つまり、JDK5以前のコードとほぼ同様のバイトコードができあがる。<br />
<br />
もう1つの大きな違いは、配列は共変(covariant)であるのに対し、ジェネリックスは不変(invariant)であるということだ。共変とは、クラスBがクラスAのサブクラスであった場合、クラスBの配列はクラスAの配列に暗黙的にキャストできることを意味する。<br />
<br />
<pre class="brush:java">class A {...}
class B extends A {...}
であるとき:
B[] b = new B[10];
A[] a = b;</pre><br />
上記のコードはエラー無くコンパイルできる。これに対しジェネリックスは不変であるため、同様な記述が許されない。<br />
<br />
<pre class="brush:java">List<B> b = new ArrayList<B>();
List<A> a = b;</pre><br />
上記のコードはコンパイルできない。<br />
共変は一見直感的であり、便利なような気がするが、Javaの配列は参照であるが故にやっかいな問題を引き起こす。<br />
例えば以下のコードはコンパイル時にはエラーが発生しない。<br />
<br />
<pre class="brush:java">class A {...}
class B extends A {...}
class C extends A {...}
であるとき:
B[] b = new B[10];
A[] a = b;
a[0] = new C();
B tmp = b[0]</pre><br />
しかし、上記コードを実行すると、配列bの1番目の要素を取り出そうとしたときに例外が発生する。これはやっかいな問題である。上記コードであれば、例外の発生する箇所からさかのぼって、配列bにおかしな値を代入した犯人を突き止めればよいが、これが別メソッドの引数であったりすると追いかけるのが困難になってくる。<br />
何よりバグがコンパイル時に自動的に見つからず、実行時に初めて発覚する可能性があるという点がやっかいだ。<br />
もしジェネリックスが共変を許容すると、この配列の問題と全く同じことがジェネリックスでも起こる。せっかくの型保証が不完全になってしまうのだ。<br />
<br />
以上のような大きな違いがあるため、配列とジェネリックスは非常に相性が悪い。原則としてコードの中に混ぜない方がよい。Joshua Bloch著 "Effective Java 第2版" の項目25では、"配列よりリストを選ぶ"ことが推奨されている。<br />
共変が引き起こす上記のような問題を避けるため、例えば、型パラメタを指定した型の配列をnewすることはできない。"new ArrayList<String>[10]" はコンパイルエラーになる。<br />
<br />
さて、いよいよ本題に入るが、ジェネリックスや拡張for文同様、JDK5で新たに導入された機能として、可変長引数がある。これはC言語にあるprintf文の様な書式指定の出力を実現するために導入されたといっても過言ではないが、その他の場面でも非常に便利な機能である。<br />
ところが、これをジェネリックスと組み合わせた場合にちょっとやっかいなことが起こる。<br />
<br />
可変長引数とジェネリックスを組み合わせたサンプルとして、複数のリストを引数として内容をマージして返すジェネリックメソッドを考える。まずは2つのリストの例。<br />
<br />
<pre class="brush:java">static <E> List<E> concat(List<E> list1, List<E> list2) {
List<E> result = new ArrayList<E>();
result.addAll(param1);
result.addAll(param2);
return result;
}</pre><br />
これはなんの問題も無い。これを2つ以上のリストを引数とする可変長引数に修正したのが以下になる。<br />
<br />
<pre class="brush:java">static <E> List<E> concat(List<E> list1, List<E> list2, List<E>... lists) {
List<E> result = new ArrayList<E>();
result.addAll(list1);
result.addAll(list2);
for (List<E> list : lists)
result.addAll(list);
return result;
}</pre><br />
最低2つのリストを要求するため、可変長引数は3番目に追加されている。これ自体はなんの警告もなくコンパイルできる。<br />
しかし、このメソッドを利用しようとすると、コンパイル時に警告が出る。<br />
<br />
<pre class="brush:java">List<String> list1 = Arrays.asList("a", "b", "c");
List<String> list2 = Arrays.asList("d", "e", "f");
List<String> list3 = Arrays.asList("g", "h", "i");
List<String> result = concat(list1, list2, list3);</pre><br />
上記コードをコンパイルすると、以下の警告が出力される。<br />
<br />
<pre class="brush:java">注:Xxx.java の操作は、未チェックまたは安全ではありません。
注:詳細については、-Xlint:unchecked オプションを指定して再コンパイルしてください。</pre><br />
注記の通り、-Xlint:uncheckedオプションを指定してコンパイルし直すと、より詳細な警告が出力される。<br />
<br />
<pre class="brush:java">Xxx.java:xx: 警告:[unchecked] 可変引数パラメータに対する型 java.util.List<java.
lang.String>[] の総称型配列の無検査作成です。
List<String> result = concat(list1, list2, list3);
^
警告 1 個</pre><br />
コード上はきちんと型指定されているように見えるのに、総称型配列の無検査作成、つまり原型を使用していると警告が出る。これはなぜだろうか。<br />
答えはコードをデコンパイルしてみると分かる。上記のconcatメソッド呼び出し箇所は、以下のようにコンパイルされている。<br />
<br />
<pre class="brush:java">concat(list, list1, new List[] { list3 });</pre><br />
可変長引数は、そのすべての引数を含む配列に変換され、呼び出しを行っている。<br />
ここで思い出してもらいたいのだが、共変の問題のため、型パラメタを指定した型の配列をnewすることはできない。従って上記の引数を、"new List<String>[] { list3 }"というように記述することはできない。デコンパイルしたコードはすべての型パラメタが抹消されているが、上記の可変長引数部分は始めから型パラメタが指定されていない(原型)ということになる。このため、コンパイラが型安全でないことを警告しているのだ。<br />
結局可変長引数が配列で実装されているため、ジェネリックスとの相性の悪さが露呈することになった。<br />
<br />
ジェネリックスを使用してAPIを実装する場合、どうしても型安全でない警告が発生してしまうことがある。<br />
しかしそれはたいていの場合内部の実装において発生する警告であり、APIを利用する側からは見えない。<br />
上記の問題はAPIを利用する側で警告が発生してしまう。<br />
対策としてはAPI自体を別の形に修正するか、利用者に逐一無検査警告を取り除いて貰うしかない。<br />
無検査警告を取り除くには、以下のようにSuppressWarningsアノテーションを指定する。<br />
<br />
<pre class="brush:java">@SuppressWarnings("unchecked")
List<String> result = concat(param1, param2, param3);</pre><br />
SuppressWarningsアノテーションは、ローカル変数の他にもメンバ変数やメソッド、クラスなどに指定することができる。<br />
しかし、このアノテーションを指定することは、いわばクサいものに蓋をすることであり、必要以上に指定してしまうと本当の問題があった場合にそれを見えなくしてしまう。指定は極力ローカルにとどめるべきだ。<br />
上記のようにローカル変数に対して個別に指定するのが望ましい。また、なぜ警告を抑制して良いのかについて、コメントを入れておくことがEffective Javaでは推奨されている。<br />
<br />
これは非常にカッコ悪いが、ちょっとどうしようもない問題のようだ。<br />
もし私がなにか勘違いしているだけなのか、あるい根本的な対策があるならばぜひ教えていただきたい。Anonymoushttp://www.blogger.com/profile/17682850078090291459noreply@blogger.com0tag:blogger.com,1999:blog-7668940394932586677.post-30648376746257351822010-03-15T16:25:00.011+09:002010-08-04T19:31:56.489+09:00Google DevFest 2010 パッチワーク問題を解いてみたガワだけ作って1年くらい放置していたブログだが、唐突に始めてみたりする。<br />
ブログの語源をたどってみると、ウェブ上のログという意味でウェブログと呼ばれていたのが縮められたようだ。というわけでこれはただの記録。あなたにとってなんの役に立たなくても時間の返品は出来かねます。<br />
<br />
去る3/12にベルサール汐留で開催されたGoogle DevFest 2010 Japanに参加してきた。このイベントは参加証をゲットするためにクイズに挑戦しなければならないという斬新な試みがなされていた。<br />
クイズの内容はいろいろなものがあったが、いくつかプログラムを書かなければ解けない問題があった。パッチワーク問題はそのひとつ。以下に問題を引用する。<br />
<br />
<blockquote><div style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px; margin-bottom: 1em; margin-left: 0px; margin-right: 0px; margin-top: 1em; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;">ここに "A" または "B" という文字のみを含む 600 桁、600 行のテキストがあります。 これを 600 x 600 の升目状に並べ、上下左右に同じ文字がある部分をつながっているとみなします。</div><div style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px; margin-bottom: 1em; margin-left: 0px; margin-right: 0px; margin-top: 1em; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;">まず、最も多くの文字がつながっている領域をすべて "_" で塗りつぶしてください。 最も多くの文字がつながっている領域が複数存在するならば、それらすべての領域を "_"で塗りつぶすこととします。</div><div style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px; margin-bottom: 1em; margin-left: 0px; margin-right: 0px; margin-top: 1em; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;">そして、各行ごとに "_" が何個含まれているかを数え、それらの数値を改行区切りのテキスト(600 行)として答えてください。</div><div style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px; margin-bottom: 1em; margin-left: 0px; margin-right: 0px; margin-top: 1em; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;">以下の例1を見てください。この入力には単一の文字4つでつながった領域が3箇所あります。これらすべてが「最も多くの文字がつながっている領域」なので、全て"_"で塗りつぶし、その数を数えています。</div><div style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px; margin-bottom: 1em; margin-left: 0px; margin-right: 0px; margin-top: 1em;">例1:<br />
入力</div><blockquote style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px; margin-bottom: 1em; margin-top: 1em;"><pre style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; background-position: initial initial; background-repeat: initial initial; border-bottom-color: rgb(204, 204, 204); border-bottom-style: solid; border-bottom-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(204, 204, 204); border-right-style: solid; border-right-width: 1px; border-top-color: rgb(204, 204, 204); border-top-style: solid; border-top-width: 1px; font-size: 1em; font: normal normal normal 13px/1.38 monospace; margin-bottom: 1em; margin-left: 0px; margin-right: 0px; margin-top: 1em; padding-bottom: 0.8em; padding-left: 1em; padding-right: 1em; padding-top: 0.8em;">ABAAB
BABAA
BAABB
ABABB
BABAA
</pre></blockquote><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px;">塗りつぶしたところ.</span><br />
<blockquote style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px; margin-bottom: 1em; margin-top: 1em;"><pre style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; background-position: initial initial; background-repeat: initial initial; border-bottom-color: rgb(204, 204, 204); border-bottom-style: solid; border-bottom-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(204, 204, 204); border-right-style: solid; border-right-width: 1px; border-top-color: rgb(204, 204, 204); border-top-style: solid; border-top-width: 1px; font-size: 1em; font: normal normal normal 13px/1.38 monospace; margin-bottom: 1em; margin-left: 0px; margin-right: 0px; margin-top: 1em; padding-bottom: 0.8em; padding-left: 1em; padding-right: 1em; padding-top: 0.8em;">AB__B
B_B__
B____
AB___
BABAA
</pre></blockquote><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px;">答え</span><br />
<blockquote style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px; margin-bottom: 1em; margin-top: 1em;"><pre style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; background-position: initial initial; background-repeat: initial initial; border-bottom-color: rgb(204, 204, 204); border-bottom-style: solid; border-bottom-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(204, 204, 204); border-right-style: solid; border-right-width: 1px; border-top-color: rgb(204, 204, 204); border-top-style: solid; border-top-width: 1px; font-size: 1em; font: normal normal normal 13px/1.38 monospace; margin-bottom: 1em; margin-left: 0px; margin-right: 0px; margin-top: 1em; padding-bottom: 0.8em; padding-left: 1em; padding-right: 1em; padding-top: 0.8em;">2
3
4
3
0
</pre></blockquote><div style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px; margin-bottom: 1em; margin-left: 0px; margin-right: 0px; margin-top: 1em;"></div><div style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px; margin-bottom: 1em; margin-left: 0px; margin-right: 0px; margin-top: 1em;">例2:<br />
入力</div><blockquote style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px; margin-bottom: 1em; margin-top: 1em;"><pre style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; background-position: initial initial; background-repeat: initial initial; border-bottom-color: rgb(204, 204, 204); border-bottom-style: solid; border-bottom-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(204, 204, 204); border-right-style: solid; border-right-width: 1px; border-top-color: rgb(204, 204, 204); border-top-style: solid; border-top-width: 1px; font-size: 1em; font: normal normal normal 13px/1.38 monospace; margin-bottom: 1em; margin-left: 0px; margin-right: 0px; margin-top: 1em; padding-bottom: 0.8em; padding-left: 1em; padding-right: 1em; padding-top: 0.8em;">BAABBABBBB
BAABABBBBB
BBAABABBBA
BABBBABBAA
BBABAAABAB
BABABBBAAA
AABBBAAAAA
BAAAAAABBB
AAABABBAAB
AABAABBABA
</pre></blockquote><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px;">塗りつぶしたところ.</span><br />
<blockquote style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px; margin-bottom: 1em; margin-top: 1em;"><pre style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; background-position: initial initial; background-repeat: initial initial; border-bottom-color: rgb(204, 204, 204); border-bottom-style: solid; border-bottom-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(204, 204, 204); border-right-style: solid; border-right-width: 1px; border-top-color: rgb(204, 204, 204); border-top-style: solid; border-top-width: 1px; font-size: 1em; font: normal normal normal 13px/1.38 monospace; margin-bottom: 1em; margin-left: 0px; margin-right: 0px; margin-top: 1em; padding-bottom: 0.8em; padding-left: 1em; padding-right: 1em; padding-top: 0.8em;">BAABBABBBB
BAABABBBBB
BBAABABBB_
BABBBABB__
BBABAAAB_B
B_BABBB___
__BBB_____
B______BBB
___B_BBAAB
__B__BBABA
</pre></blockquote><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px;">答え</span><br />
<blockquote style="font-family: arial, sans-serif; font-size: 13px; line-height: 19px; margin-bottom: 1em; margin-top: 1em;"><pre style="background-attachment: initial; background-clip: initial; background-color: #eeeeee; background-image: initial; background-origin: initial; background-position: initial initial; background-repeat: initial initial; border-bottom-color: rgb(204, 204, 204); border-bottom-style: solid; border-bottom-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(204, 204, 204); border-right-style: solid; border-right-width: 1px; border-top-color: rgb(204, 204, 204); border-top-style: solid; border-top-width: 1px; font-size: 1em; font: normal normal normal 13px/1.38 monospace; margin-bottom: 1em; margin-left: 0px; margin-right: 0px; margin-top: 1em; padding-bottom: 0.8em; padding-left: 1em; padding-right: 1em; padding-top: 0.8em;">0
0
1
2
1
4
7
6
4
4 </pre></blockquote></blockquote><br />
問題文を一目見て、ぷよぷよかと。<br />
マス目毎に再帰呼び出しを行えば、とりあえず解けそうだなと思った。<br />
何の言語で書いてみようかと思ったが、脳ミソが溶けていてJava以外の言語で書ける気がしなかったので仕方なくJavaで書いた。以下がそのプログラム。<br />
<br />
<pre class="brush:java">package devfest;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.logging.Logger;
/**
* @author hideaki
*
*/
public class PatchWork {
private static final Logger logger = Logger.getLogger(PatchWork.class.getName());
private static enum Type {
A, B
}
/**
* パッチワークテーブルのマス目の一要素を表すクラス。
*/
private static final class Element {
/** この要素の一つ前の行の要素。無い場合はnull */
Element up;
/** この要素の一つ後の行の要素。無い場合はnull */
Element down;
/** この要素の一つ前の列の要素。無い場合はnull */
Element left;
/** この要素の一つ後の列の要素。無い場合はnull */
Element right;
final Type type;
/**
* 上下左右に同じ文字の要素のつながった数。
* 未調査の場合はnull。
*/
Counter counter = null;
Element(Type type) {
if (type == null)
throw new NullPointerException();
this.type = type;
}
}
/**
* 上下左右に同じタイプの要素がいくつつながっているかを表すクラス。
*/
private final class Counter {
private int count = 0;
/**
* カウントを1つ増やす。
* 親インスタンスのmaxメンバを参照し、countがmaxの値を超えた場合、更新する。
*/
void increment() {
count++;
if (count > max)
max = count;
}
int getCount() {
return count;
}
}
/** パッチワークテーブル */
private final List<List<Element>> table;
/** 最大連結数 */
private int max = 0;
/**
* @param args 第1引数はロードするファイル名
*/
public static void main(String[] args) throws Exception {
PatchWork patchWork = new PatchWork(args[0]);
patchWork.search();
patchWork.makeResult();
}
/**
* コンストラクタ。
* 指定されたファイルを読み込み、パッチワークテーブルを完成させる。
*
* @param filename ロードするファイル名
* @throws IOException ファイルのロードに失敗した場合
*/
public PatchWork(String filename) throws IOException {
List<List<Type>> typeTable = loadFile(filename);
List<List<Element>> result = new ArrayList<List<Element>>();
List<Element> lastLine = null;
for (List<Type> typeList : typeTable) {
List<Element> thisLine = new ArrayList<Element>();
Element lastElement = null;
for (int i = 0; i < typeList.size(); i++) {
Element thisElement = new Element(typeList.get(i));
if (lastElement != null) {
// 前後列の関連付け
lastElement.right = thisElement;
thisElement.left = lastElement;
}
if (lastLine != null) {
// 前後行の関連付け
Element upElement = lastLine.get(i);
upElement.down = thisElement;
thisElement.up = upElement;
}
thisLine.add(thisElement);
lastElement = thisElement;
}
result.add(Collections.unmodifiableList(thisLine));
lastLine = thisLine;
}
table = Collections.unmodifiableList(result);
}
/**
* ファイルを読み込んで、対応するTypeのテーブルを作成する。
*
* @param filename ロードするファイル名
* @return Typeテーブル
* @throws IOException ファイルのロードに失敗した場合
*/
private List<List<Type>> loadFile(String filename) throws IOException {
BufferedReader reader = null;
try {
List<List<Type>> result = new ArrayList<List<Type>>();
reader = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));
for (String line; (line = reader.readLine()) != null; ) {
List<Type> row = new ArrayList<Type>();
for (char c : line.toCharArray())
row.add(Type.valueOf(String.valueOf(c)));
result.add(Collections.unmodifiableList(row));
}
return Collections.unmodifiableList(result);
} finally {
if (reader != null)
reader.close();
}
}
public void search() {
for (List<Element> line : table)
for (Element element : line)
if (element.counter == null) // その要素が未判定の時
traverse(element.type, new Counter(), element);
logger.info("max:" + max);
}
/**
* 判定対象が、指定されたタイプと同じタイプのエレメントかどうかを判定する。
* 判定対象がnullの場合、判定対象が判定済みの場合、または判定対象が指定されたタイプと異なる場合は終了する。
* それ以外の場合、その上下左右の要素を再帰的に判定する。
*
* @param type 判定対象と比較するタイプ
* @param counter エレメントが保持するカウンター
* @param element 判定対象
*/
private void traverse(Type type, Counter counter, Element element) {
assert type != null && counter != null;
if (element != null && element.counter == null && element.type == type) {
element.counter = counter;
counter.increment();
traverse(type, counter, element.up);
traverse(type, counter, element.down);
traverse(type, counter, element.left);
traverse(type, counter, element.right);
}
}
/**
* 各行のmax要素を数え、標準出力する。
*/
public void makeResult() {
StringBuilder sb = new StringBuilder();
for (List<Element> line : table) {
int count = 0;
for (Element element : line) {
if (element.counter.getCount() == max) {
count++;
sb.append('_');
} else {
sb.append(element.type);
}
}
System.out.println(count);
sb.append('\n');
}
logger.info(sb.toString());
}
}
</pre><br />
ファイルから読み込む挙動とElementリストの初期化を分けたのには、特に深い意味はない。読み込み元がファイル以外になることも考えて処理を分離しただけである。<br />
処理としては単純で、あるElement(マス目)の上下左右が自分と同一であるかどうかチェックし、同一であればその先を再帰的に調べていくだけである。つながった領域と認識されたElement同士は、Counterインスタンスを共有する。Counterインスタンスはその領域のつながった数を表す。ついでにElementがCounterインスタンスを持つことが、そのElementがチェック済みであることを意味している。後で最大値をチェックするのが面倒だったので、ちょっとズルをしている。<br />
<br />
この解法で気になるのは、再帰処理のスタックがどこまで積まれるか、である。最悪の場合(全マスがAまたは全マスがB)600x600=360,000スタックが積まれることになり、これは流石にオーバーフローするだろう。したがって、これは問題のマス目の性質が比較的良心的であることを期待している。<br />
<br />
さて、DevFestで(正確にはDevFestお開き後に同じ会場で催されたGTUG主催のLightening Talkで)問題の答え合わせがあり、このパッチワーク問題にはUnion-Findと呼ばれるアルゴリズムを利用するのが良いという話があった。なので帰って早速調べてみた。<br />
<br />
一言で言ってしまうと、このアルゴリズムは、ある集合を互いに素な部分集合に分類するのに使える。パッチワーク問題でいうある集合とは600x600のマス目すべてであり、互いに素な部分集合とは隣同士がつながっている部分である。ちなみにここで言う互いに素とは、同じ要素が複数の部分集合に含まれないことをさす。要するにある隣同士がつながった塊と、別の塊の両方に、同じマス目が含まれることが無いことを意味している。<br />
同じ部分集合に含まれる要素をN-ary treeで保持し、root要素を使って管理することで高速に処理しようという狙いがある。<br />
<br />
用意しなければならない関数は2つ、あるtreeのrootを見つけるfindと2つのtreeをマージするunionである。unionは片方のtreeのroot要素の直下に、もう片方のroot要素が結合されることでなされる。treeが深いほどrootを見つける処理が増えるので、treeはなるべく浅い方がいい。なのでunion時には2つのtreeの深さを比べて浅いtreeが深いtreeの下に入るようにする。<br />
<br />
というわけで、パッチワークプログラムをUnion-Findアルゴリズムを利用するように改造したのが以下である。<br />
<br />
<pre class="brush:java">package devfest;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.logging.Logger;
public class PatchWork2 {
private static final Logger logger = Logger.getLogger(PatchWork2.class.getName());
private static enum Type {
A, B
}
/**
* パッチワークテーブルのマス目の一要素を表すクラス。
*/
private static final class Element {
/** この要素の一つ前の行の要素。無い場合はnull */
final Element up;
/** この要素の一つ前の列の要素。無い場合はnull */
final Element left;
final Type type;
private final UnionFind unionFind;
Element(Type type, Element up, Element left) {
if (type == null)
throw new NullPointerException();
this.type = type;
this.up = up;
this.left = left;
unionFind = new UnionFind();
}
void union(Element element) {
unionFind.union(element.unionFind);
}
int size() {
return unionFind.size();
}
}
/** パッチワークテーブル */
private final List<List<Element>> table;
private int max;
/**
* @param args 第1引数はロードするファイル名
*/
public static void main(String[] args) throws Exception {
PatchWork2 patchWork = new PatchWork2(args[0]);
patchWork.search();
patchWork.makeResult();
}
/**
* コンストラクタ。
* 指定されたファイルを読み込み、パッチワークテーブルを完成させる。
*
* @param filename ロードするファイル名
* @throws IOException ファイルのロードに失敗した場合
*/
public PatchWork2(String filename) throws IOException {
List<List<Type>> typeTable = loadFile(filename);
List<List<Element>> result = new ArrayList<List<Element>>();
List<Element> lastLine = null;
for (List<Type> typeList : typeTable) {
List<Element> thisLine = new ArrayList<Element>();
Element lastElement = null;
for (int i = 0; i < typeList.size(); i++) {
Element upElement = (lastLine == null) ? null : lastLine.get(i);
Element thisElement = new Element(typeList.get(i), upElement, lastElement);
thisLine.add(thisElement);
lastElement = thisElement;
}
result.add(Collections.unmodifiableList(thisLine));
lastLine = thisLine;
}
table = Collections.unmodifiableList(result);
}
/**
* ファイルを読み込んで、対応するTypeのテーブルを作成する。
*
* @param filename ロードするファイル名
* @return Typeテーブル
* @throws IOException ファイルのロードに失敗した場合
*/
private List<List<Type>> loadFile(String filename) throws IOException {
BufferedReader reader = null;
try {
List<List<Type>> result = new ArrayList<List<Type>>();
reader = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));
for (String line; (line = reader.readLine()) != null; ) {
List<Type> row = new ArrayList<Type>();
for (char c : line.toCharArray())
row.add(Type.valueOf(String.valueOf(c)));
result.add(Collections.unmodifiableList(row));
}
return Collections.unmodifiableList(result);
} finally {
if (reader != null)
reader.close();
}
}
public void search() {
for (List<Element> line : table) {
for (Element element : line) {
compare(element, element.up);
compare(element, element.left);
}
}
logger.info("max:" + max);
}
private void compare(Element thisElement, Element otherElement) {
assert thisElement != null;
if (otherElement != null && otherElement.type == thisElement.type) {
thisElement.union(otherElement);
int tmp = thisElement.size();
if (tmp > max)
max = tmp;
}
}
/**
* 各行のmax要素を数え、標準出力する。
*/
public void makeResult() {
StringBuilder sb = new StringBuilder();
for (List<Element> line : table) {
int count = 0;
for (Element element : line) {
if (element.size() == max) {
count++;
sb.append('_');
} else {
sb.append(element.type);
}
}
System.out.println(count);
sb.append('\n');
}
logger.info(sb.toString());
}
}
</pre><br />
<pre class="brush:java">package devfest;
public final class UnionFind {
/** この要素のroot。経路圧縮のためにメンバ定義する。 */
private UnionFind root = this;
/** この要素の親要素。この要素がrootの場合はnull */
private UnionFind parent;
/** この要素が含まれるtreeの深さを表す。自身がroot要素である場合に限り意味を持つ。 */
private int rank;
/** この要素が含まれるtreeの構成数を表す。自身がroot要素である場合に限り意味を持つ。 */
private int size = 1;
/**
* この要素が含まれるtreeのrootを見つけて返す。
*
* @return root要素
*/
public UnionFind find() {
while (root.parent != null)
root = root.parent;
return root;
}
/**
* この要素が含まれるtreeと引数で指定された要素が含まれるtreeを結合する。
* 但し、両者のrootが同一である場合(すでに結合されている場合)何も行わない。
*
* @param other 結合する相手のtreeに含まれる要素
*/
public void union(UnionFind other) {
UnionFind thisRoot = this.find();
UnionFind otherRoot = other.find();
if (thisRoot != otherRoot) {
if (thisRoot.rank > otherRoot.rank) {
otherRoot.parent = thisRoot;
thisRoot.size += otherRoot.size;
} else {
thisRoot.parent = otherRoot;
otherRoot.size += thisRoot.size;
if (thisRoot.rank == otherRoot.rank)
otherRoot.rank++;
}
}
}
public boolean isRoot() {
return parent == null;
}
public int size() {
return find().size;
}
}
</pre><br />
再利用の予定は今のところないが、純粋なUnion-Findアルゴリズム部分は別クラスとしている。<br />
<br />
このアルゴリズムの計算量は O(A(n)) となるらしい。Aはアッカーマン関数の逆関数。この辺になるとまともな文献を漁らないとなんのことか分からないが、かなりゆっくり増加する関数らしい。Anonymoushttp://www.blogger.com/profile/17682850078090291459noreply@blogger.com3