lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


On re-examination of LTN9 "Creating strings piece by piece" I noticed a
small but significant difference between the LTN9 code and concat.lua
(distributed as part of luasocket.)  The stack invariants differ:

LTN9:  strlen(s[i]) > strlen(s[i+1])
luasocket:  strlen(s[i]) > 2*strlen(s[i+1])

The upshot is that LTN9 performs O(sqrt(n)) actual concats (worst case)
while for luasocket this is O(log(n)).  Here n is the length of the
resulting string.

Maybe LTN9 could be updated?  It is after all an important LTN (it still is
even with table.concat around I think)...

--
Wim