String algorithm

["Mark Meijer" <meijer78@...>]

Hi all,

I remember finding an algorithm on the lua wiki a couple of years ago, that 
dealt with reading a text file one line at a time (or one word at a time, in 
any case piece by piece) and concatenating all the pieces into a single 
string. The algorithm was meant to prevent numerous copying of the string in 
memory, which would occur using a straightforward approach such as the 
following:

for line in file:lines() do
mytext = mytext .. line;
end

The above approach would be unacceptably inefficient when dealing with large 
input files, because with each iteration the entire contents of the variable 
mytext would be duplicated into a new memory location.

I've been trying to find the algorithm again (already 7 months ago, and now 
again) but for the life of me I can't find it anywhere. I don't remember 
exactly how it goes, but I believe it entails storing the string pieces into 
a table (possibly a regular array) and selectively concatenating some 
pieces, based on their size relative to other pieces in the table. The newly 
formed string would be placed back into the table. This process continues 
until only one string remains in the table, which represents the whole file 
read into that string.

That's about as much as I remember of it. Plus, I found it briljant in its 
simplicity and in how it drastically reduced the effective amount of 
duplications needed (if I remember correctly, it would effectively duplicate 
the entire length of data only once or twice, but I could be wrong here). 
Obviously it was not simple enough for me to remember it :P but if any of 
you have any idea what I'm talking about, I'd really like to hear it.

Thanks!

Regards,
Mark

_________________________________________________________________
Talk with your online friends with Messenger 
http://www.join.msn.com/messenger/overview