Difference between revisions of "DeltaClock - simple but extreamly efficient scheduling system"

From RogueBasin
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]