Algorytm planowania zadań

Nov 03 2020

Zmieniony program na podstawie sugestii. Nowy kod: algorytm planowania zadań 2

Stworzyłem algorytm planowania zadań.
Algorytm przechodzi przez listy podrzędne w kolejności z dwoma zagnieżdżonymi pętlami for. Wewnątrz zagnieżdżonych pętli for algorytm zlicza, ile zadań dla każdego zadania zostało ukończonych. Jeśli jest to równe liczbie zadań, zysk z tej pracy jest dodawany do całkowitego zysku.

Przedmiot od początku do końca przedmiotu to przedmiot używający tej maszyny od początku do końca. Od początku maszyny do końca maszyny jest to moment, w którym maszyny mogą przetwarzać elementy. Pojedyncze zadanie to jedna maszyna wykonująca określone czynności. Liczba wymagana do wykonania zadania to zadania do wykonania, a zadania wykonane to zadania, które zakończą się w harmonogramie. Jeśli te dwie liczby są równe, praca jest wykonywana, a zysk jest dodawany do zmiennej zysku.

Oto kod

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

Szukam sposobów na poprawę czytelności kodu i poprawę wydajności algorytmu.

Odpowiedzi

2 Reinderien Nov 03 2020 at 16:45

Funkcje

Dobrze, że myślisz o przechwytywaniu kodu w funkcjach, ale nie wybrałeś szczególnie odpowiedniego kodu, aby przejść do funkcji.

To jest trochę trywialne:

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

i nie zasługuje na swoją własną funkcję; po prostu napisz

print(f'profit: {profit}')

na poziomie zewnętrznym. To samo dotyczy output_subset, które nie potrzebuje pętli i może być

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

Zamiast tego coś, co zasługuje na osobną funkcję, to zestaw pętli zaczynający się od for row, który można przetłumaczyć na generator; Zwróć również uwagę, że 0 to domyślny początek dla 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)

Wpisz podpowiedzi

Dobrze, że już tego próbowałeś. subset:[str]powinno być subset: List[str].

Indeksowanie

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

wydaje mi się dziwne. Na podstawie Twojej inicjalizacji itemsnie jest listą dwuwymiarową (zagnieżdżoną) - chyba że liczysz indeksowanie ciągów jako drugi wymiar. rowi coldlatego są nieco błędnie nazwane i są w zasadzie starti end.

Dodatek na miejscu

done_tasks[job_index] = done_tasks[job_index] + 1

Powinien być

done_tasks[job_index] += 1

Podsumowanie z generatorami

        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]
        

może być

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

To jednak rodzi inną kwestię. Rozważ "rotację" struktury danych tak, aby zamiast wielu sekwencji, w których ten sam indeks w każdym odpowiadał opisowi tej samej rzeczy, np.

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

zamiast tego miej sekwencję @dataclasses z atrybutami:

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

Kombinacja predykatu

            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

może po prostu być

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