Algorithms in a Nutshell

(^332) | Appendix: Benchmarking
ThelargeAddfunction from Example A-8 adds together a set of n numbers. The
output generated by(briefReport largeAdd millionplus 30 1000000 5000000)is
shown in Table A-2.
(cons (result f probSize)
(trials f (- numTrials 1) probSize))))
;; Generate an individual line of the report table for problem size
(define (smallReport f numTrials probSize)
(let ((results (trials f numTrials probSize))
(reduced (remove-number
(remove-number results (find-min results))
(find-max results))))
(display (list 'probSize: probSize
'numTrials: numTrials
(average reduced)))
(newline)))
;; Generate a full report for specific function f by incrementing
;; one to the problem size
(define (briefReport f inc numTrials minProbSize maxProbSize)
(if (>= minProbSize maxProbSize)
(smallReport f numTrials minProbSize)
(begin
(smallReport f numTrials minProbSize)
(briefReport f inc numTrials (inc minProbSize) maxProbSize))))
;; standard doubler and plus1 functions for advancing through report
(define (double n) ( 2 n))
(define (plus1 n) (+ 1 n))
Example A-8. largeAdd Scheme function
;; helper method
(define (millionplus n) ( + 1000000 n))
;; Sum numbers from 1..probSize
(define (largeAdd probSize)
(let loop ([i probSize]
[total 0])
(if (= i 0)
total
(loop (sub1 i) (+ i total)))))
Table A-2. Execution time for 30 trials of largeAdd
n Execution time (ms)
1,000,000 382.09
2,000,000 767.26
3,000,000 1155.78
4,000,000 1533.41
5,000,000 1914.78
Example A-7. Timing Scheme code (continued)
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use