Re: Performance problem with table.move

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

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

On Tue, Dec 8, 2020 at 2:13 PM Chris Smith wrote:

How about this:

Your program does not create a table containing the chain required.

Instead it creates __index-based emulation of such a table.

An emulation could be created in 0.00 seconds  ;-)

Prove it. :)  If it walks like a duck and quacks like a duck…. My program does create a table with a compatible chain, the ‘emulation' simply converts a pseudo-nil into a real nil on request, in a way that is transparent to the user.  The only way to iterate a chain is using a ‘for’ loop with a pre-computed limit (since ipairs and #t won’t work on sparse tables), so the usage is the same.

But if that really bothers you, try this simpler version which does exactly what you ask:

local function create(level, t, idx, pseudo_nil)

  if level == 0 then

    idx = idx + 1

    t[idx] = "Lua"

  else

    idx = create(level - 1, t, idx, pseudo_nil)

    table.move(t, 1, idx + level, idx + level)

    idx = (2 * idx) + level - 1

    t[idx + level] = pseudo_nil

  end

  return idx

end

function solution4(level)

  local pseudo_nil = {}

  local t = setmetatable({}, { __mode="v" }) -- create a weak table

  local last_index = create(level, t, 0, pseudo_nil)

  pseudo_nil = nil -- make the pseudo-nils magically disappear

  return t, last_index

end

local level = tonumber(arg[1])

local t, last_index = solution4(level)

┌ chris@chriss-mbp-2 ~/src/tmp/lua

└ 1:32:52 $ /usr/bin/time -p lua chris2.lua 20

real         0.06

user         0.05

sys          0.01

Regards,

Chris
—
Chris Smith <space.dandy@icloud.com>