Hi John,

Concatenating two ropes together is O(1) if you don't do some kind of balancing, O(log N) if you balance.  You only get O(log n) random access if you balance, O(n) worst-case random access if you don't.  It's similar to a binary tree, in that the "key" is the length of the left sub-rope, and you subtract the node key from the lookup key if you go to the right sub-rope on a node.  Unbalanced binary trees have O(1) insertion but O(n) worst case random access, balanced binary trees have O(log N) insertion and O(log N) worst case random access.

Note that this depends on what you use ropes for.  You can live with unbalanced ropes if you're just using it to batch up concatenations until somebody performs random access on the string - it will amortize some of the cost of having a loop that may concatenate at the start or end of a string, which may be idiomatic for particular languages or programming styles.  Consider:

(define (number-list->string ns)
  (let loop ((s "(")
                (ns ns)) (cond
    ((null? ns)  (string-append s ")"))
    (else          (loop (string-append s " " (number->string (car ns))) (cdr ns))))))

Sincerely,
AmkG


On Mon, Jun 13, 2016 at 1:53 AM, John Cowan <xxxxxx@mercury.ccil.org> wrote:
Alan Manuel Gloria scripsit:

> Ropes are an O(log n) random-access, O(log n) concatenation structure for
> string representation.  I assume you already know about ropes.

I thought that ropes were O(k) for concatenation where k is the number
of ropes, because you can just create a new top-level node for them.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
The Imperials are decadent, 300 pound free-range chickens (except they have
teeth, arms instead of wings, and dinosaurlike tails).  --Elyse Grasso