Optimized Str Rep
 |
||
|
Optimized Str Rep |
|
function log2(n)
local _n = 2
local x = 1
if (_n < n) then
repeat
x = x + 1
_n = _n + _n
until (_n >= n)
elseif (_n > n) then
if (n == 1) then
return 0
else
return nil
end
end
if (_n > n) then
return x-1
else
return x
end
end
function get_bits(n)
local bits = {}
local rest = n
repeat
local major_bit = log2(rest)
rest = rest - 2^major_bit
bits[major_bit] = 1
if (bits.count == nil) then
bits.count = major_bit
end
until (rest == 0)
return bits
end
function fast_strrep(str, times)
local bits = get_bits(times)
local strs = {[0] = str}
local count = bits.count
for i = 1, count do
strs[i] = strs[i-1] .. strs[i-1]
end
local result = ''
for i = 0, count do
if (bits[i]) then
result = result .. strs[i]
end
end
return result
end
for numreps = 1024, 30*1024*1024, 1024*64 do
a = nil
b = nil
collectgarbage()
start = clock()
a = fast_strrep("a", numreps)
print("L:"..numreps.." "..(clock() - start))
start = clock()
b = strrep("a", numreps)
print("C:"..numreps.." "..(clock() - start))
if (a~=b) then
print("the algorithm is wrong!")
else
print("ok")
end
flush(_STDOUT)
end
a .. b .. c into a single operation, and which also avoids creating a temporary vector. I think you'll find it to be about twice as fast as yours (and a lot shorter). It might also be interesting as an example of how to do stuff that looks like bit manipulation without too much pain. -- RiciLake
-- Suppose that x = b[n]*2^n + b[n-1]*2^(n-1) + ... + b[0]*2^0
-- (where every b[i] is either 0 or 1)
-- This is exactly equivalent to:
-- b[0] + 2 * (b[1] + 2 * (b[2] + (... + b[n])))
-- So we've effectively eliminated all the multiplications, replacing them with doubling.
-- Now, x * y (for any y) can be calculated by distributing multiplication over the
-- above, which effectively replaces every b[i] with b[i] * y. However, every b[i]
-- is either 0 or 1, so the product is either 0 or y.
-- Now, if k is an integer and str1 and str2 are strings, and we write:
-- str1 + str2 for the concatenation of str1 and str2
-- k * str1 for "k copies of str1 concatenated"
-- we can see that we have + and * are "just like" integer arithmetic in the sense that
-- + and * are commutative and associative, and * distributes over +. So the equivalence
-- continues to work, except that every term must be either "" (for 0) or y (the string).
-- All that is left is to compute the expression from the inside out: each step is
-- either 2 * r or y + 2 * r, where r is the cumulated value and y is the original string.
-- In string terms, we can write these as result .. result (2 * r) and
-- result .. result .. str (2 * r + y)
-- We could use the same idea to compute integer exponents in the minimum number of
-- multiplications, using * and ^ instead of + and * (which is where this algorithm
-- comes from.)
-- This makes use of the fact that Lua optimises a .. b .. c into a single concatenation.
-- With a bit more work, we could use any base we wanted to, not just base 2. But it would
-- require more options in the if statement.
function another_strrep(str, times)
local result = ""
local high_bit = 1
while high_bit < times do high_bit = high_bit * 2 end
-- at this point, high_bit is the largest (integral) power of 2 smaller than times
-- (unless times < 1 in which case high_bit is 1)
-- The computation of highbit could be:
-- local high_bit = 2 ^ floor(log(times) / log(2))
-- which is probably faster but requires the math library
-- we are now going to work through times, bit by bit, making use of the above formula:
while high_bit >= 1 do
if high_bit <= times then -- the bit is 1 if times is >= high_bit
times = times - high_bit -- we "turn it off" for the next iteration
result = result .. result .. str -- and the next step is 2 * r + y
else -- the bit is 0
result = result .. result -- so the next step is 2 * r
end
high_bit = high_bit / 2 -- Now go for the next bit
end
return result
end
luiz/rici = 1.41 (rici is 1.41 times faster than luiz)
c/luiz = 2.98 (luiz is 2.98 times faster than c)
c/rici = 4.19 (rici is 4.19 times faster than c)
"" .. "" .. str very rapidly.
%state is a standard trick for getting around the fact that Lua 4.0 doesn't have real closures.
join function which I wrote which lazily compiles subroutines to do the same sort of exponential decomposition of the problem; even though it has to compose and compile functions, it turns out to be much faster than the naive join. Of course, the functions have to be memoised to take advantage of that. I'll try to post that one, too. -- RiciLake
do
local concats = {
["0"] = function(a, b) return a .. a .. a .. a .. a .. a .. a .. a .. a .. a end,
["1"] = function(a, b) return a .. a .. a .. a .. a .. a .. a .. a .. a .. a
.. b end,
["2"] = function(a, b) return a .. a .. a .. a .. a .. a .. a .. a .. a .. a
.. b .. b end,
["3"] = function(a, b) return a .. a .. a .. a .. a .. a .. a .. a .. a .. a
.. b .. b .. b end,
["4"] = function(a, b) return a .. a .. a .. a .. a .. a .. a .. a .. a .. a
.. b .. b .. b .. b end,
["5"] = function(a, b) return a .. a .. a .. a .. a .. a .. a .. a .. a .. a
.. b .. b .. b .. b .. b end,
["6"] = function(a, b) return a .. a .. a .. a .. a .. a .. a .. a .. a .. a
.. b .. b .. b .. b .. b .. b end,
["7"] = function(a, b) return a .. a .. a .. a .. a .. a .. a .. a .. a .. a
.. b .. b .. b .. b .. b .. b .. b end,
["8"] = function(a, b) return a .. a .. a .. a .. a .. a .. a .. a .. a .. a
.. b .. b .. b .. b .. b .. b .. b .. b end,
["9"] = function(a, b) return a .. a .. a .. a .. a .. a .. a .. a .. a .. a
.. b .. b .. b .. b .. b .. b .. b .. b .. b end,
}
function decimal_strrep(str, times)
local state = {r = "" }
local concats = %concats
times = tostring(times)
if strfind(times, "^[0-9]+$") then
gsub(times, "(.)",
function(digit)
%state.r = %concats[digit](%state.r, %str)
end)
end
return state.r
end
end