Job Scheduling-Algorithmus

Question

Programm aufgrund von Vorschlägen geändert. Neuer Code: Job Scheduling Algorithmus 2

Ich habe einen Algorithmus für die Jobplanung erstellt.
Der Algorithmus durchläuft Unterlisten in der Reihenfolge mit zwei verschachtelten for-Schleifen. Innerhalb der verschachtelten for-Schleifen zählt der Algorithmus, wie viele Aufgaben für jeden Job ausgeführt werden. Wenn dies der Anzahl der Aufgaben entspricht, wird der Gewinn für diesen Job zum Gesamtgewinn addiert.

Artikelanfang bis Artikelende ist ein Artikel, der diese Maschine von Anfang bis Ende verwendet. Maschinenstart bis Maschinenende ist, wenn die Maschinen die Artikel verarbeiten können. Eine einzelne Aufgabe ist eine einzelne Maschine, die Aufgaben ausführt. Die für einen Job erforderliche Anzahl sind Aufgaben, die erledigt werden müssen, während erledigte Aufgaben Aufgaben sind, die im Zeitplan abgeschlossen werden. Wenn diese beiden Zählungen gleich sind, ist die Arbeit erledigt und der Gewinn wird zur Gewinnvariable addiert.

Hier ist der Code

def output_profit(profit:int)->None:
    print("profit: " + str(profit), end = "\n")
    
def output_subset(subset:[str])->None:
    for item in subset:
        print(str(item), end = " ")

def main():
    items = ["a", "b"]
    items_starts = [0, 3]
    items_ends = [2, 4]
    
    #total number of tasks that are needed for job i
    tasks_to_complete = [1,1] 
    
    #tasks that are done for job i 
    done_tasks = [0, 0]
    
    machine_starts = [0, 0]
    machine_ends = [1, 7]
    
    profits_for_job = [10, 12]
    profit = 0
    
    for row in range(0, len(items)):
        for col in range(0, len(items) + 1):
            subset = items[row:col]
            for job_index in range(0, len(subset)):
                if items_starts[job_index] >= machine_starts[job_index]:
                    if items_ends[job_index] <= machine_ends[job_index]:
                        done_tasks[job_index] = done_tasks[job_index] + 1
            profit = 0 
            for job_index in range(0, len(subset)):
                if tasks_to_complete[job_index] == done_tasks[job_index]:
                    profit = profit + profits_for_job[job_index]
            
            output_profit(profit)
            output_subset(subset)
                

if __name__ == "__main__":
    main()

Ich suche nach Möglichkeiten, um die Lesbarkeit des Codes zu verbessern und die Effizienz des Algorithmus zu verbessern.

Answer 1

Funktionen

Es ist gut, dass Sie darüber nachdenken, wie Code in Funktionen erfasst wird, aber Sie haben nicht besonders den richtigen Code ausgewählt, um in Funktionen zu wechseln.

Das ist etwas trivial:

print("profit: " + str(profit), end = "\n")

und verdient keine eigene Funktion; einfach schreiben

print(f'profit: {profit}')

auf der äußeren Ebene. Gleiches gilt für die output_subset, die keine Schleife benötigt und sein kann

    print(' '.join(item for item in subset))

Stattdessen ist es etwas, das es verdient, in einer separaten Funktion zu sein , dass Ihre Schleifen ab beginnen for row, die in einen Generator übersetzt werden können. Beachten Sie auch, dass 0 der Standardstart ist für range:

ProfitPair = Tuple[
    int,
    List[str],
]


def get_profits( ... variables needed for iteration ...) -> Iterable[ProfitPair]:
    for row in range(len(items)):
        for col in range(len(items) + 1):
            subset = items[row:col]
            for job_index in range(len(subset)):
                if items_starts[job_index] >= machine_starts[job_index]:
                    if items_ends[job_index] <= machine_ends[job_index]:
                        done_tasks[job_index] = done_tasks[job_index] + 1
            profit = 0 
            for job_index in range(len(subset)):
                if tasks_to_complete[job_index] == done_tasks[job_index]:
                    profit += profits_for_job[job_index]
            
            yield (profit, subset)

Geben Sie Hinweise ein

Es ist gut, dass Sie das ausprobiert haben. subset:[str]sollte sein subset: List[str].

Indizierung

for row in range(0, len(items)):
    for col in range(0, len(items) + 1):
        subset = items[row:col]

kommt mir komisch vor. Basierend auf Ihrer Initialisierung itemshandelt es sich nicht um eine zweidimensionale (verschachtelte) Liste - es sei denn, Sie zählen die Zeichenfolgenindizierung als zweite Dimension. rowund colsind daher etwas falsch benannt und sind im Grunde startund end.

In-Place-Ergänzung

done_tasks[job_index] = done_tasks[job_index] + 1

sollte sein

done_tasks[job_index] += 1

Summation mit Generatoren

        profit = 0 
        for job_index in range(0, len(subset)):
            if tasks_to_complete[job_index] == done_tasks[job_index]:
                profit = profit + profits_for_job[job_index]
        

kann sein

profit = sum(
    profits_for_job[job_index]
    for job_index in range(len(subset))
    if tasks_to_complete[job_index] == done_tasks[job_index]
)

Dies wirft jedoch einen weiteren Punkt auf. Ziehen Sie in Betracht, Ihre Datenstruktur so zu "drehen", dass anstelle mehrerer Sequenzen, in denen jeweils derselbe Index einer Beschreibung derselben Sache entspricht, z

profits_for_job[job_index]
tasks_to_complete[job_index]
done_tasks[job_index]

haben stattdessen eine Folge von @dataclasses mit Attributen:

job[job_index].profits
job[job_index].tasks_to_complete
job[job_index].tasks_done

Prädikatkombination

            if items_starts[job_index] >= machine_starts[job_index]:
                if items_ends[job_index] <= machine_ends[job_index]:
                    done_tasks[job_index] = done_tasks[job_index] + 1

kann einfach sein

if (
    items_starts[job_index] >= machine_starts[job_index] and
    items_ends[job_index] <= machine_ends[job_index]
):
    done_tasks[job_index] += 1