function solution4(level)
-- Fast calculation of last_index, see
https://oeis.org/A000325
local last_index = (2 << level) - level - 1
-- Preallocation of the array, so everything is in the array
part
local t = {"Lua"}
for j = 2, last_index do
t[j] = "Lua"
end
-- Removal of values from indices that should contain nil
local p = 3
for j = 1, (1 << (level - 1)) - 1 do
local s = j ~ (j - 1)
while s > 0 do
-- Implicitly calculation of log without a table
lookup
-- Since we already looping this is better
s = s >> 1
t[p] = nil
p = p + 1
end
p = p + 2
end
return t, last_index
end
local level = tonumber(arg[1])
local t, last_index = solution4(level)
Congratulations!
Your solution is the fastest.
$ time lua student3.lua 20
real 0m0.294s
$ time lua pierre.lua 20
real 0m0.158s
$ time lua student4.lua 20
real 0m0.140s
$ time lua xmilia.lua 20
real 0m0.127s
My version:
$ cat student4.lua
-- Unfortunately, there is no function table.new() in Lua to allocate a room for the array part.
-- Workaround: create a table and make it grow by inserting fake values, all of them will be overwritten later
function solution4(level)
if level == 0 then
return {"Lua"}, 1
end
local t = {"Lua", "Lua"}
local last_index = 2
for j = 4, 2^level + level do
t[j] = true -- inserting fake values
end
for n = 2, level do
last_index = last_index + 1
t[last_index] = nil
table.move(t, 1, last_index, last_index + 1)
last_index = 2 * last_index
end
last_index = last_index - level + 1
return t, last_index
end
local level = tonumber(arg[1])
local t, last_index = solution4(level)
The crucial part is "Preallocation of the array, so everything is in the array part"
That's what every Lua programmer should be aware of while optimising for speed.
Conclusion:
We need something like table.rebuild()/table.new() in Lua to avoid inserting fake values.
