Re: Performance problem with table.move

[Chris Smith <space.dandy@...>]

On 5 Dec 2020, at 13:31, Egor Skriptunoff <egor.skriptunoff@gmail.com> wrote:

On Sat, Dec 5, 2020 at 3:00 PM Xmilia Hermit wrote:

[ … a faster solution … ]

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

How about this:

function fastnil_table()
  local data = "" class="">  local my_nil = {}
  return setmetatable({
    move = function(a1, ...)
      table.move(data, ...)
    end
  }, {
    __index = function(t, k)
      if data[k] ~= my_nil then
        return data[k]
      end
    end,
    __newindex = function(t, k, v)
      if v == nil then
        v = my_nil
      end
      data[k] = v
    end
  })
end

local function create(level, t, idx)
  if level == 0 then
    idx = idx + 1
    t[idx] = "Lua"
  else
    idx = create(level - 1, t, idx)
    t:move(1, idx, idx + level)
    idx = (2 * idx) + level - 1
    for i = 1,level do
      t[idx + i] = nil
    end
  end
  return idx
end

function solution4(level)
   local t = fastnil_table()
   local last_index = create(level, t, 0)
   return t, last_index
end

local level = tonumber(arg[1])
local t, last_index = solution4(level)

┌ chris@chriss-mbp-2 ~/src/tmp/lua
└ 11:03:01 $ /usr/bin/time -p lua student1.lua 20
real         0.25
user         0.23
sys          0.01
┌ chris@chriss-mbp-2 ~/src/tmp/lua
└ 11:06:50 $ /usr/bin/time -p lua student3.lua 20
real         0.18
user         0.16
sys          0.01
┌ chris@chriss-mbp-2 ~/src/tmp/lua
└ 11:06:55 $ /usr/bin/time -p lua xmilia.lua 20
real         0.11
user         0.10
sys          0.01
┌ chris@chriss-mbp-2 ~/src/tmp/lua
└ 11:07:04 $ /usr/bin/time -p lua chris.lua 20
real         0.06
user         0.04
sys          0.01

Regards,

Chris