From: Nikolai Weibull <mailing-lists.ruby-talk@...>
Date: 2005-03-17T08:04:02+09:00
Subject: Re: Symbol vs String

* Peter C. Verhage (Mar 16, 2005 23:40):
> But why do Strings not behave like Symbols? I mean, why aren't all
> Strings immutable? Is this because Symbols will never get garbage
> collected (to make sure they can be used over and over again) and
> normal Strings will? Which might mean that in some cases (lots of text
> processing) immutable Strings would fill up memory?

Oh, no...not immutable vs. mutable strings again...

Well, if strings were immutable, then that would mean that strings could
share contents, and thus immutable strings wouldn't fill up memory.  I
have suggested on the ruby-core list that Ruby should provide a second
data structure that acts like a string, namely the _rope_, and that it
be implemented in a way that allows for it to be used for tasks where
immutable "strings" are desired.

A rope is basically a string represented by a tree.  Leafs of the tree
point to the subsequences of the whole string.  These subsequences can
be shared with other ropes and can be generated lazily, i.e., from IO or
other generators.  All that is needed is the length of the subsequence.
Every internal node keeps track of its own size and the size of its left
child.  Thus, the offset of a node in the tree is the size of its left
child plus its ancestors.  Ropes can be used to represent long strings
efficiently and many operations on ropes are O(1) where they are O(n) on
a string.  This is offset by the fact that lookup in a rope is O(lg n)
versus O(1) for a string, but in many cases this isn't a problem.

Anyway, the rope data structure is further described in [1].  Boehm has
actually implemented this in C for his garbage collector, so see that
package for an example implementation (not though that it uses a lot of
C-hacks which makes it undesirable to use as-is).  There's also a rope
data structure in STL, but it's limited to only using ropes and strings,
not IO,
	nikolai (the rope and piece table lover)

[1] Hans-J Boehm, "Ropes: an Alternative to Strings", Software--Practice
and Experience, vol. 25(12), 1315--1330, Dec. 1995.  Available at
http://rubyurl.com/2FRbO.

-- 
::: name: Nikolai Weibull    :: aliases: pcp / lone-star / aka :::
::: born: Chicago, IL USA    :: loc atm: Gothenburg, Sweden    :::
::: page: www.pcppopper.org  :: fun atm: gf,lps,ruby,lisp,war3 :::
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}