ここ数回は真面目で技術的な記事を書いていますが、 それ以前は「これをインストールしたらこうなった」みたいな事しか書いていません。 しかし、世間的にはそういう記事が一番需要があるようです。 「GIMP 解像度」とかいって検索して来る人が非常に多いですね。
そういう意味では、ろくな記事無いよな。ほんと、このサイトって。 つまり「これをインストールしたらどうこう」みたいな tips 的観点からいって、 役に立つようなものが実に少ないという事です。
世間でいうところの「プログラミング」という仕事の大部分は、 機械を動かすためだけに必要な、 いわゆる「呪文」と呼ばれている、 あるいみどうでもいい制限や迂回策などのノウハウを 記述する作業にほかならないわけです。 一番面倒な「ロジック」とか通称されている部分は、 せいぜいが多重ループどまりです。
つまり世間の情報処理産業というのはしばしば、 機械を動かす上での tips and tricks の多寡における格差の中に、 存在意義を見出しているわけです。
コピペやダウンロードで解消されるようなリテラシ格差に 存在意義を見出していたのでは、 「情報処理分野において確かな事はただ一つ、 それは変わらないものなど存在しないということだ」 みたいな話にならざるをえない。
しかし、私としては、そのような時局に依存した移ろいやすいものを避け、 たとえば普遍的に存在する数理上の構造に依拠したノウハウを 実際の問題を解決する上で役に立つようなかたちで ちょっとずつ紹介していこうと思うのです。 なぜかというと、じつは私は、パソコンとか嫌いなんですよ。 こんなもんを動かす上で必要になるしょうもない約束事とか、 そういうのを憶えたり調べたりするのが苦手だし、大嫌いなんですわ。
じゃあ一時期なぜそういう事を書いてたのかというと、 それは、自分の苦手なものを克服してパソコンが動くようになったのが、 嬉しかったからです。
Ruby の array は非常に便利なクラスで、 何が便利ってメンバが何でもいい、というところがイカス。
だから、array の array の array の array の array とか 作れるわけで、これを使って2分木とかを簡単に作ってみることができる。
ところで array には、メンバが何個入っているかを調べる メソッド length がある。 しかし、 array で2分木を作ってしまうと、 メンバの数は常に2であり、全然参考になる情報がとれない。
これはべつに悪いことではなくて、 そのように、下の構造が隠蔽されているのが木構造の良いところでもある。
じつはメンバが何個あるかを数える簡単な方法はある。 こうすればいい。
array.flatten.length
flatten はネストした array を展開して平坦化してくれるので、 その長さを数えればよいのだ。
では、何段入れ子になっているかを数えるにはどうすればよいだろうか？
とりあえず depth っていうメソッドがあったら、それがやってくれそうなので、 試してみるが、そういうメソッドはなさげ。
そこで無きゃ作ってみよう、というのがこの記事の趣旨です。 つまりここからがネタ。
メンバが array 以外の、普通のデータが入ってる array の depth は1 でしょう。 でも待て。メンバが array 以外ってどうやって判る？
self.map{|e| e.class}
これで判りますね。だからこの結果が全部 Array 以外だったら、1を返すことに すればいい。 でもまてよ。じゃあメンバが Array だったらどうすりゃいいの？ というかそもそも depth って何？
そこでじっくり考えてみよう。 もしいま array のメンバの depth がそれぞれ 2 3 4 5 だったとして、 その array の depth は幾らなら良いの？ それは当然、 6 ですよね。 要するに、一般化すると、メンバの最大 depth +1 が自分の depth ですよね。 これが問題の本質を捕まえた瞬間です。
じゃあそれをそのまま書こう。
def depth
self.map{|e|
if e.class == Array
e.depth
else
ここは謎
end}.max + 1
end
そのまんま書いてみました。ただし、謎のまま残っているところが 一箇所あります。 これを解決するのが、さきの、ネストしていない array の depth は幾らなのか？という観察です。 1だったはず。 だから謎部分のコードはリテラルの 0 でいい。 ネストしていない arrayのdepth は map の中身は全部ゼロで、最大値もゼロ。それに1足して depth は1です。 これが再帰の端になります。 つまり正解は
def depth
self.map{|e|
if e.class == self.class
e.depth
else
0
end}.max + 1
end
また、array の depth は array 以外のデータでは 0 というのは直観的にも妥当に見えます。 むろん、このメソッドが array 以外のデータから呼ばれる事は ないのですが、たとえそうであったとしても この種の統一性は良い事です。
2009/11/17 追記: クラスを即値じゃなくて self.class にしとけば、 Array の子クラスでも使えて便利なのでそのように改めました。
ayさんのにっきから、C言語一行コードを実現するツールとその15分間パケージング。