舌足らずなブログ: 5月 2009

2009年5月26日火曜日

「１０分でコーディング x 2 〜リストの破壊的操作篇〜」を解いてみる

乗り遅れた感はありますが、g00000さん出題のLISP問題を解いてみました。

１０分でコーディング x 2 〜リストの破壊的操作篇〜 - わだばLisperになる - cadrグループ

(1) alistを破壊的にplistに変換する関数(nalist-to-plist)を書いて下さい。
(2) nplist-to-alistも作ってみて下さい。

まず自分がやったのは「リストの図を書く」こと。実際は紙の上で考えた。

;; 連想リスト:alist  '((foo . 1) (bar . 2))

   +-+    +-+
-->|1|--->|3|--->nil
   +-+    +-+
    |      |
    V      V
   +-+    +-+
   |2|->1 |4|->2
   +-+    +-+
    |      |
    V      V
   foo    bar

;; プロパティリスト:plist  '(foo 1 bar 2)

   +-+   +-+   +-+   +-+
-->|1|-->|2|-->|3|-->|4|-->nil
   +-+   +-+   +-+   +-+
    |     |     |     |
    V     V     V     V
   foo    1    bar    2

なるほど、確かにコンスセル数が同じだ。

で、このコンスセルを増やすことなくリスト操作を行うんだから →各コンスセルのcar/cdrの向きを操作すれば良さそうだ →じゃあrplaca/rplacdを使おう →出来上がり

...と書けば短いのに、それに気づくのに結構時間がかかった上、解答後に他の人のコードを見てようやくrotatef/setfの存在に気づいたのはナイショです。

所要時間：(1)1時間(2)50分

しかも効率優先のための破壊的操作なのに無駄に再帰を使ったのもマイナスポイント。

CLの無い端末で作業をしていたのでEmacsLispでコーディング。自宅のubuntu+SBCL 1.0.18+SLIMEでも動作確認しました。今回xyzzy使わなかったな...

	(defun nalist-to-plist (list)
	"連想リストをプロパティリストに変換する[破壊的]."
	(if (null list)
	nil
	(let ((car (car list))
	(cdr (cdr list)))
	(rplaca list (car car))
	(rplacd list car)
	(rplaca (cdr list) (cdr car))
	(rplacd (cdr list) cdr)
	(nalist-to-plist (nthcdr 2 list))
	list)))

	(nalist-to-plist '((foo . 1) (bar . 2) (baz . 3)))
	;;=> (foo 1 bar 2 baz 3)

	(prog ((data (loop :repeat 10000 :collect (cons 1 2))))
	(time (nalist-to-plist data)))
	;;=> NIL
	#\|
	Evaluation took:
	0.001 seconds of real time
	0.000000 seconds of total run time (0.000000 user, 0.000000 system)
	0.00% CPU
	853,799 processor cycles
	0 bytes consed
	~~~~~~~~~~~~~~
	\|#

	(defun nplist-to-alist (list)
	"プロパティリストを連想リストに変換する[破壊的]."
	(if (null (cdr list))
	nil
	(let ((x (car list))
	(y (car (cdr list))))
	(rplaca list (cdr list))
	(rplacd list (cdr (cdr list)))
	(rplaca (car list) x)
	(rplacd (car list) y)
	(nplist-to-alist (cdr list))
	list)))

	(nplist-to-alist '(foo 1 bar 2 baz 3))
	;;=> ((foo . 1) (bar . 2) (baz . 3))

	(prog ((data (loop :repeat 100000 :collect (cons 1 2))))
	(time (nplist-to-alist data)))
	;;=> NIL
	#\|
	Evaluation took:
	0.006 seconds of real time
	0.004000 seconds of total run time (0.004000 user, 0.000000 system)
	66.67% CPU
	7,906,917 processor cycles
	0 bytes consed
	~~~~~~~~~~~~~~
	\|#