작업 예약 알고리즘
제안에 따라 프로그램을 변경했습니다. 새 코드 : 작업 예약 알고리즘 2
작업 일정을위한 알고리즘을 만들었습니다.
알고리즘은 두 개의 중첩 된 for 루프가있는 순서대로 하위 목록을 통과합니다. 중첩 된 for 루프 내에서 알고리즘은 각 작업에 대해 완료된 작업 수를 계산합니다. 이것이 작업 수와 같으면 해당 작업의 이익이 총 이익에 추가됩니다.
항목 시작부터 항목 끝까지 해당 기계를 처음부터 끝까지 사용하는 항목입니다. 기계 시작에서 기계 종료는 기계가 항목을 처리 할 수있는 때입니다. 단일 작업은 항목을 수행하는 단일 기계입니다. 작업에 필요한 수는 완료해야 할 작업이고 완료된 작업은 일정에서 완료되는 작업입니다. 이 두 카운트가 같으면 작업이 완료되고 이익 변수에 이익이 추가됩니다.
다음은 코드입니다.
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()
코드 가독성을 높이고 알고리즘의 효율성을 향상시킬 방법을 찾고 있습니다.
답변
기능
함수에서 코드를 캡처하는 방법에 대해 생각하고있는 것은 좋지만 함수로 이동할 올바른 코드를 특별히 선택하지 않았습니다.
이것은 다소 사소한 것입니다.
print("profit: " + str(profit), end = "\n")
그리고 자체 기능을 할 자격이 없습니다. 간단히 쓰다
print(f'profit: {profit}')
외부 수준에서. 에도 동일하게 적용되며 output_subset루프가 필요하지 않으며
print(' '.join(item for item in subset))
대신, 뭔가 않는 별도의 기능에있을 자격은 시작 루프의 당신의 집합입니다 for row발전기로 번역 될 수있다; 또한 0은의 기본 시작입니다 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)
유형 힌트
당신이 이것을 시도한 것이 좋습니다. subset:[str]이어야합니다 subset: List[str].
인덱싱
for row in range(0, len(items)):
for col in range(0, len(items) + 1):
subset = items[row:col]
나에게 이상해 보인다. 초기화를 기반으로 items문자열 인덱싱을 두 번째 차원으로 계산하지 않는 한 2 차원 (중첩 된) 목록이 아닙니다. row및 col따라서 다소 잘못된 이름, 기본적으로되어있다 start및 end.
내부 추가
done_tasks[job_index] = done_tasks[job_index] + 1
해야한다
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]
될 수 있습니다
profit = sum(
profits_for_job[job_index]
for job_index in range(len(subset))
if tasks_to_complete[job_index] == done_tasks[job_index]
)
그러나 이것은 또 다른 요점을 제기합니다. 데이터 구조를 "회전"하여 각각의 동일한 인덱스가 동일한 항목의 설명에 해당하는 여러 시퀀스 대신에, 예를 들어
profits_for_job[job_index]
tasks_to_complete[job_index]
done_tasks[job_index]
대신 @dataclass속성 이있는 일련의 es가 있습니다.
job[job_index].profits
job[job_index].tasks_to_complete
job[job_index].tasks_done
술어 조합
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
그냥 될 수 있습니다
if (
items_starts[job_index] >= machine_starts[job_index] and
items_ends[job_index] <= machine_ends[job_index]
):
done_tasks[job_index] += 1