Hello,
> From: Daniel Hartwig <mand...@gmail.com>
>
> 2013/4/1 Nala Ginrut <nalagin...@gmail.com>:
>> I've tried to implement a function to mimic string multiply like Python:
>> "asdf" * 10
>>
>> --------------code----------------
>> (define (str* str n)
>> (format #f "~{~a~}" (make-list n str)))
>>
>> or
>>
>> (define (str* str n)
>> (string-join (make-list n str) ""))
>> --------------end-----------------
> Those are both very general mechanisms, it does not suprise me that
> they are less than efficient for very large N. Although I can not
> comment whether this is a worthwhile issue to address, I offer this
> snippet as a hint of something perhaps better for your specific case:
>
> (define (str* str n)
> (call-with-output-string
> (lambda (p)
> (let lp ((n n))
> (unless (zero? n)
> (display str p)
> (lp (1- n)))))))
>
> Out of curiousity, how does the performance figures you showed compare
> to the Python operator for similarly large values of N?
I attempted a method that I thought should surely be faster using
https://gitorious.org/guile-ploy
(import (util ploy))
(define str*-as-array (lambda (s n) (ravel (reshape s n (string-length s)))))
ravel is essentially
(define (ravel a)
(or (array-contents a) (array-contents (array-copy (array-type a) a))))
reshape is more complicated but in this particular case it resolves to
make-shared-array, so it's O(1). Here's a full trace:
scheme@(guile-user)> ,trace (string-length (str*-as-array "1234567890" 1000000))
trace: | (#<procedure 117ac0d60> #(#<directory (guile-user) 114aebcf0> #f #f
#f))
trace: | #(#<directory (guile-user) 114aebcf0> string-length str*-as-array
"1234567890")
trace: (#<procedure 117ad8980 at <current input>:4:0 ()>)
trace: | (str*-as-array "1234567890" 1000000)
trace: | | (string-length "1234567890")
trace: | | 10
trace: | | (reshape "1234567890" 1000000 10)
trace: | | | (array? "1234567890")
trace: | | | #t
trace: | | | ($ "1234567890")
trace: | | | | (array? "1234567890")
trace: | | | | #t
trace: | | | (array-dimensions "1234567890")
trace: | | | (10)
trace: | | | (reverse (10))
trace: | | | (10)
trace: | | | (reverse (1000000 10))
trace: | | | (10 1000000)
trace: | | (make-shared-array "1234567890" #<procedure 11770fa40 at
util/ploy.scm:385:22 i> 1000000 10)
trace: | | | (#<procedure 11770fa40 at util/ploy.scm:385:22 i> 0 0)
trace: | | | | (length (1000000))
trace: | | | | 1
trace: | | | (list-tail (0 0) 1)
trace: | | | (0)
trace: | | | (#<procedure 11770fa40 at util/ploy.scm:385:22 i> 0 1)
trace: | | | | (length (1000000))
trace: | | | | 1
trace: | | | (list-tail (0 1) 1)
trace: | | | (1)
trace: | | | (#<procedure 11770fa40 at util/ploy.scm:385:22 i> 1 1)
trace: | | | | (length (1000000))
trace: | | | | 1
trace: | | | (list-tail (1 1) 1)
trace: | | | (1)
trace: | (ravel #)
trace: | | (array-contents #)
trace: | | #f
trace: | | (array-type* #)
trace: | | | (array? #)
trace: | | | #t
trace: | | (array-type #)
trace: | | a
trace: | | (array-copy a #)
trace: | | | (make-array-of-size # a)
trace: | | | | ($ #)
trace: | | | | | (array? #)
trace: | | | | | #t
trace: | | | | (array-dimensions #)
trace: | | | | (1000000 10)
trace: | | | (make-typed-array a #<unspecified> 1000000 10)
trace: | | | #
trace: | | | (array-copy! # #)
trace: | | | #<unspecified>
trace: | | #
trace: | (array-contents #)
trace: |
"12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678…"
trace: (string-length
"123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234…")
trace: 10000000
It is in fact quite slower than your solution using call-with-output-string +
display:
scheme@(guile-user)> ,time (string-length (str* "1234567890" 1000000))
$4 = 10000000
;; 0.528000s real time, 0.530000s run time. 0.000000s spent in GC.
scheme@(guile-user)> ,time (string-length (str*-as-array "1234567890" 1000000))
$5 = 10000000
;; 1.745000s real time, 1.750000s run time. 0.000000s spent in GC.
scheme@(guile-user)>
The profile is interesting, I think:
scheme@(guile-user)> ,profile (string-length (str*-as-array "1234567890"
1000000))
% cumulative self
time seconds seconds name
100.00 1.74 1.74 make-typed-array
0.00 1.74 0.00 call-with-prompt
0.00 1.74 0.00 start-repl
0.00 1.74 0.00 catch
0.00 1.74 0.00 #<procedure 1161a37c0 at ice-9/top-repl.scm:31:6
(thunk)>
0.00 1.74 0.00 apply-smob/1
0.00 1.74 0.00 run-repl
0.00 1.74 0.00 statprof
0.00 1.74 0.00 array-copy
0.00 1.74 0.00 #<procedure 117762d80 at statprof.scm:655:4 ()>
0.00 1.74 0.00 #<procedure 117b05e80 at <current input>:5:0 ()>
0.00 1.74 0.00 ravel
0.00 1.74 0.00 #<procedure 1161a36c0 at ice-9/top-repl.scm:66:5 ()>
How can it be slower to allocate the result at once?
