> On Jan 4, 2017, at 1:49 PM, Robby Findler <ro...@eecs.northwestern.edu> wrote: > > Is changing the alphabet something that can be done post-facto with > string replacements?
Could there be a more general list-of-digits->number that could work with any base? (list-of-digits->number (list 50 73) 90) ;=> 4573 Then using an arbitrary alphabet could work by replacing numbers within a list instead of finding sequences within a string, which sounds much more hacky. Alex Knauth > Robby > > On Wed, Jan 4, 2017 at 12:46 PM, Deren Dohoda <deren.doh...@gmail.com> wrote: >> Some food for thought on this topic, I use base conversion for all sorts of >> silly things. To this end I require a great deal of flexibility in >> representation. When I wrote my continued-fractions package I included this >> as a separate module. Here's an example: >> >> Welcome to DrRacket, version 6.7 [3m]. >> Language: racket/base, with debugging [custom]; memory limit: 2048 MB. >>> (require continued-fractions/bases) >> >> (define rep (make-representation #:radix #\! >> #:negate #\+ >> #:terms >> "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ")) >> >> (parameterize ((representation rep) >> (digits 10)) >> (let ((n (/ -125382661425156036913657 101559956668416))) >> (let ((s (->string n))) >> (displayln s) >> (let ((n* (->number s))) >> (= n n*))))) >> +KF12OI!4FZZZXRSP >> #t >>> >> >> This may be pointlessly more flexible than a normal user of number->string >> would want but an arbitrary alphabet is something I'd request people >> consider for a few moments if changing number->string is open for debate. >> Maybe it is too much flexibility for racket/base, though, which is where >> number->string lives. >> >> Deren >> >> On Wed, Jan 4, 2017 at 11:38 AM, Gustavo Massaccesi <gust...@oma.org.ar> >> wrote: >>> >>> I'm still worried about bignums. So I borrowed the idea of Mathew of >>> splitting the number in 1/2/3 digits chucks, but I use fixnum chunks. >>> For each fixnum chunk I calculate the string representation as usual, >>> but as most of the calculations involve only fixnum, then It's x4 >>> faster for bignums. >>> >>> It's slightly slower for the DrRacket distribution and fixnums and >>> (5%-10%). >>> >>> The code assumes that a 999999999 is a fixnum, this is true for 32 and >>> 64 bit's racket. (In case Racket is ported in the future to a 16 bits >>> platform, the code is still correct but slower.) >>> >>> DrRacket distribution of numbers >>> number->string cpu time: 4907 real time: 4898 gc time: 77 >>> number->string* cpu time: 3703 real time: 3701 gc time: 0 >>> number->string** cpu time: 6782 real time: 6777 gc time: 16 >>> number->string*** cpu time: 3797 real time: 3796 gc time: 16 >>> >>> Always N=123 (10 times less calls) >>> number->string cpu time: 859 real time: 846 gc time: 0 >>> number->string* cpu time: 1688 real time: 1676 gc time: 31 >>> number->string** cpu time: 672 real time: 673 gc time: 0 >>> number->string*** cpu time: 1796 real time: 1800 gc time: 0 >>> >>> Always N=1234567890123456789012345678901234567890 (10 times less calls) >>> number->string cpu time: 5625 real time: 5623 gc time: 0 >>> number->string* cpu time: 102125 real time: 102100 gc time: 403 >>> number->string** cpu time: 750 real time: 748 gc time: 15 >>> number->string*** cpu time: 26343 real time: 26337 gc time: 95 >>> >>> Gustavo >>> >>> ;Here is ony the code of the new function and benchmarks >>> ;I'm not happy with the names of the auxiliary functions. >>> >>> (define (number->string***/fixed N short-size trim) >>> (define str (make-string short-size #\0)) >>> (let loop ([N N] [i short-size]) >>> (cond >>> [(zero? N) >>> (if trim >>> (substring str i short-size) >>> str)] >>> [else >>> (define q (quotient N 10)) >>> (define r (remainder N 10)) >>> (define d (integer->char (+ r (char->integer #\0)))) >>> (string-set! str (- i 1) d) >>> (loop q (- i 1))]))) >>> >>> (define (number->string***/bignum/list N tail) >>> (define-values (q r) (quotient/remainder N (expt 10 9))) >>> (cond >>> [(zero? q) >>> (cons (number->string***/fixed r 9 #t) tail)] >>> [else >>> (number->string***/bignum/list q (cons (number->string***/fixed r >>> 9 #f) tail))])) >>> >>> (define (number->string*** N) >>> (cond >>> [(fixnum? N) >>> (cond >>> [(< N 10) >>> (string (integer->char (+ (char->integer #\0) N)))] >>> [(< N (expt 10 9)) >>> (number->string***/fixed N 9 #t)] >>> [else >>> (apply string-append (number->string***/bignum/list N '()))])] >>> [else >>> (apply string-append (number->string***/bignum/list N '()))])) >>> >>> ;(define-syntax-rule (test-it id ...) ...) >>> >>> (define iterations 50000) >>> >>> (define-syntax-rule (time-it id ...) >>> (begin >>> (define numbers (for/list ([i (in-range 1000)]) >>> (sample/drr))) >>> (begin >>> (collect-garbage) >>> (time >>> (for* ([x (in-range iterations)] >>> [n (in-list numbers)]) >>> (id n)) >>> (printf "~a " 'id))) ...)) >>> >>> (time-it number->string number->string* number->string** >>> number->string***) >>> >>> (define-syntax-rule (time-it-N N id ...) >>> (begin >>> (begin >>> (collect-garbage) >>> (time >>> (for* ([x (in-range (* 100 iterations))]) >>> (id N)) >>> (printf "~a " 'id))) ...)) >>> >>> (time-it-N 123 number->string number->string* number->string** >>> number->string***) >>> (time-it-N 1234567890123456789012345678901234567890 number->string >>> number->string* number->string** number->string***) >>> ;--- >>> >>> >>> On Sun, Jan 1, 2017 at 8:01 PM, Robby Findler >>> <ro...@eecs.northwestern.edu> wrote: >>>> I'm skeptical of an unbounded cache. >>>> >>>> If we go by the sample from DrRacket's start up, then we don't really >>>> need a cache to do better than the built-in number->string. Below is >>>> some code that takes the version I had earlier with what I understood >>>> to be Gustavo's suggestions and then just does better on the fixnums >>>> between 0 and 9. I then changed the random inputs to sample from the >>>> distribution that DrRacket demonstrated and you won't be surprised to >>>> learn that this does better than having a cache. Below is the code. >>>> >>>> I also tried to collect the arguments to number->string during >>>> rebuilding all of the .zo files. Of the first 2.3 million calls about >>>> 99.5% of them were exact integers between 0 and 9 so probably this is >>>> the only optimization we need to do. (My sampling method turned out to >>>> be noisy, tho, but I don't think it affects the results.) >>>> >>>> ... unless someone comes up with some other benchmark or app we care >>>> about? >>>> >>>> Robby >>>> >>>> #lang racket >>>> (require (for-syntax syntax/parse)) >>>> >>>> (define-syntax (mk-sample stx) >>>> (syntax-parse stx >>>> [(_ (value:exact-nonnegative-integer >>>> occurrences:exact-nonnegative-integer) ...) >>>> (define-values (cond-clauses count) >>>> (for/fold ([other-cases '()] >>>> [so-far 0]) >>>> ([value (in-list (syntax->list #'(value ...)))] >>>> [occurrences (in-list (syntax->list #'(occurrences >>>> ...)))]) >>>> (define next-count (+ so-far (syntax-e occurrences))) >>>> (values (cons #`[(< x #,next-count) #,value] other-cases) >>>> next-count))) >>>> #`(λ () >>>> (define x (random #,count)) >>>> (cond #,@(reverse cond-clauses)))])) >>>> >>>> (define sample/drr >>>> (mk-sample >>>> (0 2399) >>>> (1 8116) >>>> (2 4278) >>>> (3 2196) >>>> (4 1346) >>>> (5 901) >>>> (6 364) >>>> (7 230) >>>> (8 106) >>>> (9 96) >>>> (10 42) >>>> (11 5) >>>> (12 3) >>>> (72 1) >>>> (100 34) >>>> (241 1))) >>>> >>>> (define number->string** >>>> (let ([digits (list->vector (string->list "0123456789"))] >>>> [cache (make-hasheqv)]) >>>> (λ (N) >>>> (hash-ref! cache N >>>> (λ () >>>> (list->string >>>> (let loop ([N N][acc empty]) >>>> (define q (quotient N 10)) >>>> (define next-acc (cons (vector-ref digits >>>> (remainder N 10)) acc)) >>>> (if (zero? q) >>>> next-acc >>>> (loop q next-acc))))))))) >>>> >>>> >>>> (define (number->string* N) >>>> (cond [(and (exact-nonnegative-integer? N) (< N 10)) >>>> (string (integer->char (+ (char->integer #\0) N)))] >>>> [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 q (quotient N 10)) >>>> (define r (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 (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**) >>>> (test-it number->string*) >>>> >>>> (define iterations 10000) >>>> >>>> (define-syntax-rule (time-it id ...) >>>> (begin >>>> (define numbers (for/list ([i (in-range 1000)]) >>>> (sample/drr))) >>>> (begin >>>> (collect-garbage) >>>> (time >>>> (for* ([x (in-range iterations)] >>>> [n (in-list numbers)]) >>>> (id n)) >>>> (printf "~a " 'id))) ...)) >>>> >>>> (time-it 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. >>> >>> -- >>> 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. >> >> > > -- > 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. -- 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.
