[python] どう書く？-- 一方向リスト編その2

前に書いたコードでも期待する動作はするんだけど、やっぱり気になるので無駄をなくしてみました。

そのまえに、まずは前のエントリのコメントに答えておこうか。

簡単・複雑以前に、用途に対する道具の規模が大きすぎるような。リソース消費量という観点でまずくないでしょうか？

辞書やら集合やらって、かなり高機能なコンテナで、それを素のC言語でも簡単に実装できるようなリスト構造のためにふんだんに用いるってのは、バランス的にどうかという気がします。(内部的には、辞書・集合オブジェクトの「中で」リスト構造は山のように使われているはずで)

え～と、実際にわたしは要素数100万の集合オブジェクトを複数定義して、それらを使った演算をするコードを書いたことがあるんだけど別に問題なかったんだけどな。それどころか同じ処理をするために C++ で書かれた、作者たちが「Python で書いたそれよりも比べるまでも無く高機能で、メモリ効率がいい」といっているプログラムを動作させたら Out Of Memory が発生したっけ。

何が言いたいかというと、何事も使い方次第だってこと。

わたしのコードとコメント先にあるコードを何人かに見比べてもらうこともしたんだけど。わたしの師に当たる方も友人も「美しい」のはわたしのほうだという回答をいただけた。もっとも師匠からは「どちらかといわれればこっちだけど、君のコードにはまだ無駄がある」というようなことを突っ込まれたけど ( ´･ω･`)

あと、おまけの一言として「Python のコードの比較に C を持ち出して C ではどうこういうのはおかしい」ってのもあったな。ごもっとも。C ならどうこう言うのなら最初から C で書けばいいのだ。そもそも、Python を使う利点に「メモリを節約できる言語」ってのは無かったと思う。メモリ消費量を極限まで減らして、パフォーマンスもかつかつにチューニングしたいならアセンブラと C を使うというのがいい選択肢だと思うけどね。

あぁ、後バランスだっけ？見たところ、あなたのコードは引数として渡されたオブジェクトの中に一方向リストが1つある場合にしか正常に動作しない。その点でボツだと思うんだけどどうなんだろうね。わたしから見れば、課題の要求を満たしていないように思える。コードを追加することで対応できるだろうけれど、そのときには数学的な美しさからはさらに離れるでしょう。

さて、突っ込まれてから書き直したコードが↓
doctest とかは削ってあります( ´･ω･`)

# coding: utf-8

def get_endpoint( linked_list ):
	difference = set( linked_list.values() ) - set( linked_list.keys() )
	
	return (None if difference == set([]) else difference)

辞書の鍵を要素とする集合 linked_list.keys() と値を要素とする集合 linked_list.values() の対称差がφなら、差もφになる。また、部分的に循環がある場合は linked_list.values() - linked_list.keys() もφになる。つまり循環が部分的であれ全体であれ、循環構造がある場合には linked_list.values() - linked_list.keys() = φ となる。

一度集合差を求めて、その結果を判定するだけで求める答えは導けると考えられる。

なんでこのことに気づけなかったんだろう・・・＿|￣|○

[python] どう書く？-- 一方向リスト編

今日の御題。

a は b を参照し、b は c を参照し、c は d を参照し・・・ という、いわゆる一方向リストがある。 このデータ構造体における終端のオブジェクトを返す関数を書け

わたしはこれを「a を指定すると b が返り、b を指定すると c が返り、c を指定すると d が返る・・・」 というデータ構造体と考え、これは Python では辞書で表現できると考えた。そこで書いた答えが↓

# coding: utf-8
def get_endpoint( linked_list ):
	"""
	循環リストの場合は None を返す。
	線形リストの場合は終端のオブジェクトを返す。
	"""
	if (set( linked_list.keys() ) ^ set( linked_list.values() )) == set([]):
		return None
	
	difference = set( linked_list.values() ) - set( linked_list.keys() )
	return (difference if difference else None)

最後の2行はもともとは return (set( linked_list.values() ) - set( linked_list.keys() )) だったんだけど、 それでは部分的に巡回するリストだった場合に空集合 φ が返ってしまうので上記のように修正を加えた。 それでも正しく動作しないという人がいるんだけど、わたしには正しく動作するように思える。

まず、一方向リストにはリングバッファ( 円形リスト ) と線形リストがある。このうち、リングバッファについては 集合 set( linked_list.keys() ) と集合 set( linked_list.values() ) の対象差は空集合φになるのは 考えるまでもなく明白である。

リングバッファを次のように表現しよう

circular_list = {a:b, b:c, c:d, d,a}

この場合、circular_list の鍵を要素としてもつ集合は set([a, b, c, d]) となり、 値を要素として持つ集合は set([b, c, d, a]) となる。両者の対象差は当然 φ になる。

そして部分的に循環がある場合は、値の集合から鍵の集合を引いた差 difference が φ になる。 difference が φ でないのは、終端が存在する一方向線形リストのときだけなのだ。

スタックを使った方が簡単だといわれたのだが、わたしにはそちらの方がよほど難しいように思える。 実際、集合を使ったアルゴリズムはすぐに思いついたけど ( 初版のコードはエラーあったけど( ´･ω･`) ), スタックを使ったコードはむしろ何でスタックが必要なのか理解に苦しんだ。 何より数学的に美しくないと感じるのだ。

[PC] 便利だけど、ちょっと熱い Thinkpad X61 Tablet

ThinkPad X61 Tablet を使ってみました。
改善されたキーボードと、より直感的な操作を可能にする指先入力機能が秀逸です。

わたしは X60 も使っているんだけど、キータッチは X61 Tablet のほうが、比較にならないくらい快適。押してるんだかどうだか実感がわかないような X60 のキーボードと違って X61 Tablet のキーボードは打鍵感がしっかりしています。タイプしていて気持ち良い。また、ペン入力だけじゃなく、指先でカーソル操作ができるのも便利。わざわざペンに持ち替える必要がなく、キーボードからそのまま手をディスプレイに持ち上げてマウスカーソルの操作とか、文字通り「手書き入力」ができます。

指先入力ができるので、マウスやタッチパッドより直感的。
これならマウス、トラックポイントやタッチパッドが苦手という人でも使えると思います。 マウスのように設置スペースをとらないので電車の中とか散らかった机の上でも問題なし。

X60 できつかった原因のひとつの発熱は、X61 Tablet ではある程度抑えられていた。X60 では無線 LAN モジュールをつかって高速通信を連続でしているときなどはノートPC クーラーを使っていてもパームレストが熱く感じるくらい酷かった。X61 Tablet では低電圧版 CPU に切り替えたからか改善されたように感じます。ノートPCクーラーに乗せていればわずかに暖かいなと感じるくらい。クーラーなしでも、まぁ我慢できるかなという感じ。

X61 Tablet は入力系が大幅に強化された使いやすいマシンだと思う。
ファイル、フォルダなどを指先で操作できるのは、マウスなどに比べてもはるかに直感的。マウスですら「直感的ではない」という人にもお勧めできる。マウス操作を難なくこなすユーザでも、指先操作に慣れると、指先操作のほうが高速になったりする ( マウスでポインタをアナログに動かすよりも、指先で狙ったポイントに直接飛べるとか便利 )。
パームレストが熱くならなければモバイル PC としては文句なしでしょう。

[ms-office / 備忘録] Office2007 で PDF 出力を可能にするアドオン

Office 2007 シリーズで PDF 出力を可能にするアドオンのダウンロード先。

2007 Microsoft Office プログラム用 Microsoft PDF/XPS 保存アドイン

Google で検索するとダウンロードページはもちろん、本家 MS Office オンラインへのリンクすらない間抜けなニュースサイトがかなり引っかかるのでダウンロード先をメモしておきます。

「Microsoft が Office に PDF 出力機能を追加するアドインを公開」なんて記事を書くのなら該当ページへのリンクくらいはつけてほしいものだね。ソースへのリンクを Reference として付記しておくのはニュースサイトなら当然のことではないのか？

[windows / 備忘録] 邪魔な吹出し ( バルーン Tips ) を無効にする

ノート PC を買って、数年ぶりに XP をデフォルトで使った。そこで感じたのはあまりにも邪魔な機能が多すぎるということだ。ほとんどは過去の備忘録などを参考に無効にできたのだがバルーン Tips を無効にする方法がなかなかわからなかった。バルーン Tips というのは下のスクリーンショットのようなものだ。

バルーン Tips っていうのは、「更新プログラムが～」とかよくタスクトレイにポップアップしてくるあの吹出しだ。何を考えてあんなものを XP の機能として実装したのか理解できないんだけど、ひとつわかっていることは、あれは邪魔以外の何物でもないっていうことだ。あんなものは無効にしてしまおう。

バルーン Tips はレジストリを操作することで無効にできる。次のツリーを開こう。

HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\Advanced

目的の場所までツリーを開けたら、次は右側のペインに値を作成する。右側のペインを右クリックして、表示されるメニューから [新規(N)] →[DWORD 値(D)] を選ぼう。

新しい値が作成されたら、値の名前を EnableBalloonTips に変更。
下のスクリーンショットのように編集できたらレジストリエディタを終了して再起動。

再起動後はバルーン Tips は表示されなくなっているはず。

落ちてた orz

以前募集していた Thinkpad の大和事業所見学ですが、落ちてました(´･ω･｀)

残念。X60 とも長くなりそうだしなんだかなー・・・
なんとかして25万 ( T61 ) 貯められないものかな・・・

[science] ビッグバン宇宙論

3 日ほど沖縄に行っていました。旅先ではネットに繋げなかったのですが、本を読んだり自然を観察することができました。 些細なことですが仮説を立ててそれを観察で確かめたりと、久し振りの、数年ぶりのゆっくりとした充実した時間だったと思います。 そこで実感したのは時間に追われる生活を送っていては知性は伸ばせないし、ろくなことを想起できないということでしょう。 欲を言えば、ヤンバルや西表で生物相を観察してみたかったです。動物園でイリオモテヤマネコなでなでもしたかったな (*/▽＼*)

さて、持っていった本は「ビッグバン宇宙論」。読みたかったのですが、仕事方面で学ぶことが多くてまとまった時間をとることができなかった わたしの原点ともいえる理学分野のお話です。邦題からは暗号としか思えない数式と計算だらけの難しい本を連想してしまうと思いますが、実際の 内容は原題 "BIG BANG - The Most Important Scientific Discovery of All Time and Why You Neet to Know About it" が表している通りのものです。

「宇宙がどうなっているのか」この問いに人間は紀元前から挑み、いくつもの考えが生まれました。 広く受け入れられた考えもありますし、「常識的にありえない」と一蹴された考えもあります。 この本では、その考えがどうして生まれたのか、どうして当時否定されてしまったのかといったことと、 それぞれの説を考えた人たち -- 望遠鏡を自作したマッチョな貴族のおじさんとかメイドさん、アインシュタインの苦悩 -- のエピソードが書かれています。 この本の上巻を読めば宇宙論は突飛なものではなく、他の分野と同じように日常から生まれたものだということがわかるでしょう。

しかし、本書が優れているのは「科学者として一番大切なものは何か」を簡潔にそして説得力のある形で示していることと、 それにどのようにして向き合えばいいのかも具体的に書かれていることでしょう。科学者として疑問に向き合うにはどうすればいいのか、 データをどのようにみればいいのか。そして、打ち砕かれる説と生き残る説はどこが違うのか。

宇宙とは関係がない分野を研究している、または目指している場合でも本書から得られることは大きいと思う。 学生、あるいは研究者として続けていくことに疑問を感じた時に読んでほしいタイトル。

もちろん、本書には宇宙に関する様々な疑問の答えとその考え方もわかりやすく解説されている。 月の大きさはどうやって求められるのか。宇宙に行くこともできない紀元前に地球の赤道距離をどうやって求めたのか。 地球から太陽までの距離はどうやって求められたのか。すんごい遠くにある星 -- たとえばシリウス -- までの距離ってどうやって求めるのか。 宇宙の大きさってどうやって考えるの？ こんな疑問を持ったことがあるなら楽しめるでしょう。