5
\$\begingroup\$

I've built a discrete event simulation system, similar to the bank problem presented on the wikipedia page but with a key difference.

Let's say, that a TELLER can service two CUSTOMERS at the same time, and that the CUSTOMER-DEPARTURE time depends upon the number of CUSTOMERS a TELLER is servicing concurrently; I need to manage the dynamic CUSTOMER-DEPARTURE event scheduling when the number of concurrently served CUSTOMERS changes.

Consider the following example, where the servicing time for a single customer is of 4 time intervals and is doubled when the teller is servicing two customers at the same time:

t=0  CUSTOMER-ARRIVAL (1)   
t=1  TELLER-BEGINS-SERVICE (1) --> schedules CUSTOMER-DEPARTURE (1) at t_a=5
...
t=3  CUSTOMER-ARRIVAL (2)
t=4  TELLER-BEGINS-SERVICE (1) --> teller is now servicing two customers:
                                   - reschedule CUSTOMER-DEPARTURE (1) to t_b=6
                                   - schedule CUSTOMER-DEPARTURE (2) at t_c=12
...
t=6  CUSTOMER-DEPARTURE (1)    --> teller is now servicing only one customer:
                                   - reschedule CUSTOMER-DEPARTURE (2) at t_d=9
...
t=9  CUSTOMER-DEPARTURE (2)

The times are calculated using this formula:

t = t_current + (4 - completed) * customer_count

Which gives these results for the values used above:

  1. t_a = 1 + (4 - 0) * 1 = 5
  2. t_b = 4 + (4 - 3) * 2 = 6
  3. t_c = 4 + (4 - 0) * 2 = 12
  4. t_d = 6 + (4 - 1) * 1 = 9

I came up with the following code in Python; is there something you would have done differently?

import heapq

class Simulator(object):

    def __init__(self):
        self.queue = []
        self.time = 0


    def schedule(self, time, callback, *args, **kwargs):
        """
        Schedules an event to be executed at a later point in time.
        ``callback`` is a callable which executed the event-specific behavior;
        the optional ``args`` and ``kwargs`` arguments will be passed to the
        event callback at invocation time.

        Returns an object which can be used to reschedule the event.
        """
        assert time > self.time
        event = [time, True, callback, args, kwargs]
        heapq.heappush(self.queue, event)
        return event


    def reschedule(self, event, time):
        """
        Reschedules ``event`` to take place at a different point in time
        """
        assert time > self.time
        rescheduled = list(event)
        event[1] = False
        rescheduled[0] = time
        heapq.heappush(self.queue, rescheduled)
        return rescheduled


    def run(self):
        """
        Simple simulation function to test the behavior
        """
        while self.queue:
            time, valid, callback, args, kwargs = heapq.heappop(self.queue)
            if not valid:
                continue
            self.time = time
            callback(*args, **kwargs)


def event(id, simulator, scheduled, rescheduled=None):
    if rescheduled is None:
        print "Event #{0}: scheduled at {1} and fired at {2}".format(id,
                scheduled, simulator.time)
    else:
        print "Event #{0}: scheduled at {1}, rescheduled at {2} and fired " \
                "at {3}".format(id, scheduled, rescheduled, simulator.time)


s = Simulator()
e1 = s.schedule(5, event, 1, s, 5)
e2 = s.schedule(7, event, 2, s, 7, 12)
e3 = s.schedule(9, event, 3, s, 9)
s.reschedule(e2, 12)
s.run()

\$\endgroup\$

migrated from programmers.stackexchange.com Jul 28 '11 at 0:29

This question came from our site for professionals, academics, and students working within the systems development life cycle.

3
\$\begingroup\$

Given the problem scope as I understand it (need to execute events in particular sequence, with ability to rearrange sequence at any point) I think the design seems clean and direct. I caveat that with: I don't know python, and I seem to be missing the part where you are ensuring sequence of your queue by the event's time member. I understand the event.time needs to be the sequencing key for your queue, or else the reschedule will have erratic behavior as self.time goes forward and backward if the queue isn't in order

The design wholesale seems clean though, to my eyes.

\$\endgroup\$
  • 1
    \$\begingroup\$ Python orders tuples by ordering them by their first member, in case of conflicts, it uses the second and so on; the heapq module can be used as a prioritized queue, where the element returned by heapq.heappop(queue) function always equals sorted(queue)[0]. \$\endgroup\$ – GaretJax Jul 31 '11 at 19:43
0
\$\begingroup\$

Event is some kind of stateful object being modeled as a list. Often a bad idea.

class Event( object ):
    def __init__( self, time, callback, *args, **kwargs ):
        self.time= time
        self.live= True
        self.callback= callback
        self.args= args
        self.kwargs= kwargs
    def invalidate( self ):
        self.live= False
    def __call__( self ):
        if self.live: 
            self.callback( self.*args, **self.kwargs )

This may be better than a list. A list where the order of the arguments is critical is a bad thing waiting to happen.

Code like event[1] = False is utterly opaque. It should be replaced with event.invalidate() so that the meaning is obvious.

Also, once you have an Event class, your separate event function becomes needless. You can subclass event like this.

class MyEvent( Event ):
    def __call__( self, id, simulator, scheduled, rescheduled=None ):
        if rescheduled is None:
            print "Event #{0}: scheduled at {1} and fired at {2}".format(id,
                scheduled, simulator.time)
        else:
            print "Event #{0}: scheduled at {1}, rescheduled at {2} and fired " \
                "at {3}".format(id, scheduled, rescheduled, simulator.time)

Avoid trying to build a "mutable tuple" as a fixed-length list.

Either use immutable named tuples or a proper class.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for taking the time to reply, but this does not address at all my question (actually not true, after the edit to add the code, but this is a long story ;-) ). The problem I have is with the rescheduling part of the priority queue and I'm asking more for design aspects rather than for implementation details (and yes, although I completely agree with your opinions, if you ask me, using an object or a list, is merely an implementation detail; the client never accesses the data in the list or in the object) \$\endgroup\$ – GaretJax Jul 30 '11 at 4:07
  • \$\begingroup\$ "I'm asking more for design aspects rather than for implementation details". You posted code. That means you're asking for implementation details. I can't find a design question. If you want to ask a design question, then you need to (1) actually identify the design issue, and (2) consider posting on Stack Overflow. This is code review. That means implementation. \$\endgroup\$ – S.Lott Aug 1 '11 at 11:05
  • \$\begingroup\$ If you take a look at the question, before it was edited and before it was migrated from programmers (not by me!), the question was: "Which is the best way to—at t=4 and t=6—reschedule the already scheduled events?" \$\endgroup\$ – GaretJax Aug 1 '11 at 15:50
  • 1
    \$\begingroup\$ If someone has to spend more than a few seconds looking at the question, there's a small possibility that the question could stand to have better organization. Not everyone is capable of reading and parsing lots and lots of words and coming to a full understanding. TL;DR: If folks don't get your question, consider fixing it. Second. This is code review. Therefore, claiming you don't want a review of the code is going to be confusing to us who read the questions, expecting to find code and code reviews. If you want design review, you need to use Stack Overflow to discuss design. \$\endgroup\$ – S.Lott Aug 1 '11 at 15:57
  • \$\begingroup\$ You're probably right, but as I said before, I posted the question on programmers.stackexchange.com and ins FAQ you can find these three items: "Algorithm and data structure concepts, Design patterns, Architecture" so I posted to the right site... again I didn't migrate it! \$\endgroup\$ – GaretJax Aug 1 '11 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.