From 421f2e783af773712a5e7a799f7cbaca69ab7a21 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Thu, 21 Feb 2019 21:32:22 -0600 Subject: Priority queue parallel job processing done! Not too bad since I worked it out in Java. Good practice of heapq module in Python! A lot of fun :) --- sources/job_queue.py | 47 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 47 insertions(+) create mode 100644 sources/job_queue.py (limited to 'sources') diff --git a/sources/job_queue.py b/sources/job_queue.py new file mode 100644 index 0000000..8928d4a --- /dev/null +++ b/sources/job_queue.py @@ -0,0 +1,47 @@ +# python3 + +from heapq import heappush, heappop +from collections import namedtuple + +AssignedJob = namedtuple("AssignedJob", ["worker", "started_at"]) + + +def assign_jobs(n_workers, jobs): + # Naive algorithm + result = [] + next_free_time = [0] * n_workers + for job in jobs: + next_worker = min(range(n_workers), key=lambda w: next_free_time[w]) + result.append(AssignedJob(next_worker, next_free_time[next_worker])) + next_free_time[next_worker] += job + + return result + + +def assign_jobs_improved(n_workers, jobs): + result = [] + worker_priority_q = [] + for i in range(n_workers): + heappush(worker_priority_q, (0, i)) + + for j in range(len(jobs)): + pair = heappop(worker_priority_q) + result.append(AssignedJob(pair[1], pair[0])) + heappush(worker_priority_q, (pair[0] + jobs[j], pair[1])) + + return result + + +def main(): + n_workers, n_jobs = map(int, input().split()) + jobs = list(map(int, input().split())) + assert len(jobs) == n_jobs + + assigned_jobs = assign_jobs_improved(n_workers, jobs) + + for job in assigned_jobs: + print(job.worker, job.started_at) + + +if __name__ == "__main__": + main() -- cgit v1.2.3