0
\$\begingroup\$

I want to sort object list named schedules according to arrivalT. if arrivalT is equal, I want to sort according to burst, if arrivalT and bursT both equal I want to sort according to id. Is my custom comparitor implementaion correct?

from functools import cmp_to_key
class Pair:
    def __init__(self, id, arrivalT, burstT):
        self.id = id
        self.arrivalT = arrivalT
        self.burstT = burstT
def compare(p1, p2):
    if p1.arrivalT < p2.arrivalT:
        return -1
    elif p1.arrivalT < p2.arrivalT:
        return 1
    else:
        if p1.burstT < p1.burstT:
            return -1
        elif p1.burstT > p2.burstT:
            return 1
        else:
            if p1.id < p2.id:
                return -1
            elif p1.id > p2.id:
                return 1

n = len(id)
schedules = []
for i in range(n):
    schedules.append(Pair(id[i], arrival[i], burst[i]))
schedules = sorted(schedules, key = cmp_to_key(compare))
for i in schedules:
    print(i.id, i.arrivalT, i.burstT)
id =[1, 2, 3, 4]
arrival = [2, 0, 4, 5]
burst = [3, 4, 2, 4 ]
shortestJobFirst(id, arrival, burst)

```
\$\endgroup\$
2
  • 2
    \$\begingroup\$ In terms of correctness insofar as correct results, you need to be at least somewhat confident that your implementation is correct before this is eligible for review. The purpose of review isn't to validate correctness, it's to talk about how well-structured the implementation is, standards adherence, etc. \$\endgroup\$ – Reinderien Jun 6 at 20:04
  • \$\begingroup\$ The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. \$\endgroup\$ – Toby Speight Jun 7 at 7:16
3
\$\begingroup\$

As suggested in another review, you could write a specific function to sort the objects as you like in this one use case. Or you could package these objects up as namedtuple instances, and just sort them directly. But you might not want to convert to nametuple (maybe your class needs some other behaviors). In that case, you have a few options.

One is to use a dataclass and arrange the attributes in the order than you want sorting to occur. This approach is similar to the nametuple strategy in the sense that you must declare the attributes in the desired sorting-order.

from dataclasses import dataclass

@dataclass(frozen = True, order = True)
class Job:
    arrivalT: int
    burstT: int
    id: int

Another option is to define the __lt__() method in the class, so that Python's built-in sorting functions can compare the objects directly.

@dataclass(frozen = True)
class Job:
    id: int
    arrivalT: int
    burstT: int

    def __lt__(self, other):
        return (
            (self.arrivalT, self.burstT, self.id) <
            (other.arrivalT, other.burstT, other.id)
        )

Or if you need more flexibility at runtime, you could write a general purpose function to allow you to sort any objects based on any combination of attributes. This approach would make more sense in situations where you don't know in advance how things should be sorted.

@dataclass(frozen = True)
class Job:
    id: int
    arrivalT: int
    burstT: int

def attrs_getter(*attributes):
    return lambda x: tuple(getattr(x, a) for a in attributes)

# Usage example.
jobs = [Job(1, 4, 3), Job(2, 1, 4), Job(3, 4, 2), Job(4, 1, 4)]
jobs.sort(key = attrs_getter('arrivalT', 'burstT', 'id'))
\$\endgroup\$
1
  • \$\begingroup\$ Great answer! I particularly liked hooking into __lt__. I just want to mention that my first snippet works perfectly fine using a class as well. I just found it convinient in this case to switch to a named tuple =) \$\endgroup\$ – N3buchadnezzar Jun 7 at 7:35
3
\$\begingroup\$

Tips and changes

  1. Python has a style guide PEP 8 which explains in excruciating detail how to structure your code. I whole heartily recommend skimming through it and follow it.

    For instance shortesJobFirst(id, arrival, burst) appears (it is hard to know) to be a function, but functions in python are - according to PEP 8 - written in lowercase seperated by underscores. E.g shortesJobFirst -> shortest_job_first. However if shortesJobFirst is a class, you are good =)

  2. You should use the if __name__ == "__main__": module in your answer.

  3. Your naming practices are somewhat lacking, what does Pair mean? A better name would perhaps have been Job.

  4. It is tough suggesting better names, as you lack a short explanation of what your code does. This is done by using docstrings

  5. The printing could be improved by using pythons awesome formating options

  6. Why use a class at all when a namedtuple() can do the same job?

  7. Why implement a sorting function when you can use attrgetter from operators?

  8. Use a basic linter for your code, this ensures you have correct spacings and indents. As mentioned it is common to have two spaces between classes and functions.

Improvements

from collections import namedtuple
from operator import attrgetter


def sort_jobs_by_attributes(jobs, attributes):
    """
    This functions sorts the jobs (namedtuples) according to the attribute_lst. If

             attribute_lst = ["arrival_time", "burst_time", "id"]

    We then first sort by arrival_time, on tie we
                  sort by burst_time, on tie we
                  sort by id
    """
    for attribute in reversed(attributes):
        jobs.sort(key=attrgetter(attribute))
    return jobs


JOB_ATTRIBUTES = ["arrival_time", "burst_time", "id"]
Job = namedtuple("Job", JOB_ATTRIBUTES)


if __name__ == "__main__":

    job_ids = [1, 2, 3, 4]
    arrival_times = [4, 1, 4, 1]
    burst_times = [3, 4, 2, 4]

    jobs = [
        Job(*job_details) for job_details in zip(arrival_times, burst_times, job_ids)
    ]

    sort_jobs_by_attributes(jobs, JOB_ATTRIBUTES)

    for job in jobs:
        print(job)

Side note: you don't need to provide any key function. The default behavior of tuples (and by extension, namedtuples, since they are a subclass) is to sort element-wise. That means that the first elements of the two tuples are compared, and if there's a tie then the second elements are compared, and so on. Since the name is the first element, all you need is sorted(jobs).

from collections import namedtuple

JOB_ATTRIBUTES = ["arrival_time", "burst_time", "id"]
Job = namedtuple("Job", JOB_ATTRIBUTES)


if __name__ == "__main__":

    job_ids = [1, 2, 3, 4]
    arrival_times = [4, 1, 4, 1]
    burst_times = [3, 4, 2, 4]
    job_details = [arrival_times, burst_times, job_ids]

    jobs = sorted(
        Job(*details) for details in zip(*job_details)
    )

    for job in jobs:
        print(job)

Note that implicitly sorting the tuple can be a bit spooky if you later decide the change around the order. In addition to make it harder to see exactly what is being sorted. I will leave it up to you to make the final call on which version is the best.

\$\endgroup\$
2
  • \$\begingroup\$ This is a good review. Can be done in one sort call, if so inclined: sort(key = lambda j: tuple(getattr(j, a) for a in attributes)). \$\endgroup\$ – FMc Jun 6 at 21:57
  • \$\begingroup\$ @FMc good comment. In fact you do not need any keys ;-) See the edit above. \$\endgroup\$ – N3buchadnezzar Jun 6 at 22:09

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.