Algoritmo de programación de trabajos

Question

Programa modificado según sugerencias. Nuevo código: algoritmo de programación de trabajos 2

He creado un algoritmo para la programación de trabajos.
El algoritmo recorre las sublistas en orden con dos bucles for anidados. Dentro de los bucles for anidados, el algoritmo cuenta cuántas tareas se completan para cada trabajo. Si es igual a la cantidad de tareas, la ganancia de ese trabajo se agrega a la ganancia total.

El artículo desde el principio hasta el final del artículo es un artículo que utiliza esa máquina de principio a fin. El inicio de la máquina al final de la máquina es cuando las máquinas pueden procesar los artículos. Una sola tarea es una sola máquina que realiza elementos. El número requerido para un trabajo es tareas que se completarán, mientras que las tareas realizadas son tareas que finalizarán en el cronograma. Si esos dos recuentos son iguales, entonces el trabajo está hecho y la ganancia se agrega a la var.

Aqui esta el codigo

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

Estoy buscando formas de mejorar la legibilidad del código y mejorar la eficiencia del algoritmo.

Answer 1

Funciones

Es bueno que esté pensando en cómo capturar código en funciones, pero no ha elegido particularmente el código correcto para pasar a funciones.

Esto es algo trivial:

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

y no merece su propia función; simplemente escribe

print(f'profit: {profit}')

en el nivel exterior. Lo mismo se aplica para output_subset, que no necesita un bucle y puede ser

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

En su lugar, algo que no merecen estar en una función separada es su conjunto de bucles a partir de las for rowque se puede traducir en un generador; también tenga en cuenta que 0 es el inicio predeterminado 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)

Sugerencias de tipo

Es bueno que hayas probado esto. subset:[str]debería ser subset: List[str].

Indexación

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

me parece extraño. Según su inicialización, itemsno es una lista bidimensional (anidada), a menos que cuente la indexación de cadenas como la segunda dimensión. rowy col, por lo tanto, están algo mal nombrados, y son básicamente starty end.

Adición in situ

done_tasks[job_index] = done_tasks[job_index] + 1

debiera ser

done_tasks[job_index] += 1

Suma con generadores

        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]
        

puede 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]
)

Sin embargo, esto plantea otro punto. Considere "rotar" su estructura de datos para que, en lugar de múltiples secuencias donde el mismo índice en cada una corresponda a una descripción de lo mismo, p. Ej.

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

en su lugar, tenga una secuencia de @dataclasses con atributos:

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

Combinación de predicados

            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

puede ser

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