One day I wondered how to prevent the simultaneous and redundant tasks on a single point (or tile) on the map. The short answer is the sets and the caching.
Sets in the Lua looks, for example, like:
Code: Select all
cached = { [ID1] = true, [ID3] = true, ... , [ID2] = true }Code: Select all
if not cached[ID] then
add(x, y, action)
[EDIT]: Most likely I'm wrong in that I use the pairing functions to generate the hash from the two values. The main advantage of the pairing function is that the unpairing functions exist
And in the above case, reversibility of the operation is not required. But I have not yet found a simple and fast hash function for Lua. 
It is also very desirable that the computed IDxy will have not too many digits.The easiest way is the concatenation of these two coordinates as strings with a delimiter between:
Code: Select all
IDxy = tostring(x).."/"..tostring(y)
Probably it is not a better way at all. And I managed to find on the web at least another two examples of the pairing functions:
- 1. The Cantor pairing function;
2. An Elegant Pairing Function by Matthew Szudzik.
For the Z -> N mapping we can use such a way:
Code: Select all
n = z * 2, for n >= 0;
n = -z * 2 - 1, for n < 0.
profiler.lua
Code: Select all
local profiler = {}
require "socket"
local Timer
local function getTime()
-- time in milliseconds instead of os.time() in seconds
return socket.gettime()*1000
end
function profiler.start()
Timer = getTime()
end
function profiler.stop()
return tostring(os.difftime(getTime(), Timer))
end
return profilerCode: Select all
------------------------------------------------------
-- Test environment section
------------------------------------------------------
local profiler = require("profiler")
local p =
{
x = {},
y = {}
}
local out1 = {}
local out2 = {}
local out3 = {}
local out4 = {}
local out5 = {}
local out6 = {}
local out7 = {}
local function genPolyline(n, max)
for i = 1, n do
p.x[i] = math.random(-max, max)
p.y[i] = math.random(-max, max)
end
end
------------------------------------------------------
-- The mappings
------------------------------------------------------
-- ZxZ -> {strings}
local function concatPair(x, y)
return tostring(x).."/"..tostring(y)
end
-- Z -> N
local function NtoZ(x, y)
return (x >= 0 and (x * 2) or (-x * 2 - 1)), (y >= 0 and (y * 2) or (-y * 2 - 1))
end
-- ZxZ -> N, i.e. (x, y) -> IDxy
local function cantorPair_v1(x, y)
x,y = NtoZ(x, y)
return (x + y +1)*(x + y)/2 + x
end
local function cantorPair_v2(x, y)
x,y = NtoZ(x, y)
-- other representation, same result
return (x*x + 3*x + 2*x*y + y + y*y) / 2
end
local function cantorPair_v3(x, y)
x,y = NtoZ(x, y)
-- the same values * 2
return x*x + 3*x + 2*x*y + y + y*y
end
local function elegantPair_v1(x, y)
x,y = NtoZ(x, y)
return (x >= y and (x * x + x + y) or (y * y + x))
end
local function elegantPair_v2(x, y)
x,y = NtoZ(x, y)
if x >= y then
return x * x + x + y
end
return y * y + x
end
local function godelPair(x, y)
x,y = NtoZ(x, y)
return (2^x)*(3^y)
end
------------------------------------------------------
-- Profiling section
------------------------------------------------------
-- init test data
local n = 5000000
print("Generating test data..")
genPolyline(n, 12000)
print("Profiling:")
print("Test #1 - concatPair")
profiler.start()
for i = 1, n do
out1[i] = concatPair(p.x[i], p.y[i])
end
local result = profiler.stop()
print(result.." ms")
print("Test #2 - cantorPair v1")
profiler.start()
for i = 1, n do
out2[i] = cantorPair_v1(p.x[i], p.y[i])
end
local result = profiler.stop()
print(result.." ms")
print("Test #3 - cantorPair v2")
profiler.start()
for i = 1, n do
out3[i] = cantorPair_v2(p.x[i], p.y[i])
end
local result = profiler.stop()
print(result.." ms")
print("Test #4 - cantorPair v3")
profiler.start()
for i = 1, n do
out4[i] = cantorPair_v3(p.x[i], p.y[i])
end
local result = profiler.stop()
print(result.." ms")
print("Test #5 - elegantPair v1")
profiler.start()
for i = 1, n do
out5[i] = elegantPair_v1(p.x[i], p.y[i])
end
local result = profiler.stop()
print(result.." ms")
print("Test #6 - elegantPair v2")
profiler.start()
for i = 1, n do
out6[i] = elegantPair_v2(p.x[i], p.y[i])
end
local result = profiler.stop()
print(result.." ms")
print("Test #7 - godelPair")
profiler.start()
for i = 1, n do
out7[i] = godelPair(p.x[i], p.y[i])
end
local result = profiler.stop()
print(result.." ms")
print("Done!")Lua 5.1.4 Copyright (C) 1994-2008 Lua.org, PUC-Rio
concatPair: 15199 ms
cantorPair v1: 1949 ms
cantorPair v2: 2312 ms
cantorPair v3: 2266 ms
elegantPair v1: 2017 ms
elegantPair v2: 1974 ms
[EDIT]: godelPair: ~3000-3500ms
As we can see, the way of multiple concatenations is dramatically slow. I was rooting for the elegantPair() function but I did not manage to implement it to be faster than the Cantor's method.
The more efficient ways are welcome! For me the current winner is:
Code: Select all
-- Z -> N
local function NtoZ(x, y)
return (x >= 0 and (x * 2) or (-x * 2 - 1)), (y >= 0 and (y * 2) or (-y * 2 - 1))
end
-- ZxZ -> N, i.e. (x, y) -> IDxy
local function cantorPair_v1(x, y)
x,y = NtoZ(x, y)
return (x + y +1)*(x + y)/2 + x
endMaterials used:
http://szudzik.com/ElegantPairing.pdf (an Elegant Pairing Function by Matthew Szudzik)
https://en.wikipedia.org/wiki/Pairing_function (The Cantor pairing function)
https://www.lua.org/gems/sample.pdf (Lua Performance Tips by Roberto Ierusalimschy)
https://www.lua.org/pil/11.5.html (Lua - Sets)
[EDIT]:https://hbfs.wordpress.com/2011/09/27/p ... functions/ (some more examples of the pairing functions)
