Am 17.09.2010 02:40, schrieb liam mail:
On 16 September 2010 23:19, Mike Pall <mikelu-1009@mike.de>
wrote:
Victor Poughon wrote:
> When running it until 1,000,000 it finishes in about 15
seconds. (I have a
> 1.83Ghz processor).
> I'm not really concerned about performance, and i'm
sure there's a better
> algorithm for solving this problem. But an equivalent
algorithm in
> C<http://pastebin.com/9MMzS4UA>finishes
about 6 times faster.
> Is this what one should expect from Lua ?
It runs 8.5x faster with LuaJIT.
Obviously algorithmic improvements pay off a lot here. The
following code takes 60 milliseconds on my machine with
LuaJIT:
local bit = require("bit")
local bnot, bor, band = bit.bnot, bit.bor, bit.band
local shl, shr = bit.lshift, bit.rshift
local N = tonumber(arg and arg[1]) or 1000000
local cache, m, n = { 1 }, 1, 1
for i=2,N do
local j = i
for len=1,1000000000 do
j = bor(band(shr(j,1), band(j,1)-1), band(shl(j,1)+j+1,
bnot(band(j,1)-1)))
local x = cache[j]; if x then j = x+len; break end
end
cache[i] = j
if j > m then m, n = j, i end
end
io.write("Found ", n, " (chain length: ", m, ")\n")
--Mike
That code may well be faster but it is horrible code that
someone learning the language should not have to look at.
Liam
To hard words. It is just to show that it is possible.
The bit operations are challenging me at the moment, but I'm very
fine with the cache (very luaish, I think).
Mike, thank you for the stimulation.
--Frank
|
