home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / usr.bin / lisp / lispnews / text0197.txt < prev    next >
Encoding:
Text File  |  1985-11-10  |  1.7 KB  |  72 lines
  1.  
  2. Somewhat bizzarely it seems that Franz Lisp sort and sortcar have
  3. different time complexities. sort is good and sortcar is bad so
  4. I suggest you convert your sortcar's to sort's until someone sorts
  5. this out. The code and transcript below use both sort and sortcar
  6. to sort a list of length n (the list happens to start in precisely
  7. reverse order). A count of the number of calls to the comparison
  8. function is kept. The results show that sort takes n*log(n)
  9. comparisons while sortcar takes n*n. The problem should
  10. be fixable by throwing out code as there must be two sorters lurking
  11. in there!
  12.  
  13. ;;;;;;;;;;;;;;;
  14.  
  15. (defun gen (n)
  16.     (do ((i 0 (1+ i))
  17.      (l () (cons (cons i ()) l)))
  18.     ((= i n)
  19.      l)))
  20.  
  21. (defun compare (x y)
  22.     (setq *count* (1+ *count*))
  23.     (< x y))
  24.  
  25. (defun compare-cars (x y) (compare (car x) (car y)))
  26.  
  27. (defun count-sort (n)
  28.     (let ((*count* 0))
  29.      (sort (gen n) #'compare-cars)
  30.      *count*))
  31.  
  32. (defun count-sortcar (n)
  33.     (let ((*count* 0))
  34.      (sortcar (gen n) #'compare)
  35.      *count*))
  36.  
  37. (defun test (n)
  38.     (let ((csort (count-sort n))
  39.       (csortcar (count-sortcar n)))
  40.      (list n
  41.            csort
  42.            csortcar
  43.            (/$ (float csort) (*$ (float n) (log n)))
  44.            (/$ (float csortcar) (float (* n n))))))
  45.  
  46. ;;;;;;;;;;;;;;;
  47.  
  48. Here's the transcript. The lists of 5 elements are:
  49.     n
  50.     compares for sort
  51.     compares for sortcar
  52.     compares for sort / n*log(n)
  53.     compares for sortcar / n*n
  54.  
  55.  
  56. Franz Lisp, Opus 38
  57. -> (load 'test)
  58. t
  59. -> (test 3)
  60. (3 3 6 0.910239226626837 0.6666666666666667)
  61. -> (test 100)
  62. (100 460 9900 0.9988773083774791 0.99)
  63. -> (test 200)
  64. (200 1020 39800 0.9625697456705496 0.995)
  65. -> (test 300)
  66. (300 1440 89700 0.8415468193831012 0.9966666666666667)
  67. -> (test 400)
  68. (400 2240 159600 0.9346629619469353 0.9975)
  69. -> 
  70.  
  71.  
  72.