Algorytm planowania zadań
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
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