We have learned:
set!command to mutate variable values
beginto evaluate a sequence of expressions, rather than a single expression
We have applied these new mechanisms on problems of traffic lights, and address book management.
Following are the code for insertion sort and merge sort algorithms we have developed before. We now want to compare running time performances of the two sorting methods.
;;; CREATE RANDOM LIST ;Function n:number k:number -> list ;Returns a list of size n, containin random numbers each between 0 and k (define (makeRandomList n k) (cond ((or (< n 0) (< k 0)) (error "invalid input")) ((= n 0) empty) (else (cons (random k) (makeRandomList (- n 1) k))))) ;;; INSERTION SORT ;Function number ascending-sorted-list -> sorted-list ;Returns a version of the list where the vlue is inserted in proper order (define (insert value sortedList) (cond ((empty? sortedList) (cons value empty)) ((< value (first sortedList)) (cons value sortedList)) (else (cons (first sortedList) (insert value (rest sortedList)))))) ;Function list ascending-sorted-list -> sorted-list ;returns a list obtained by inserting each of the values in the list into sorted list in proper order (define (insertAll unsortedList sortedList) (cond ((empty? unsortedList) sortedList) (else (insertAll (rest unsortedList) (insert (first unsortedList) sortedList))))) (define (insertionSorter unsortedList) (insertAll unsortedList empty)) ;;;MERGE SORT ;Function that splits the given list into two equal size halves (define (split list) (splitAccumulator empty empty list)) ;helper function (define (splitAccumulator half1 half2 originalList) (cond ((empty? originalList) (list half1 half2)) (else (splitAccumulator half2 (cons (first originalList) half1) (rest originalList))))) (define (sortHalvesHelper halves) (list (merge-sort (first halves)) (merge-sort (first (rest halves))))) (define (mergeHalvesHelper halves) (mergeHalves (first halves) (first (rest halves)))) (define (mergeHalves half1 half2) (cond ((empty? half1) half2) ((empty? half2) half1) ((< (first half1) (first half2)) (cons (first half1) (mergeHalves (rest half1) half2))) (else (cons (first half2) (mergeHalves half1 (rest half2)))))) (define (merge-sort unsorted) (cond ((or (empty? unsorted) (empty? (rest unsorted))) unsorted) (else (mergeHalvesHelper (sortHalvesHelper (split unsorted))))))
For measuring the time performance, we can use
(current-inexact-milliseconds) function in Racket. For example:
(define startTime (current-milliseconds)) (merge-sort (makeRandomList 1000 1000)) (- (current-milliseconds) startTime)
(define startTime void) (define (sortTimer sortFunction length) (begin (set! startTime (current-milliseconds)) (sortFunction (makeRandomList length 1000)) (- (current-milliseconds) startTime))) (sortTimer merge-sort 1000) (sortTimer insertionSorter 1000)
Use of the global variable named
startTimer is both misplaced and confusing, as apparent in its initialization. What we need instead is mutative variable which is valid within the local scope of the function only. The
local command (somewhat similar to
begin command) provides the mechanism for this:
<exp> = (local (<def-1> ...<def-n>) <exp>)
local function allows you to precede an expression with several variable definitions local to the scope. These variables are created everytime the function is evaluated.
(define (sortTimer sortFunction length) (local ((define startTime (current-milliseconds))) (begin (sortFunction (makeRandomList length 1000)) (- (current-milliseconds) startTime)))) (sortTimer merge-sort 1000) (sortTimer insertionSorter 1000)
Remember that finding the maximum in a list had a double recursion problem, and one needs a helper function to avoid this. Helper functions are a form of "litter" whose presence in the global scope is unnecessary. Thus one can use a local definiton to avoid such a situation. Solve the find-max problem using local definitions.
(define (maxOfList list) (cond ((empty? (rest list)) (first list)) (else (local ((define maxtemp (maxOfList (rest list)))) (cond ((> maxtemp (first list)) maxtemp) (else (first list)))))))
Apply the above pattern to solution of Fibonacci numbers. i.e. write a function which uses a locally defined accumulator.
One can print messages on screen using (printf ...) function in Racket. For example:
or if you want to produce combined messages, by using placeholders ~a, and/or newlines ~n:
(printf "Result of ~a times ~a is ~a ~n" 4 5 (* 4 5))
The following program to compute factorials reports what it is doing:
(define (factorial n) (cond ((< n 0) (error "invalid")) ((<= n 1) 1) (else (begin (printf "Computing factorial of ~a ~n" n) (* n (factorial (- n 1))))))) (check-expect (factorial 4) 24)