DeltaClock - simple but extreamly efficient scheduling system

From RogueBasin
Revision as of 20:28, 13 February 2013 by Hari Seldon (talk | contribs)
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]