[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: string-map arg order

From: Alex Shinn
Subject: Re: string-map arg order
Date: 06 Sep 2001 13:16:08 -0400
User-agent: Gnus/5.0808 (Gnus v5.8.8) Emacs/21.0.104

>>>>> "Dirk" == Dirk Herrmann <address@hidden> writes:

    >> Note that we can also use this same approach when resizing utf8
    >> strings, so we can get back the O(n) time on string-for-each
    >> and kin.  Thanks for pointing that out :)

    Dirk> Sorry, no :-) Look at the following pseudo code that runs in
    Dirk> a single-threaded guile and tell me how you would implement
    Dirk> string-for-each in O(n) with a multi byte encoding...

    Dirk>  (define s <some string>)
    Dirk>  (define (foo c)
    Dirk>    (string-set! s (random-index (length s)) (random-character)))
    Dirk>  (string-for-each foo s)

Well, the looping of string-for-each is O(n)... in your example, the
inside of the loop happens to be an O(n) computation (in a style we
would have to make clear is inefficient).

When I said string-for-each is O(n), I meant the overhead involved, I
did not mean you could magically write

(string-for-each (lambda (x) (some-huge-computation-of x)) str)

and always get it to run in O(n) time :)

Alex Shinn <address@hidden>

reply via email to

[Prev in Thread] Current Thread [Next in Thread]