--.--
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

10.03
Wed
ぶろぐ更新できない〜〜。テスト期間中のもらとりです〜〜

クイックソートでピボットのとり方を変えて速さを確かめるテストです

一万個の要素のリストを並び替えます。

(defun grls (num lst &optional (func '<))
	(if (null lst)
		nil
		(if (funcall func num (car lst))
			(cons (car lst) (grls num (cdr lst) func))
			(grls num (cdr lst) func)
		)
	)
)
(defun repeat (atm n)
	(if (= n 0)
		nil
		(cons atm (repeat atm (- n 1)))
	)
)
(defun quicksort (lst where)
	(if (null lst)
		nil
		(let ((pivot(funcall where lst)))
			(append 
				(quicksort (grls pivot lst '>) where)
				(repeat pivot (count pivot lst)) 
				(quicksort (grls pivot lst '<) where)
			)
		)
	)
)

(defun make-randomlst (size maxval)
	(if (= size 0)
		nil
		(cons (random maxval) (make-randomlst (- size 1) maxval))
	)
)


(defun compare nil
	(let (
			(rndmlst (make-randomlst 10000 10001))
			(aorderlst (loop for x to 9999 by 1 collect x))
			(symmlst (append (loop for x to 4999 by 1 collect x) (reverse (loop for x to 4999 by 1 collect x))))
		 	
		 )
		(format t "#RANDOM LIST~%")
		(format t "----PIVOT IS HEAD  ----~%")
		(time (quicksort rndmlst 'car))
		(format t "----PIVOT IS RANDOM----~%")
		(time (quicksort rndmlst (lambda (lst)(car(nthcdr(random (length lst))lst)))))
		(format t "----PIVOT IS MIDDLE----~%")
		(time (quicksort rndmlst (lambda (lst)  (car (nthcdr (floor (/ (length lst) 2))lst)))))
		(format t "~%~%")
		
		(format t "#ASCENDING ORDER LIST~%")
		(format t "----PIVOT IS HEAD  ----~%")
		(time (quicksort aorderlst 'car))
		(format t "----PIVOT IS RANDOM----~%")
		(time (quicksort aorderlst (lambda (lst)(car(nthcdr(random (length lst))lst)))))
		(format t "----PIVOT IS MIDDLE----~%")
		(time (quicksort aorderlst (lambda (lst)  (car (nthcdr (floor (/ (length lst) 2))lst)))))
		(format t "~%~%")

		(format t "#SYMMETRY LIST~%")
		(format t "----PIVOT IS HEAD  ----~%")
		(time (quicksort symmlst 'car))
		(format t "----PIVOT IS RANDOM----~%")
		(time (quicksort symmlst (lambda (lst)(car(nthcdr(random (length lst))lst)))))
		(format t "----PIVOT IS MIDDLE----~%")
		(time (quicksort symmlst (lambda (lst)  (car (nthcdr (floor (/ (length lst) 2))lst)))))
		
		(format t "~%~%")
	)
)

(compare)


(ピボットを基準にリストを分割する際に分けたリストの要素の数が半分こずつぐらいになると速いのかなぁーたぶん)

ねむい
スポンサーサイト

comment 0 trackback 0
トラックバックURL
http://telracsmoratori.blog.fc2.com/tb.php/142-2379bd35
トラックバック
コメント
管理者にだけ表示を許可する
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。