[racket] Filling number

From: Danny Yoo (dyoo at hashcollision.org)
Date: Fri Sep 28 16:38:39 EDT 2012

> It is also possible to use build-string, without using explicit recursion:
> (define (string->mformat str n filler)
>   (string-append
>    (build-string (max 0 (- n (string-length str)))
>                  (lambda (x) filler))
>    str))


Hi Laurent,

I like this one much more because it won't have the quadratic behavior
that the first solution will exhibit on sufficiently large n.


It's neat to see how the two compare in terms of time.  Here's a small
test program:

###########################
#lang racket

;; string->mformat-1: string number char -> string
(define (string->mformat-1 str n filler)
  (if (equal? (string-length str) n)
      str
      (string->mformat-1 (string-append (string filler) str)
                         n
                         filler)))

;; string->mformat-2: string number char -> string
(define (string->mformat-2 str n filler)
  (string-append
   (build-string (max 0 (- n (string-length str)))
                 (lambda (x) filler))
   str))


;; test: number -> void
;; Just show how the two functions compare.
(define (test n)
  (printf "trial ~a\n" n)
  (displayln "1:")
  (time (void (string->mformat-1 "foo" n #\0)))
  (displayln "2:")
  (time (void (string->mformat-2 "foo" n #\0)))
  (newline))


(for ([n '(10 100 1000 10000 100000)])
  (test n))
###########################



We'll compare the two versions to see how they perform.  Here's what I
see on my machine:


###########################
trial 10
1:
cpu time: 0 real time: 0 gc time: 0
2:
cpu time: 0 real time: 0 gc time: 0

trial 100
1:
cpu time: 0 real time: 0 gc time: 0
2:
cpu time: 0 real time: 0 gc time: 0

trial 1000
1:
cpu time: 0 real time: 0 gc time: 0
2:
cpu time: 0 real time: 0 gc time: 0

trial 10000
1:
cpu time: 141 real time: 152 gc time: 78
2:
cpu time: 1 real time: 0 gc time: 0

trial 100000
1:
cpu time: 20866 real time: 22001 gc time: 8670
2:
cpu time: 2 real time: 2 gc time: 0
###########################


We can see that the performance of string->mformat-1 starts to falter
as n grows.  The string->mformat-2 function is better because it does
not repeatedly use string-append on the accumulated result.

Posted on the users mailing list.