« [PC] 便利だけど、ちょっと熱い Thinkpad X61 Tablet | トップページ | [python] どう書く?-- 一方向リスト編その2 »

2007/07/14

[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 | トップページ | [python] どう書く?-- 一方向リスト編その2 »

コメント

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

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

投稿: zetamatta | 2007/07/14 09時06分

コメントを書く



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


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



トラックバック

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

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

« [PC] 便利だけど、ちょっと熱い Thinkpad X61 Tablet | トップページ | [python] どう書く?-- 一方向リスト編その2 »