lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


Hey,
how about:

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)

time ./lua student3.lua 20

real    0m0.126s
user    0m0.126s
sys     0m0.000s

time ./lua student4.lua 20

real    0m0.063s
user    0m0.062s
sys     0m0.000s

Regards,
Xmilia

Am 03.12.2020 um 16:09 schrieb Egor Skriptunoff:
Hi!
 
Imagine the following situation: students are taking the Lua exam.
Besides usual questions, this exam has a practical part: a task to write some Lua program and optimize it for speed.
This is the task:
 
Write a function which returns a table containing a fractal-like chain of values described below.
The chain resembles the Cantor set; its definition is recursive:
This is a table containing a level 0 chain:
{"Lua"}
This is a table containing a level 1 chain (concatenation of two level 0 chains):
{"Lua", "Lua"}
This is a table containing a level 2 chain (two level 1 chains with a nil in between):
{"Lua", "Lua", nil, "Lua", "Lua"}
This is a table containing a level 3 chain (two level 2 chains with double nil in between):
{"Lua", "Lua", nil, "Lua", "Lua", nil, nil, "Lua", "Lua", nil, "Lua", "Lua"}
And so on:
to create a chain of level n, concatenate two chains of level (n-1) separated by (n-1) nils.
Your function should return a table containing a chain; the level of the chain is passed to the function as an argument (a non-negative integer).
The faster your function runs the more exam points you earn.
 
 
Four students are solving this task.
 
----
 
Student #1 uses simple recursion.
This is his solution:
 
$ cat student1.lua
local function append(n, t, idx)
   -- appends a chain of level n to table t starting from index idx+1
   -- returns the last touched index
   if n == 0 then  -- append chain of level 0
      idx = idx + 1
      t[idx] = "Lua"
      return idx
   else -- recursively append chain of a higher level
      idx  = append(n-1, t, idx) -- append chain of level (n-1)
      idx  = idx + (n-1)         -- skip (n-1) nils
      return append(n-1, t, idx) -- append chain of level (n-1)
   end
end
 
function solution1(level)
   local t = {}
   local last_index = append(level, t, 0)
   return t, last_index
end
 
local level = tonumber(arg[1])
local t, last_index = solution1(level)
 
----
 
Student #2 has a deeper knowledge of Lua.
He knows that calling a function in Lua is an expensive operation.
So he decides to use a loop instead of recursion.
He also knows that Lua has a special function to copy a continuous range of indices:
table.move() is written in C, so it should work really fast.
This is his solution:
 
$ cat student2.lua
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
 
local level = tonumber(arg[1])
local t, last_index = solution2(level)
 
Student #2 is absolutely sure that his code would be faster than the program of student #1.
But a benchmark for level 20 shows that the code written by student #1 is significantly better.
(A chain of level 20 consists of 2097131 elements: 1048576 strings and 1048555 nils.)
 
$ lua -v
Lua 5.4.2  Copyright (C) 1994-2020 Lua.org, PUC-Rio
 
$ time lua student1.lua 20
real  0m0.395s
user  0m0.352s
sys   0m0.040s
 
$ time lua student2.lua 20
real  0m4.498s
user  0m4.432s
sys   0m0.060s
 
Student #2 says "Damn it, table.move is a slow shit, I'll never use it again!" and leaves the classroom slamming the door.
Obviously, he is very disappointed in the benchmark results.
 
----
 
Question to Roberto:
   How would you explain to student #2 why table.move() is so slow despite having been implemented in C?
 
----
 
Student #3 is a smart guy.
He has noticed that the number of nils after the N-th string equals the number of trailing zeroes in the binary representation of the number N.
He also knows the formula of the number of trailing zeroes:
LOG_2(XOR(N,N-1)+1)-1
math.log() is slow in Lua, so he uses a table lookup instead.
This is his solution:
 
$ cat student3.lua
function solution3(level)
   local step = {}
   for j = 1, level do
      step[(1<<j)-1] = j
   end
   local t = {"Lua"}
   local last_index = 1
   for j = 1, (1<<level)-1 do
      last_index = last_index + step[j ~ (j-1)]
      t[last_index] = "Lua"
   end
   return t, last_index
end
 
local level = tonumber(arg[1])
local t, last_index = solution3(level)
 
This code runs 1.3 times faster than the solution #1:
 
$ time lua student3.lua 20
real  0m0.296s
user  0m0.260s
sys   0m0.036s
 
----
 
Student #4 is an experienced Lua programmer.
He avoids all pitfalls.
His solution runs twice as fast as the solution #3.
 
$ time lua student4.lua 20
real  0m0.142s
user  0m0.124s
sys   0m0.020s
 
----
 
A mini-exam for the reader:
   How has student #4 solved the task?
 
(You might want to stop here and find
your own candidate for "solution #4"
before continuing reading this thread)