A rope represents an immutable character sequence. A rope's length is simply the number of characters in the sequence. Most string representations store all their characters contiguously in memory. The defining characteristic of a rope is that it does away with this restriction, instead allowing fragments of the rope to reside noncontiguously and joining them using concatenation nodes. This design allows concatenation to run asymptotically faster than for Java Strings. The String version of concatenation requires strings you want to join to be copied to a new location, which is an O(n) operation. The rope counterpart simply creates a new concatenation node, which is an O(1) operation. (If you're unfamiliar with big-O notation, see Resources for a link to explanatory material.)
Read full article from Ropes: Theory and practice
No comments:
Post a Comment