またつまらぬものを最適化してしまった

ちょっと、リストを述語でわける関数を考えてみた。

述語が真になるもののリストと、偽になるもののリストを多値で返してみよう。
そう考えたとき、シンプルな実装はこうなるだろう。

(defun divid-if (fn lst)
  (values (remove-if-not fn lst)
	  (remove-if fn lst)))

だが、こんなことをしていては、リスト二回なめるから遅いんじゃないかなと考えちゃう。こういうのは本当はしてはいけないのだが、あそびなので。

ループをひとつにした、再帰版と mapc版をつくってみた。

(defun divid-if-recursive (fn lst)
  (labels ((iter (src trues falses)
	       (if (null src)
		   (values (nreverse trues)
			   (nreverse falses))
		   (if (funcall fn (first src))
		       (iter (rest src) (cons (first src) trues) falses)
		       (iter (rest src) trues (cons (first src) falses))))))
    (iter lst nil nil)))

(defun divid-if-mapc (fn lst)
  (let ((trues nil)
	(falses nil))
    (mapc #'(lambda (x) (if (funcall fn x)
			    (push x trues)
			    (push x falses))) lst)
    (values (nreverse trues) (nreverse falses))))

他にデータ生成用にiotaを作成してみる。

(defun iota (end &optional (begin 1) (step 1))
  (labels ((iter+ (num aux)
	     (if (> num end)
		 (nreverse aux)
		 (iter+ (+ num step) (cons num aux))))
	   (iter- (num aux)
	     (if (< num end)
		 (nreverse aux)
		 (iter- (+ num step) (cons num aux)))))
    (if (<= begin end)
	(iter+ begin nil)
	(iter- begin nil))))

これで、奇数と偶数にわけるテストをしてみよう。

再帰版

(time (divid-if-recursive #'oddp (iota 1000)))
(DIVID-IF-RECURSIVE #'ODDP (IOTA 1000))
took 172 microseconds (0.000172 seconds) to run.
During that period, and with 2 available CPU cores,
97 microseconds (0.000097 seconds) were spent in user mode
81 microseconds (0.000081 seconds) were spent in system mode
32,000 bytes of memory allocated.

mapc 版

(time (divid-if-mapc #'oddp (iota 1000)))
(DIVID-IF-MAPC #'ODDP (IOTA 1000))
took 188 microseconds (0.000188 seconds) to run.
During that period, and with 2 available CPU cores,
107 microseconds (0.000107 seconds) were spent in user mode
85 microseconds (0.000085 seconds) were spent in system mode
32,112 bytes of memory allocated.

たいしてかわらない...

シンプル版

シンプル版はどうか？

(time (divid-if-simple #'oddp (iota 1000)))
(DIVID-IF-SIMPLE #'ODDP (IOTA 1000))
took 68 microseconds (0.000068 seconds) to run.
During that period, and with 2 available CPU cores,
69 microseconds (0.000069 seconds) were spent in user mode
7 microseconds (0.000007 seconds) were spent in system mode
32,000 bytes of memory allocated.

あれれ... そうか1000件くらいじゃかわらないのか。あと、oddp の処理も対して時間かからないし。こういうのを無駄な最適化の害というらしい。

関数	1000個	100000個
愚直	68	13761
再帰	172	10346
mapc	180	15404

かかった時間の単位は microsecond