Daily Coding Problem: Problem #10

Here I am with another problem!

Photo by AltumCode on Unsplash

Problem

Implement a job scheduler which takes in a function f and an integer n, and calls f after n milliseconds.

Solution1: Direct implementation

The straightforward approach will be to write a function that takes a function and an integer as arguments, that waits for n milliseconds and then calls the function. Lets implement it then!

import time
def scheduler(f, n):
    time.sleep(n)
    f()

We may think that the above solution is the best, but its not!. We have consider the real world scenarios. The above methods runs sequentially, also what if we want to schedule functions that take arguments. Lets list them down.

1. Multiple functions must be scheduled
2. Function that take argument must be executed

Now to handle multiple functions, we need to think of multi-threading.
import threading

Solution 2: Multi-threading with list

from time import sleep, time
class Scheduler:
    def __init__(self):
        self.functions = []
        thread = threading.Thread(target=self._poll)
        thread.start()
    def _poll(self):
        while True:
            now = time() * 1000
            if len(self.functions) > 0:
                due, func, args, kwargs = self.functions[0]
                if now > due:
                    func(*args, **kwargs)
                self.functions = [(due, func, args, kwargs) for due, func, args, kwargs in self.functions if due < now]
            sleep(0.01)
    def schedule(self, func, n, *args, **kwargs):
        heapq.heappush(self.functions, (n + time() * 1000, func, args, kwargs))

Time Complexity: O(n)

Space Complexity: O(n)

We maintain a list of functions with its schedule time and arguments as a four value tuple. We run a loop to check if the current time is greater than any of the scheduled function’s time, if so we take that function and execute. The above solution may look optimal, but its not. It can still be optimized. Since the functions from the list are selected based on it scheduled time, we can maintain a heap. Min-heap guarantees that the first element is always the smallest. So when we remove that function, the time taken will be O(log(n)) and not O(n) as in the above solution.

Solution 3: Multi-threading with min-heap

import heapq
import threading
from time import sleep, time
class Scheduler:
    def __init__(self):
        self.functions = []
        heapq.heapify(self.functions)
        thread = threading.Thread(target=self._poll)
        thread.start()
    def _poll(self):
        while True:
            now = time() * 1000
            if len(self.functions) > 0:
                due, func, args, kwargs = self.functions[0]
                if now > due:
                    func(*args, **kwargs)
                    heapq.heappop(self.functions)
            sleep(0.01)
    def schedule(self, func, n, *args, **kwargs):
        heapq.heappush(self.functions, (n + time() * 1000, func, args, kwargs))

Time Complexity: O(log(n))

Space Complexity: O(n)

I hope you guys enjoyed this post.

If you find it helpful, please share and claps are much appreciated! 😄

Feel to ask your queries in the comments section!.