Algoritmo de programação de trabalho

Question

Programa alterado com base em sugestões. Novo Código: Algoritmo de Agendamento de Trabalho 2

Eu criei um algoritmo para agendamento de trabalho.
O algoritmo passa por sublistas em ordem com dois loops for aninhados. Dentro dos loops for aninhados, o algoritmo conta quantas tarefas para cada trabalho são concluídas. Se isso for igual ao número de tarefas, o lucro desse trabalho é adicionado ao lucro total.

Item start to item end é um item que usa aquela máquina do início ao fim. O início da máquina até o final da máquina é quando as máquinas podem processar os itens. Uma única tarefa é uma única máquina fazendo itens. O número necessário para um trabalho é de tarefas a serem concluídas, enquanto as tarefas concluídas são tarefas que serão concluídas na programação. Se essas duas contagens forem iguais, o trabalho está concluído e o lucro é adicionado à var.

Aqui está o código

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

Estou procurando maneiras de melhorar a legibilidade do código e melhorar a eficiência do algoritmo.

Answer 1

Funções

É bom que você esteja pensando em como capturar código em funções, mas não escolheu particularmente o código certo para mover para funções.

Isso é um tanto trivial:

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

e não merece função própria; simplesmente escreva

print(f'profit: {profit}')

no nível externo. O mesmo se aplica a output_subset, que não precisa de um loop e pode ser

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

Em vez disso, algo que não merece estar em uma função separada é o seu conjunto de loops a partir de for row, que pode ser traduzido em um gerador; Observe também que 0 é o início padrão para 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)

Dicas de digitação

É bom que você tenha experimentado isso. subset:[str]deveria ser subset: List[str].

Indexando

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

parece estranho para mim. Com base na sua inicialização, itemsnão é uma lista bidimensional (aninhada) - a menos que você conte a indexação de string como a segunda dimensão. rowe colsão, portanto, um tanto errados, e são basicamente starte end.

Adição no local

done_tasks[job_index] = done_tasks[job_index] + 1

deveria estar

done_tasks[job_index] += 1

Soma com geradores

        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]
        

pode ser

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

Isso levanta outro ponto, no entanto. Considere "girar" sua estrutura de dados de modo que, em vez de várias sequências onde o mesmo índice em cada uma corresponda a uma descrição da mesma coisa, por exemplo

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

em vez disso, tenha uma sequência de @dataclasses com atributos:

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

Combinação de predicado

            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

pode ser apenas

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