Rope (data structure): Difference between revisions
Cybercobra (talk | contribs) |
cord |
||
| Line 1: | Line 1: | ||
In [[computer programming]], a '''rope''' is a heavyweight [[string (computer science)|string]], involving the use of a [[concatenation tree]] representation. The concept was introduced in a paper called "Ropes: an Alternative to Strings".<ref name="Boehm"> |
In [[computer programming]], a '''rope''' (also known as cord) is a heavyweight [[string (computer science)|string]], involving the use of a [[concatenation tree]] representation. The concept was introduced in a paper called "Ropes: an Alternative to Strings".<ref name="Boehm"> |
||
{{cite journal |
{{cite journal |
||
| last = Boehm |
| last = Boehm |
||
Revision as of 19:45, 2 August 2010
In computer programming, a rope (also known as cord) is a heavyweight string, involving the use of a concatenation tree representation. The concept was introduced in a paper called "Ropes: an Alternative to Strings".[1]
Description
A rope is essentially a binary tree whose leaves are arrays of characters. A node in the tree has a left child and a right child - the left child is the first part of the string, while the right child is the final part of the string. Concatenation of two ropes simply involves the creation of a new tree node with both ropes as children.
The main advantages of ropes as compared to storing strings as character arrays is that they enable much faster concatenation than ordinary strings, and don't require a large contiguous memory space to store a large string. The main disadvantages are greater overall space usage and slower indexing, both of which become more severe as the tree structure becomes larger and deeper. However, many practical applications of indexing involve only iteration over the string, which remains fast as long as the leaf nodes are large enough to benefit from cache effects.
Comparison to array-based strings
This table compares the algorithmic characteristics of string and rope implementations, not their "raw speed". Array-based strings may have smaller overhead, so (for example) concatenation and substring operations may sometimes be faster on small strings than small ropes, but will usually be faster on large ropes than large strings.
| Operation | Rope performance | String performance |
|---|---|---|
| concatenation | O(1) | O(n) |
| substring | O(log n) | O(n) |
| indexing | O(log n) | O(1) |
| iteration | O(n) | O(n) |
See also
References
- ^ a b
Boehm, Hans-J (December 1995). "Ropes: an Alternative to Strings" (PDF). Software—Practice & Experience. 25 (12). New York, NY, USA: John Wiley & Sons, Inc.: 1315–1330. doi:10.1002/spe.4380251203.
{{cite journal}}: Unknown parameter|coauthors=ignored (|author=suggested) (help)
External links
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |