# Question of reference and (sub)strings

**URL:** <https://www.ruby-forum.com/t/question-of-reference-and-sub-strings/50259>\
**Category:** Ruby\
**Created:** [December 14, 2005, 4:33pm UTC](https://www.ruby-forum.com/t/question-of-reference-and-sub-strings/50259 "2005-12-14T16:33:29Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![Steve\_SRubyTalk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/9de0a6/32.png) [@Steve\_SRubyTalk](https://www.ruby-forum.com/u/Steve_SRubyTalk)\
**Post date:** [December 14, 2005, 4:33pm UTC](https://www.ruby-forum.com/t/question-of-reference-and-sub-strings/50259/1 "2005-12-14T16:33:29Z")

</div>

Imagine comparing using C++ and Ruby to manipulate some strings. I would  
like to confirm some assumptions I am making about in-memory efficiency  
with Ruby. (This explains why the example seems contrived and I don’t  
want to be told to tackle the problem a different way, such as splitting  
up the input as it is read from file/sockets etc… 🙂 )

Assume I’ve got a large in-memory sequence of bytes (this would be  
represented in C(++) using a malloc block) and in ruby as a String. I  
have a pre-defined (non-trivial, potentially computationally expensive)  
function which calculates a sequence of offsets into the String subject  
to some arbitrary criteria… and subsequently I wish to reference  
sub-strings (i.e. strings between two successive offsets) as if they  
were independent of the original string (though, of course, each having  
a fixed length.) N.B. This could be done ‘cheaply’ using pointers into  
the original string if using C/C++.

Given that I only want to compute the offsets once, an obvious solution  
would be to construct an Array of String - each element representing a  
sub-string of the original… but this would double memory use. What  
would be the best way to avoid duplicating the character sequences and  
causing run-time bloat?

By corollary, if I had a large number of Strings, what would be the most  
memory efficient way to represent their concatenation? If I had n mK  
stings, would I need another n\*mK contiguous block of memory to  
represent their concatenation?

---

<div class="post-metadata">

**Author:** ![Steve\_SRubyTalk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/9de0a6/32.png) [@Steve\_SRubyTalk](https://www.ruby-forum.com/u/Steve_SRubyTalk)\
**Post date:** [December 15, 2005, 6:34am UTC](https://www.ruby-forum.com/t/question-of-reference-and-sub-strings/50259/2 "2005-12-15T06:34:23Z")

</div>

On 12/14/05, Steve [RubyTalk] [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> Given that I only want to compute the offsets once, an obvious solution  
> would be to construct an Array of String - each element representing a  
> sub-string of the original… but this would double memory use. What  
> would be the best way to avoid duplicating the character sequences and  
> causing run-time bloat?

You don’t need to create the substrings until you need them: Here’s a  
test which only allocates memory for the substrings as needed. As far  
as I can tell, the substrings are released back to the GC as soon as  
you are done with them.

class IndexedString \< String  
def initialize s, &indexer  
super s  
@offsets = yield self  
self  
end  
def substring n  
(0…(@offsets.size-1)) === n ?  
self[@offsets[n]…@offsets[n+1]] :  
nil  
end  
end

def build\_index s  
indexes = [0]  
while (n=s.index(‘.’,indexes.last+1)) do indexes \<\< n+1 end  
indexes \<\< s.length+1  
end

s = IndexedString.new( ((“TESTINGTESTING!!”\*1024)+“.”)\*100) do |str|  
build\_index(str)  
end #= +1600K  
s.substring 10; #+16K  
s.substring 95; #+16K

> By corollary, if I had a large number of Strings, what would be the most  
> memory efficient way to represent their concatenation? If I had n mK  
> stings, would I need another n\*mK contiguous block of memory to  
> represent their concatenation?

Not necessarily: You can build a class which takes an array of  
strings and returns  
“superstrings” only as needed. Here are my passing test cases, but  
the class still needs a little work before I’ll post it:

def test\_MegaString  
small\_strings = %w( this is a collection of small strings)  
mega = MegaString.new(small\_strings)  
assert\_equal(“t”,mega[0])  
assert\_equal(“this”,mega[0,4])  
assert\_equal(“hisisaco”,mega[1,8])  
assert\_equal(“ollect”,mega[8,6])  
assert\_equal(“a”, mega[6…7])  
assert\_equal(“col”, mega[7…10])  
assert\_equal(“lstrings”, mega[23,-1])  
assert\_equal(“lstrings”, mega[23,230])  
assert\_equal(“thisisacollectionofsmallstrings”, mega.to\_s)  
end

-Adam