4
\$\begingroup\$

Here is my code for the below packet time simulation problem using queue. My code works correctly but it's slow, please help with suggestions to improve run time and other suggestions for performance improvement.

Problem: You are given a series of incoming packets in an array of [t_a, t_d] pairs (one pair for each packet) where t_a is arrival time of the packet and t_d is the processing time required for that packet. The processor has a buffer with a fixed size and when full, packets are dropped. For each packet, output either the start of process time or -1 if the packet is dropped. Processor only processes one packet at the time and packet arrival times are non-decreasing.

eg. input of [ [0, 2], [1, 4], [5, 3] ] with buffer size of 2 gives output equal to [0, 2, 6].

def process_packets(packets, buffSize):
    # base case for packet size or buffSize == 0
    if packets == [] or buffSize == 0:
        return []
    # initializing parameters:
    # ts_te is array of [ts,te] pairs where ts = start of packet process time
    # and te = end of packet process time
    # length of ts_te array is treated as buffer size
    ts_te = [  [ packets[0][0], packets[0][0] + packets[0][1] ]  ]
    # results is either start of packet process time (if packet makes it to buffer)
    # or -1 for packets when buffer is full at their arrival time
    results = [ ts_te[0][0] ]

    # since first packet is processed in initialization, I remove it 
    packets = packets[1:]

    for packet in packets:
        packetArr = packet[0]
        packetDur = packet[1]
        # processor's start time is either end of last packet in buffer or 
        # new packet's arrival time, whichever is bigger
        startTime = max ( ts_te[-1][1], packetArr )

        # removing all packets that have been processed from buffer when new
        # packet arrives
        for elem in ts_te:
            if packetArr >= elem[1]:
                ts_te.pop(0)

        # if there is room in the buffer, add new packets [ts,te] information 
        # and append process time start to result
        if len(ts_te) < buffSize:
            ts_te.append( [startTime , startTime+packetDur] )
            results.append(startTime)
        else:
            results.append(-1)

    return results
\$\endgroup\$
  • 1
    \$\begingroup\$ Could you add more examples to clarify? Does the buffer need to store the packet being processed or not? For example, if the buffer size is 1, and the inputs are (0, 2) and (1, 4), then at time 1, would you say that the sole buffer slot is still occupied by the first packet? Or would you say that the first packet has already being processed, and therefore the buffer slot is free? \$\endgroup\$ – 200_success Aug 4 '18 at 7:49
  • \$\begingroup\$ The processor processors the first packet in buffer and only processes 1 packet a time (i.e., 2 packets w/ same arrival time do not get processed simultaneously even if they are both in buffer). Also, packets are kept in buffer until process is finished, e.g., for buffer size = 2 and current elements in buffer = [ [0,1], [0,1] ] the correct output is [0,1]. It is assumed that when a packet is finished, it is removed from buffer immediately: for example, for buffer of size = 1 , packets = [ [0,1], [1,0] ], both packets will get processed. \$\endgroup\$ – mghah Aug 4 '18 at 17:01
4
\$\begingroup\$

Efficiency

Your algorithm is actually quite simple and efficient. Keeping track of the scheduled finish times for each packet in the buffer (using ts_te) is a great idea. The main problem is your poor choice of data structure for ts_te.

Actually, even though ts_te stores the scheduled start and end times for each buffered packet, you never care about the start times. So, you can just store the end times. (Incidentally, if you had to store a pair of immutable elements, you should use a tuple rather than a list. A list implies that the length may vary or that the contents may change.)

You have a performance problem in ts_te.pop(0). Removing the first item in a list requires all the subsequent elements to be copied over to fill in the hole. What you want is a data structure that lets you efficiently remove items from the head and append items at the tail. Such a structure is called a deque (a double-ended queue), and it's in Python's standard library:

Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

Futhermore, if you specify a maxlen when creating the collections.deque, then it acts as a ring buffer, which is often how fixed-size buffers are implemented in real-life systems.

On a related note, I recommend creating results to be the same size as packets, since you know exactly how long it is supposed to be. That would be more efficient than repeatedly calling .append() and letting Python resize the list as necessary. (Each resizing operation can be expensive, possibly involving the copying of the entire existing contents.) Alternatively, if you don't need the results to be a list, simply yield the results instead of building a list.

Style

Follow PEP 8 naming conventions. buffSize and startTime don't comply.

Avoid introducing special cases. I don't think that buffSize == 0 should result in an empty list; rather, the results should all be -1, since every packet would have to be dropped. Furthermore, your algorithm should be designed so that it does not rely on the buffer always being non-empty.

To avoid writing this:

for packet in packets:
    packetArr = packet[0]
    packetDur = packet[1]

… use destructuring assignments:

for packetArr, packetDur in packets:

As a rule, it's more elegant to write if failure_condition: (e.g detecting a dropped packet) rather than if success_condition:. Usually, failure cases have short code to handle them, and there may be multiple failure cases to handle.

Suggested solution

from collections import deque

def process_packets(packets, bufsize):
    # Stores the scheduled finish times for packets
    buffer = deque(maxlen=bufsize)

    start_times = [None] * len(packets)
    for i, (arrival, duration) in enumerate(packets):
        # Remove packets from the buffer that have been processed by the
        # arrival time.
        while buffer and buffer[0] <= arrival:
            buffer.popleft()

        if len(buffer) >= bufsize:
            # Buffer overrun
            start_times[i] = -1
        else:
            # This packet will start being processed after the finish time of
            # the last buffered packet (if there is anything in the buffer).
            start_times[i] = max(arrival, buffer[-1] if buffer else 0)

            # Store the scheduled finish time for this packet.
            buffer.append(start_times[i] + duration)
    return start_times
\$\endgroup\$

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.