just a little update on the thing, ditched the strings as table keys. That made
it a second faster from 1.5 seconds.
import std/[monotimes, random, tables]
let t0 = getMonoTime()
type
Box = object
x, y, w, h: uint
n:uint
func isqrt(n: uint): uint {.inline.}=
# http://stackoverflow.com/a/15391420
var
x = n
y = (x + 1) div 2
while y < x:
x = y
y = (x + n div x) div 2
return x
func tupToInt(tup: tuple[x:uint, y:uint]): uint {.inline.}=
#http://szudzik.com/ElegantPairing.pdf
let (x, y) = tup
if x == max(x, y):
return x * x + x + y
else:
return y * y + x
func intToTup(val: uint): tuple[x:uint, y:uint] {.inline.} =
let s = isqrt(val)
if val - s * s < s:
return (val - s * s, s)
else:
return (s, val - s * s - s)
func toLayer(layer: var Table[uint, seq[Box]], b:Box)=
for j in b.x..<b.x + b.w:
for i in b.y..<b.y + b.h:
let k = tupToInt((j, i))
layer.mgetOrPut(k, @[]).add b
var layer = initTable[uint, seq[Box]]()
var n:uint
for _ in 0..<200:
n += 1
toLayer(layer, Box(
x: rand(10000).uint,
y: rand(1000).uint,
w: rand(100).uint,
h: rand(100).uint,
n: n
))
let t1 = getMonoTime()
var count:int
var fail:int
for i in 0.uint..<10100.uint:
for j in 0.uint..<1100.uint:
let k = tupToInt((i, j))
if layer.hasKey(k):
inc count
else:
inc fail
let t2 = getMonoTime() - t1
let t3 = getMonoTime() - t0
echo t2
echo t3
echo layer.len
echo count
echo fail
let xy = intToTup(1077444)
echo xy
Run
Cheers.
