Algorithme de planification des travaux

Question

Programme modifié en fonction des suggestions. Nouveau code: algorithme de planification des travaux 2

J'ai créé un algorithme pour la planification des travaux.
L'algorithme parcourt les sous-listes dans l'ordre avec deux boucles for imbriquées. À l'intérieur des boucles for imbriquées, l'algorithme compte le nombre de tâches terminées pour chaque travail. Si cela est égal au nombre de tâches, le profit pour ce travail est ajouté au profit total.

L'élément du début à la fin de l'élément est un élément utilisant cette machine du début à la fin. Le début de la machine à la fin de la machine correspond au moment où les machines peuvent traiter les articles. Une seule tâche est une seule machine effectuant des éléments. Le nombre requis pour un travail correspond aux tâches à accomplir tandis que les tâches effectuées sont des tâches qui se termineront dans le calendrier. Si ces deux comptes sont égaux, alors le travail est terminé et le profit est ajouté au profit var.

Voici le 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()

Je recherche des moyens d'améliorer la lisibilité du code et d'améliorer l'efficacité de l'algorithme.

Answer 1

Les fonctions

C'est bien que vous réfléchissiez à la façon de capturer du code dans les fonctions, mais vous n'avez pas particulièrement choisi le bon code pour passer aux fonctions.

C'est quelque peu trivial:

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

et ne mérite pas sa propre fonction; écris simplement

print(f'profit: {profit}')

au niveau extérieur. Il en va de même pour output_subset, qui n'a pas besoin de boucle et peut être

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

Au lieu de cela, quelque chose qui ne méritait pas d'être dans une fonction séparée est votre ensemble de boucles à partir for row, ce qui peut être traduit en un générateur; notez également que 0 est le début par défaut pour 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)

Taper des indices

C'est bien que vous ayez essayé cela. subset:[str]devrait être subset: List[str].

Indexage

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

me semble étrange. En fonction de votre initialisation, il itemsne s'agit pas d'une liste bidimensionnelle (imbriquée) - à moins que vous ne comptiez l'indexation de chaînes comme deuxième dimension. rowet colsont donc quelque peu mal nommés, et sont essentiellement startet end.

Ajout sur place

done_tasks[job_index] = done_tasks[job_index] + 1

devrait être

done_tasks[job_index] += 1

Sommation avec générateurs

        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]
        

peut être

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

Cela soulève cependant un autre point. Pensez à "faire pivoter" votre structure de données de sorte qu'au lieu de plusieurs séquences où le même index dans chacune correspond à une description de la même chose, par exemple

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

au lieu d'avoir une séquence de @dataclasses avec des attributs:

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

Combinaison de prédicat

            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

peut juste être

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