Re: Performance problem with table.move

[Egor Skriptunoff <egor.skriptunoff@...>]

On Thu, Dec 3, 2020 at 10:09 PM Pierre Chapuis wrote:

function solution4(level)

   local step = {}

   for j = 1, level do

      step[(1<<j)-1] = j

   end

   local last_index = 1

   for j = 0, level-1 do

      last_index = 2 * last_index + j

   end

   local t = {"Lua"}

   local p = last_index

   for j = 1, (1<<level)-1 do

      p = p - step[j ~ (j-1)]

      t[p] = "Lua"

   end

   return t, last_index

end

local level = tonumber(arg[1])

local t, last_index = solution4(level)

Interesting workaround!

A nitpicking: probably you mean
   local t = {[last_index] = "Lua"}
instead of
   local t = {"Lua"}

Your solution is very fast, almost as required, but still not fast enough:

----

Benchmark of level 20:

$ time lua student1.lua 20
real    0m0.401s
user    0m0.360s
sys    0m0.036s

$ time lua student2.lua 20
real    0m4.495s
user    0m4.436s
sys    0m0.052s

$ time lua student3.lua 20
real    0m0.289s
user    0m0.264s
sys    0m0.020s

$ time lua student4.lua 20
real    0m0.138s
user    0m0.120s
sys    0m0.016s

$ time lua pierre.lua 20
real    0m0.158s
user    0m0.128s
sys    0m0.028s

----

Benchmark of level 23:

$ time lua student1.lua 23
real    0m3.423s
user    0m3.156s
sys    0m0.260s

$ time lua student2.lua 23
real    0m51.331s
user    0m48.440s
sys    0m2.824s

$ time lua student3.lua 23
real    0m2.575s
user    0m2.300s
sys    0m0.268s

$ time lua student4.lua 23
real    0m1.075s
user    0m0.924s
sys    0m0.144s

$ time lua pierre.lua 23
real    0m1.219s
user    0m1.020s
sys    0m0.196s

----

On level 20 the time difference between solution #3 and solution #4 is 2.1 times.
On level 23 the time difference between solution #3 and solution #4 is 2.4 times.