Model simulation in Lua : probabilistic model with insertions that are uniform on the array of the hashtable and deletions

lua-timed-iterations.lua

math.randomseed(2151) -- (2151)
n = 1<<23

iterations = 100

pow = 1<<31
pow2 = pow>>1
m = 15
offset = 1<<m
it = offset
p = 0.75
MOD = 100000

sums = {}

for k = 1, iterations do

    t = {}
    -- prepare for deletions ! 
    -- a will gather the list of elements present
    a = {}
    del = 1
    ins = 1

    e = 0
    before_time = os.clock()
    for i = 1, n do
        rand = math.random()
        if rand <= p then
            val = math.random(pow2,pow-1) -- large value, uniform modulo 2^t , can only go into hashpart and is uniform in range
            -- for every small t
            while t[val] do -- make sure not already in table !
                val = math.random(pow2,pow-1) 
            end
            t[val] = 1 -- never going into array, uniform position
            a[ins] = val -- a is an array by construction
            ins = ins + 1 -- inserted
        else -- delete an existing element
            if ins > del then -- there must be some element to delete
                t[a[del]] = nil 
                del = del + 1
            end
        end 
        -- if i is a multiple of MOD, we record the time elapsed
        if ( (i%MOD) == 0) then
            after_time = os.clock()
            delta = after_time-before_time
            j = i / MOD -- sums is an array by construction
            if sums[j] then
                sums[j] = sums[j] + delta
            else
                sums[j] = delta
            end
        end
    end

end 

a = MOD
while a <= n do 
    if a >= offset then
        print(string.format("(%d, %f)", a,sums[a/MOD]/iterations)  )
    end
    a = a + MOD
end