2) To honestly warn users about performance penalties of tables with nils. Introduce table.new()/rebuild() to help users improve performance when they need
With msvc 2019 (64 bits):
static int tnew (lua_State *L) {
int narray = luaL_checkinteger(L, 1);
int nrec = luaL_optinteger(L, 2, 1);
lua_createtable(L, narray, nrec); /* create result table */
return 1; /* return table */
}
#student2.lua
local s, e
local clock = os and os.clock or clock
function solution2(level)
local t = {"Lua"} -- chain of level 0 is already in the table
local last_index = 1 -- last touched index
local table_move = table.move
for n = 1, level do
-- skip (n-1) nils and append a copy of the current content of the table
table_move(t, 1, last_index, last_index + n)
last_index = 2*last_index + n-1
end
return t, last_index
end
if clock then
s = clock()
end
local level = tonumber(arg[1])
local t, last_index = solution2(level)
if clock then
e = clock()
local fmt = string and string.format or format
print(fmt and fmt("%f", e - s) or (e - s))
else
print("Done")
end
..\lua student2.lua 20
4.187000
#student5.lua (from Xmilia Hermit)
local s, e
local clock = os and os.clock or clock
function solution5(level)
local last_index = (2 << level) - level - 1
local step = {}
for j = 1, level do
step[(1 << j)-1] = j
end
local t = table.new(last_index, 0)
t[1] = "Lua"
local p = 1
for j = 1, (1 << level)-1 do
p = p + step[j ~ (j - 1)]
t[p] = "Lua"
end
return t, last_index
end
if clock then
s = clock()
end
local level = tonumber(arg[1])
local t, last_index = solution5(level)
if clock then
e = clock()
local fmt = string and string.format or format
print(fmt and fmt("%f", e - s) or (e - s))
else
print("Done")
end
..\lua table.lua 20
0.072000
regards,
Ranier Vilela
