AW: String algorithm

["Itterheim, Steffen" <sitterheim@...>]

You might also be interested in the string buffer example:
http://lua-users.org/wiki/SimpleStringBuffer


-----Ursprüngliche Nachricht-----
Von: lua-bounces@bazar2.conectiva.com.br [mailto:lua-bounces@bazar2.conectiva.com.br] Im Auftrag von Mark Meijer
Gesendet: Donnerstag, 25. Januar 2007 14:26
An: lua@bazar2.conectiva.com.br
Betreff: String algorithm

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