mx.sx 3701

(defun insert-sort (list element)
  "Contestant 1: Insert element into list, then sort"
  (sort (cons element list) #'<)
  )

(defun insert-linear (list element)
  "Contestant 2: Scan sorted list linearly and insert element in order"
  (cond
   ((null list) (cons element list))
   ((<= element (car list)) (cons element list))
   (t
    (let ((tail list) (prev nil))

      (while (and tail (> element (car tail)))
        (setq prev tail)
        (setq tail (cdr tail)))

      (setq tail (cons element tail))

      (if prev (setcdr prev tail))

      list))))

(defun bsearch (list target)
  "Binary search list and return the insertion point for target"
  (let ((left 0)
        (right (length list))
        (mid (/ (length list) 2)))
    (while (and (< left (- right 1))
                (/= target (elt list mid)))

      (if (< target (elt list mid))
          (setq right mid)
        (setq left (+ mid 1)))

      (setq mid (/ (+ left right) 2)))

    (cond ((= left right) right)
          ((= target (elt list mid)) mid)
          (t; (= left (- right 1)
           (if (<= target (elt list left))
                  left
                right)))))

(defun insert-element-at (list element index)
  "Insert element at position index in list"
  (push element (nthcdr index list))
  list)

(defun insert-bsearch (list element)
  "Contestant 3: Binary search list for element's position and insert it there"
  (insert-element-at list element (bsearch list element)))

(defmacro measure-time (&rest body)
  `(let ((time (current-time)))
     ,@body
     (message "%.06f" (float-time (time-since time)))))

(defconst test-limit 30000)

(defconst random-list
  (let (mylist '())
    (dotimes (i test-limit) (push (random test-limit) mylist))
    mylist))

(defun time-many-random-inserts (insert-func)
  "Run a dumb test with a bunch of inserts"
  (let ((mylist '())
        (tmplist random-list))
    (measure-time
     (dotimes (i test-limit)
       (setq mylist (funcall insert-func mylist (car tmplist)))
       (setq tmplist (cdr tmplist)))
     )))

(defun time-many-tail-inserts (insert-func)
  "Run a dumb test with a bunch of inserts"
  (let (mylist '())
    (measure-time
     (dotimes (i test-limit) (setq mylist (funcall insert-func mylist i)))
     )))


;; (time-many-tail-inserts 'insert-sort)        ; 116.420000
;; (time-many-tail-inserts 'insert-linear)      ;  20.421000
;; (time-many-tail-inserts 'insert-bsearch)     ;  24.112000

;; (time-many-random-inserts 'insert-sort)      ; 126.393000
;; (time-many-random-inserts 'insert-linear)    ;  10.346000
;; (time-many-random-inserts 'insert-bsearch)   ;  38.448000