[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() = φ となる。

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

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