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

*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) ->

- Prev by Date:
**Disgusting Copyright Laws** - Next by Date:
**Copyright laws** - Previous by thread:
**Disgusting Copyright Laws** - Next by thread:
**Copyright laws** - Index(es):