« [python] どう書く?-- 一方向リスト編 | トップページ | 生きてます »

2007/07/17

[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] どう書く?-- 一方向リスト編 | トップページ | 生きてます »

コメント

すみません。素直に白旗を挙げさせていただきます。

どちらかというと前提条件をわたくしがきちんと理解しきれていない・自分の考えの説明不足などが大きいと思いましたので、ここは真摯に負けを認めるべきと判断いたしました。。本当は、勝ち負けの問題じゃなくて、自分が思うところの問題点をきちんと説明して、相互理解をすすめるのが生産的だと思うのですが、そのゆとりが今はないもので…たいへん申しわけなく。

また、当方(わたくし)のウェブの記事におきましては、自分のフィールドという思いが強いため、やや挑発的な記述になっていたかと存じます(いつも、こんな調子なのですが)。それゆえ、お読みになって、ややご不快の点があったかもしれません。その点についてはお詫びいたします。

投稿: zetamatta | 2007/07/19 08時26分

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/103108/15793562

この記事へのトラックバック一覧です: [python] どう書く?-- 一方向リスト編その2:

» [Python]一方向リスト [odz buffer]
ref:Fomalhaut of Piscis Australis : python どう書く?-- 一方向リスト編 ref:Fomalhaut of Piscis Australis : python どう書く?-- 一方向リスト編その2 ref:DARK SERVER - $ python どう書く?-- 一方向リスト編 def get_endpoint( link... [続きを読む]

受信: 2007/07/21 01時20分

« [python] どう書く?-- 一方向リスト編 | トップページ | 生きてます »