Difference between revisions of "DeltaClock - simple but extreamly efficient scheduling system"
Jump to navigation
Jump to search
(Added DeltaClock page) |
m (Added code example of delta clock) |
||
Line 1: | Line 1: | ||
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. | 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== | |||
<pre> | |||
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] | |||
</pre> |
Revision as of 15:34, 12 February 2013
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]