DeltaClock - simple but extreamly efficient scheduling system
Jump to navigation
Jump to search
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]