;; schartzian transform
;; * Sorting by a computed field.
;; * Don't sort the values and compute the field for each
;;   comparison. That involves needless comparisons.
;; * Precompute and sort by the precomputed values:

(use srfi-1)
(use gauche.time)

;; separate operations
(define nums (iota 20 1 1))

(define nums-and-modulos
  (map (lambda (x) (list x (modulo x 4))) nums))

(define sorted-nums-and-modulos
  (sort nums-and-modulos
        (lambda (a b)
          (< (cadr a) (cadr b)))))

(define sorted-nums
  (map car sorted-nums-and-modulos))

;; all operations rolled into one fn
(define (schwartzian sequence computation-fn sort-fn)
  (map car
       (sort (map (lambda (x)
                    (list x (computation-fn x)))
                  sequence)
             (lambda (a b)
               (sort-fn (cadr a) (cadr b))))))

(define expensive-count 0)
(define (expensive x)
  (inc! expensive-count)
  (sys-nanosleep 10000000)             ; sleep 10 ms, or 0.01 s
  (modulo x 4))

(print "starting schwartzian")
(time (print (schwartzian nums expensive <)))
(format #t "expensive fn called ~d times\n" expensive-count)

;; for comparison, the same sort operation that *does* recompute the
;; associated field
(define (recomputing-sort)
  (sort nums
        (lambda (x y)
          (< (expensive x) (expensive y)))))

(print "starting recomputing-sort")
(set! expensive-count 0)
(time (print (recomputing-sort)))
(format #t "expensive fn called ~d times\n" expensive-count)

;; comparison for schwartzian vs. recomputing-sort
;;      schwartzian                  recomputing-sort
;; N    (time-taken expensive-count) (time-taken expensive-count)
;; 10   (0.194 10)                   (1.317 66)
;; 20   (0.394 20)                   (3.916 196)
;; 30   (0.595 30)                   (5.686 284)
;; 40   (0.797 40)                   (8.816 440)
;; 50   (0.998 50)                   (10.956 548)
;; 100  (1.999 100)                  (26.433 1322)
;; 200  (4.017 200)                  (60.073 3004)