> On Dec 31, 2016, at 10:57 AM, Matthew Butterick <m...@mbtype.com> wrote:
>
>> I started with Ryan's code from `~r` and tried to emulate some special
>> cases I see the C code (and didn't worry about negative numbers) and
>> ended up with something 4-5x slower than the C code version. :( Code
>> follows.
>
>
> Is it cheating to avoid divisions by using table lookups?
Whoops, my `test-it` macro had a typo in it. Here are results for different
number lengths.
; convert 123
cpu time: 893 real time: 925 gc time: 21 ; number->string
cpu time: 3306 real time: 3376 gc time: 74 ; number->string* (Findler
algorithm)
cpu time: 583 real time: 614 gc time: 26 ; number->string** (table
lookup)
; convert 123456
cpu time: 1393 real time: 1433 gc time: 38 ; number->string
cpu time: 5474 real time: 5544 gc time: 86 ; number->string* (Findler
algorithm)
cpu time: 1325 real time: 1423 gc time: 79 ; number->string** (table
lookup)
; convert 123456789
cpu time: 1950 real time: 1980 gc time: 46 ; number->string
cpu time: 7835 real time: 7882 gc time: 97 ; number->string* (Findler
algorithm)
cpu time: 2293 real time: 2532 gc time: 174 ; number->string** (table
lookup)
;;;;;;;;;;;;;;;;;;;;;;
#lang racket
(define (number->string* N)
(cond [(zero? N)
(string #\0)]
[else
(let* ([short-size 10]
[str (make-string short-size)])
(let loop ([N N] [digits null] [i short-size])
(cond
[(zero? N)
(if (<= i 0)
(if (null? digits)
str
(string-append (apply string digits) str))
(substring str i short-size))]
[else
(define-values (q r) (quotient/remainder N 10))
(define d (integer->char (+ r (char->integer #\0))))
(cond
[(<= i 0)
(loop q (cons d digits) i)]
[else
(string-set! str (- i 1) d)
(loop q '() (- i 1))])])))]))
(define-syntax-rule (digit-vector id ...)
(for*/vector ([id (in-range 10)] ...)
(append (string->list (number->string id)) ...)))
(define number->string**
(let ([digits (digit-vector i)]
[double-digits (digit-vector i j)]
[triple-digits (digit-vector i j k)])
(λ (N)
(list->string
(let loop ([N N])
(cond
[(< N 10) (vector-ref digits N)]
[(< N 100) (vector-ref double-digits N)]
[(< N 1000) (vector-ref triple-digits N)]
[else
(append (loop (quotient N 1000))
(vector-ref triple-digits (remainder N 1000)))]))))))
(define-syntax-rule (test-it id ...)
(begin
(module+ test
(require rackunit)
(check-equal? (id 1234567890987654321)
(number->string 1234567890987654321))
(for ([x (in-range 10000)])
(check-equal? (id x )
(number->string x)))) ...))
(test-it number->string* number->string**)
(define iterations 10000000)
(define-syntax-rule (time-it number-to-convert id ...)
(begin
(begin
(collect-garbage)
(time
(for ([x (in-range iterations)])
(id number-to-convert)))) ...))
(time-it 123 number->string number->string* number->string**)
(time-it 123456 number->string number->string* number->string**)
(time-it 123456789 number->string number->string* number->string**)
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
