[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: efficient timers
- From: Oliver Kroth <oliver.kroth@...>
- Date: Mon, 13 Apr 2015 10:44:56 +0200
Hi Nagaev,
here you are. In this implementation, the events are closures being
called when due.
--
Oliver Kroth
Am 13.04.2015 um 10:38 schrieb Nagaev Boris:
On Mon, Apr 13, 2015 at 8:17 AM, Oliver Kroth <oliver.kroth@nec-i.de> wrote:
Hi Thijs,
not sure if someone else referred to a solution like mine:
I used in one of my projects a so called binary heap as "queue". New events
are inserted at the end and bubbled up. Deleted timers leave a hole that is
filled by inserting the last element and resort the heap. Checking whether
the first (earliest) event is due can be done in O(1) by looking on the
heap's root. Inserting and deleting events can be done in O(log n). The
funny thing is that the heap does not use pointers but is stored in a
contiguous array using the event's index to calculate the parent's and
children's indexes.
May not be the most efficient solution but had the smallest overhead on
checking the due events, and has reasonable effort on queue management.
The Lua implementations is about 100 LOC.
If someone is interested, I may post it.
--
Oliver Kroth
I am interested. Could you post it, please?
Best regards,
Boris Nagaev
#license =_MANIFEST.license
---
--- module for a binary heap with { time, f(params) }
--- f is a function that shall be triggered at time 'time'
--- actually its a closure with all params
--
-- we define an event queue
-- that is a binary heap implemented as array
-- each element is a tupel of when it happens and what happens
-- usually, what is a so called closure, i.e. a function with
-- upvalues uses
-- e.g. schedule( 100, decrement( timers, 1))
-- will first create a function that will, when called, decrement timers[1]
-- and then insert this into the heap
local schedule = {}
local now = os.time
local floor = math.floor
function schedule:bubbleUp( pos )
while pos>1 do
local parent = floor(pos/2)
if self[parent].when <= self[pos].when then break end
self[parent], self[pos]= self[pos], self[parent]
pos = parent
end
end
function schedule:sinkDown( pos )
local last = #self
while true do
local min = pos
local child =2*pos
for c=child, child+1 do
if c <= last and self[c].when < self[min].when then min = c end
end
if min == pos then break end
self[pos], self[min] = self[min], self[pos]
pos = min
end
end
function schedule:remove( pos )
local last = #self
if pos<1 or pos>last then return end
local node = self[ pos ]
if pos<last then
self[pos] = self[last]
self:bubbleUp( pos )
self:sinkDown( pos )
end
self[last] = nil
return node
end
function schedule:get( when )
if #self>0 and self[1].when < (when or now()) then
return self:remove( 1 ).what
end
end
function schedule:put( when, what )
local pos = #self+1
if when < 1000000 then when = when + now() end -- relative time -> absolute
self[pos] = {when=when, what=what}
self:bubbleUp( pos )
end
function schedule:run( when )
when = when or now()
while true do
local what = self:get( when )
if not what then break end
what( when )
end
end
function schedule:schedule( when, what )
if what then
return self:put( when, what )
else
return self:run( when )
end
end
--
-- schedule() will do schedule:run()
-- schedule(when) will do schedule:run(when)
-- schedule(when,what) will do schedule:put(when,what)
setmetatable( schedule, {__call = schedule.schedule })
return schedule