DeltaClock - simple but extreamly efficient scheduling system
Revision as of 20:28, 13 February 2013 by Hari Seldon (talk | contribs)
There are a few articles describing various scheduling systems out there already, but I am going to present a slightly different data structure which has the potential to be extremely efficient, while maintaining elegance and simplicity. It is based off of the idea of a delta clock, which I first encountered years ago in my operating systems class as an undergrad. I'll describe the algorithm at a high level, and then given an example implementation in Python.
Delta Clock
Comparative Runtime
Code Example
class DeltaClock(object):
class Node(object):
def __init__(self, delta, link):
self.delta = delta
self.link = link
self.events = set()
def __init__(self):
self.head = None
self.nodes = {}
def schedule(self, event, delta):
assert event not in self.nodes
prev, curr = None, self.head
while curr is not None and delta > curr.delta:
delta -= curr.delta
prev, curr = curr, curr.link
if curr is not None and delta == curr.delta:
node = curr
else:
node = DeltaClock.Node(delta, curr)
if prev is None:
self.head = node
else:
prev.link = node
if curr is not None:
curr.delta -= delta
node.events.add(event)
self.nodes[event] = node
def advance(self):
events = self.head.events
for event in events:
del self.nodes[event]
self.head = self.head.link
return events
def unschedule(self, event):
self.nodes[event].events.remove(event)
del self.nodes[event]