[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

# Don't use Franz sortcar!

• To: franz-friends@Berkeley
• Subject: Don't use Franz sortcar!
• From: Rod Brooks <ROD@SU-AI.ARPA>
• Date: Sat, 17 Mar 84 21:47:00 GMT
• Original-date: 17 Mar 84 1347 PST

```Somewhat bizzarely it seems that Franz Lisp sort and sortcar have
different time complexities. sort is good and sortcar is bad so
I suggest you convert your sortcar's to sort's until someone sorts
this out. The code and transcript below use both sort and sortcar
to sort a list of length n (the list happens to start in precisely
reverse order). A count of the number of calls to the comparison
function is kept. The results show that sort takes n*log(n)
comparisons while sortcar takes n*n. The problem should
be fixable by throwing out code as there must be two sorters lurking
in there!

;;;;;;;;;;;;;;;

(defun gen (n)
(do ((i 0 (1+ i))
(l () (cons (cons i ()) l)))
((= i n)
l)))

(defun compare (x y)
(setq *count* (1+ *count*))
(< x y))

(defun compare-cars (x y) (compare (car x) (car y)))

(defun count-sort (n)
(let ((*count* 0))
(sort (gen n) #'compare-cars)
*count*))

(defun count-sortcar (n)
(let ((*count* 0))
(sortcar (gen n) #'compare)
*count*))

(defun test (n)
(let ((csort (count-sort n))
(csortcar (count-sortcar n)))
(list n
csort
csortcar
(/\$ (float csort) (*\$ (float n) (log n)))
(/\$ (float csortcar) (float (* n n))))))

;;;;;;;;;;;;;;;

Here's the transcript. The lists of 5 elements are:
n
compares for sort
compares for sortcar
compares for sort / n*log(n)
compares for sortcar / n*n

Franz Lisp, Opus 38
-> (load 'test)
t
-> (test 3)
(3 3 6 0.910239226626837 0.6666666666666667)
-> (test 100)
(100 460 9900 0.9988773083774791 0.99)
-> (test 200)
(200 1020 39800 0.9625697456705496 0.995)
-> (test 300)
(300 1440 89700 0.8415468193831012 0.9966666666666667)
-> (test 400)
(400 2240 159600 0.9346629619469353 0.9975)
->

```