[racket] Filling number

Good analysis, Danny.
It's mainly due to the linear time required by string-append and maybe
string-length. If there had been a constant-time string-cons, we would have
had linear time.
This can still be done by converting to lists:
(define (string->mformat-3 str n filler)
  (let loop ([l (string->list str)] [len (string-length str)])
    (if (>= len n)
        (list->string l)
        (loop (cons filler l) (add1 len)))))

There is still an overhead though, probably from the conversion from a big
list to a big string:
trial 10000000
2:
cpu time: 348 real time: 347 gc time: 36
3:
cpu time: 4957 real time: 4959 gc time: 3740

Actually, version 3 is in fact in O(n log n) because of the add1 (maybe
also because of len, depending on how it is treated on the loop call).
Version 2 is also probably in O(n log n), but maybe there can be some nice
compilation trick to prevent that.
Although we are of course bounded by the addressable memory space (but
Racket programs are supposed to be independent of that, I think).

Laurent

On Fri, Sep 28, 2012 at 10:38 PM, Danny Yoo <dyoo at hashcollision.org> wrote:

> > 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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120928/8ab381bd/attachment.html>