Hatena::ブログ(Diary)

小人さんの妄想 このページをアンテナに追加 RSSフィード Twitter

2009-01-02

ツリー構造、もう1つの答

をいをいをいをい、ホットエントリーに載るって、こんなに大変なことだったのか。

正月早々、俺はパソコンに向かって何やってんだ。

もっとまったりと、ダラダラする予定だったのに・・・

でも気になる、気になるんだよー。。。なんかフォローを書かずにはいられない。

以下は前回のエントリー id:rikunora:20081228 の続編です。


大きな数を表すとき、日本では「一、十、百、千」を1つの塊として、それに「万、億、兆・・・」といった名前を付けています。

一方、英語では「One, Ten, Hundred」を1つの塊として、それに「thousand, Million, Billion・・・」といった名前を付けます。

日本の塊は4つずつ、英語の塊は3つずつです。

そこで、日英対決!

4と3ではどちらがより効率的なのでしょうか。


前回のエントリーで

* 数字という文字を、ギリシア数字で考えるとIVXの3文字で表示?

というコメントをいただきました。

これはまた、おもしろい数字体系に着目しましたね。

※「ギリシャ数字」じゃなくて「ローマ数字」だった! あっちゃー。。。(1/8追記)

ギリシア数字は「3つの記号 -> それを組み合わせて数を表す」という、一段階置いた間接的な仕組みをとっていますよね。

そこで「複数の記号をひとまとめに扱って、操作レベルを1段階増やす」方法もあることに気付きました。

上述の、大きな数を幾つかのブロックにまとめて数える方法。

ギリシア数字のように、いったんIVXの3文字で表記するという段階を踏んで、その上で操作を行う方法。

今回は、こうした多段階の仕組みに着目してみましょう。


実際の日本語や英語では、塊を作る階層が1段階だけなのですが、

以下ではツリー構造を想定して「多段階の数え方」というものを考えることにしましょう。

「多段階の数え方」とは、「一、十、百、千」という4つの数字記号だけしか使わない代わりに、

「5百千千千」のように、記号を何回繰り返してもよい、とする数え方です。

こうした恣意的な仮定を導入して、問題を「ツリー構造の性能評価」という一般的なものに落とし込んでみます。

f:id:rikunora:20090103003653p:image

図の右端が「日本語型4分岐」、中央が「英語型3分岐」、左端が比較のための最も単純な「2分岐」ツリーです。

この3つのツリーの中で、どれが最も優れているのでしょうか?

最適な分岐数というものは存在するのでしょうか?


ところで、ツリー構造って何だろう。

身近な例は、パソコンのフォルダ。

パソコンの中では、たくさんのファイルはフォルダを作って整理しますよね。

あれはツリー構造そのもの。

今、考えているのは「1フォルダに平均何個くらいファイルを置いたら最も効率的か」という問題と同じことです。

ツリー構造はデータの分類整理に威力を発揮する、すごい発明なんです。

いわゆるデータベースでは、高速な検索技術としてツリー構造を用いています。

なのでこの問題は、高速なデータベースを作るにはどうすればよいか、という実用上の問題と深く関係しているんです。


さて、ただ漫然とツリーの絵を眺めていても、答は思い付きません。

ここはひとつ、もっとも単純な仮定、

  (記号を1つ増やす手間)=(操作段階を1段増やす手間)  ・・・[仮定1]

を入れてみましょう。

操作段階(=ツリーの高さ)がN段だったとき、表し得る状態数(=ツリー底辺の長さ)は、

それぞれのツリーで 4^N、3^N、2^N です。

なので、ある一定の状態数M個を表わすのに要する手間は、

  M = N^N

となります。

この f(N) = N^N を最小にするようなNはいくつになるか。

対数をとって微分してみます。

  f(N) = N^N

  log f(N) = N log(N)

  (log f(N))' = log(N) + N・(1/N) = log(N) + 1

(log f(N))' = 0 となるのは、- log(N) = 1 になるとき、

つまり、N = 1/e となるときが最小値です。

( 直接 f(N)' を求めると、N^N { 1 + log(N) } となります。

 なんだか大学入試問題みたい。暇な人はやってみよう。)

f(N) = N^N という関数がおもしろいので、グラフに描いてみました。

f:id:rikunora:20090103003654p:image

1/e = 0.367879 のところに極小点があります。

つまり、[仮定1] を正しいものとすれば、ツリーの分岐は約0.37本が良い。

実際には小さいほど良い、つまり2分岐ツリーが最適ということになります。


でも、実際のところ [仮定1] は妥当でしょうか。

パソコンでファイル1個作るのと、フォルダ階層1つ作るのと、どちらの手間が大きいか。

普通の感覚からすれば、(ファイル作成の手間)<(フォルダ階層の手間)ですよね。

そこで、この手間の比率を R と置いて、改めて次の仮定を布いてみます。

  (記号を1つ増やす手間)= R ・(操作段階を1段増やす手間)  ・・・[仮定2]

つまり、このツリー比較にベストの答なんてものはなくて、

最適な分岐数は、操作段階を1段増やす手間によって変わってくる、ということです。

ある一定の状態数M個を表わすのに要する手間は、

  M = (N / R) ^ N

以下、上と同じようにして

  f(N) = (N/R)^N

  log(f(N)) = N log(N/R) = N { log(N) - log(R) } = N log(N) - N log(R)

  (log f(N))' = log(N) + 1 - log(R)

(log f(N))' = 0 となるのは、log(N) = log(R) - 1 になるとき、

つまり、N = R / e となるときが最小値です。

( 直接 f(N)' を求めると、(n/r)^n ・{ 1 + log(n/r) } ってなるんだぞ。

 ううっ、難関大学入試問題・・・)

N と R の関係は直線的だったんです。

ここから、

・4分岐ツリー(日本の数え方タイプ)のR = 約 10.87

・3分岐ツリー(英語の数え方タイプ)のR = 約 8.15

といった数字が出てきます。

英語の方がより操作的、ツリー階層を作るのに躊躇しないんですかね。

そういえば、アルファベット26文字よりも、漢字まで持っている日本語の方がずっと記号の種類も多いし。

ちなみに、問題の発端となったギリシア数字は、およそ3分岐ツリーの延長上(3分岐ツリーを1段深く掘り下げた形)となっています。

つまり、西洋文化は昔から階層を作りたがる傾向にあるのだと、、、そういった妄想に発展するわけですね。


------------------------------------------------------------------------

ところで、上のツリー構造のお話は、前回のエントリーの「e進法」とどのように関係するのか。

なんか、前回と違うこと言ってない?

はい、違うこと言ってます。

じゃあ前回の「e進法」はウソなの?

いや、そんなこともないです。

前回のは前回ので、一理あるんです。

視点が違いますから!

以下に、とっても常識的で、アタリマエで、つまらないお話を付け足します。


最も優れた進数とは、いくつなのか?

前回のエントリーと合わせて、私は3つの視点を提供したつもりです。

 視点1.e進法 -- 回路設計者の視点。

 視点2.めんどうくささ -- 日常的な視点。

 視点3.ツリー構造 -- データベース設計者の視点。

この3つには、それぞれ前提、仮定があって、結論があります。

これはなにも進数の話に限ったことではなくて、何だってそうです。

     (前提)、(仮定) -> (結論)

 視点1.機械、2状態のランプ -> e進法 が最適。

 視点2.人間、めんどくささ = 桁数K+基数N -> 10進数はちょっと多めかな?

 視点3.機械/人間両方、検索の手間 = (N/R)^N -> 階層を作るコストに依存。

こうして見渡せばわかりやすいかな。

この視点ってやつは、3つで終わりなのか?

そんなことないですよね。

考えれば、まだいくらでも出てくると思います。

実は、今回の視点3.は、わざわざ「別の視点が存在するんだよ」ということを示すために作ってみました。

(なので視点1.よりも、もっと話に無理がありますね。)

その気になれば、私はあと3つくらい、同列のお話を作れます。(もう飽きたから寝るけど)


e進法 について、ブックマークのコメントを見たところ、どうやら

「最初から2状態のランプを使って考えれば、2進法に有利なのは当たり前じゃない?」

という疑問が多いみたいですね。

その通り。

仮定ですから、アタリマエです。

その仮定が妥当かどうか、自然に受け容れられるかどうか、という判断だけです。

自然だと思えば受け容れるし、こじつけだと思ったら捨てる、それだけ。

私としては、2状態という仮定を布いたにもかかわらず、

結果が2ではなく2.71828...と、ずれた所に来たのが興味深いな、と思っています。


ちなみに、e進法というのは私がオリジナルに考え出したアイデアではありません。

エントリー中で紹介した以下のページにも、よく見ると書いてありますよ。

* 三進法のコンピューターが、二進法のコンピューターより優れた点は?

>> http://oshiete1.goo.ne.jp/qa2083198.html

「原理的にはe=2.718・・・進法のコンピュータが最も効率がいいそうです。」

実は、私も以前「原理的にはe進法」という結論のところだけ、小耳に挟んだことがあったんです。

でも、なぜそうなるかという説明まではなかった。

そこで、なぜそうなるかという理由を自分なりに考えて、導き出したのが「ランプ」だったのです。

実際のところ「e進法」に、どれほどの妥当性があるのか、私にも計りかねます。

おそらく「e進法」の言い出しっぺは、回路設計者の視点に立って、このことを言ったのだと思います。


ランプでe進法、というお話は、もちろん絶対の真理ではありません。

(もし頭からそう信じていた人がいたら、(前提)、(仮定)を問う習慣を付けよう。)

そもそも「最も優れた進数」というお話に、唯一絶対の答なんて無いんです。

なぜ無いのか。

それは、(前提)、(仮定) によって答が変わってくるからです。

設問の立て方が悪くて、あいまいで、(前提)、(仮定)が1つにビシッと決まっていない。

なので、いくらでも妄想を繰り広げる余地があるんですねー。


で、そこまで認めた上で、期待していたのは、もっとオモロくて斬新な視点だったんだけどなー。

私はしょせんコンピュータ技術者なので、コンピューターチックな発想しか出てこないんですよ。

これだとつまらない。

なんかこう、俺は前衛的なジャズが好きだから11拍子だっ!とか。

ゴルゴが好きだから13なんだっ!とか。

個人的には「えーっ、そんなのあり?!」って叫んじゃうような、ぶっ飛んだ発想が好き。

やりすぎるとホントに飛んでっちゃうんで、そのさじ加減が微妙なんですが。。。

視点4.以降の、オモロい発想を期待してるよっ!


kokogikokokogiko 2009/01/03 17:04 すみません
ケータイからの操作ミスでスターつけちゃいました
悪意も他意もありません

kokogikokokogiko 2009/01/05 18:47 こんばんは。
面白いんですが、結論に意外性がないのが残念です。
>・4分岐ツリー(日本の数え方タイプ)のR = 約 10.87
>・3分岐ツリー(英語の数え方タイプ)のR = 約 8.15
>といった数字が出てきます。
>英語の方がより操作的、ツリー階層を作るのに躊躇しないんですかね。

単に「英語の方がツリーを作るのに躊躇しない」という結論では、英語の方が少ない桁数で位が上がるわけですから、計算をしなくても直感だけでも答えられそうなので、今一つな気がします。
せっかく数値まで計算したわけなので、直感では導けないもう一歩踏み込んだ結論が欲しい気がします。

あと、ローマ数字は、I、V、Xの3文字で表記されるわけではなく、
・1の位:I(1)、V(5)の2文字(正確には9にはXを使いますが)
・10の位:X(10)、L(50)の2文字(正確には90にはCを(ry)
・100の位:C(100)、D(500)の2文字(正確には(ry))
というふうに、桁ごとに違う2文字を使って表す考え方です。
なので、言わば一桁毎に違う表現を使っているわけなので、1分岐(?)ツリーなのかもしれません。
http://ja.wikipedia.org/wiki/%E3%83%AD%E3%83%BC%E3%83%9E%E6%95%B0%E5%AD%97

rikunorarikunora 2009/01/08 12:01 まず「ギリシャ数字」じゃなくて「ローマ数字」だった!
そして、そのローマ数字の書き方が、数字が大きくなるとこんな風になるとは知らなかった。
人に「オモロい発想を期待」するくらいなら、もっと深く練り込まないといけませんね。
まだまだ修行が足りんです、ハイ。。。

あと、以外に難しそうなのが中国語での数え方。
「中国 数字 数え方」でググったら、こんな記述がありました。
http://www.chinesemaster.net/modules/grammar/?%E6%95%B0%E9%87%8F%E8%A1%A8%E7%8F%BE%2F%E6%95%B0%E3%81%AE%E8%A8%80%E3%81%84%E6%96%B9%E3%81%A8%E6%95%B0%E3%81%88%E6%96%B9
“兆”の定義については十進法、万進法、自乗法の三種類があり、「一万?=一兆」とするのは万進法である。
自乗法の場合は「一??=一兆」となる。貨幣については日本と同様に万進法を採用しており、日本語の影響を受けた可能性も考えられる。
( ? のところ、文字化けして上手く表せない。「にんべんに乙」という文字です)

私は、何の気無しに中国語と日本語の数え方は同じなのかと思っていたのですが、どうやら違うらしい。
中国語(や他の国々)の数え方に詳しい方、ご教示願えませんか?

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証