From: "Itterheim, Steffen" <sitterheim@ea.com>
Reply-To: Lua list <lua@bazar2.conectiva.com.br>
To: "Lua list" <lua@bazar2.conectiva.com.br>
Subject: AW: String algorithm
Date: Thu, 25 Jan 2007 13:35:37 -0000
http://www.lua.org/pil/11.6.html
RTFM ;)
-----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
