İş Planlama Algoritması

Question

Önerilere göre Program Değiştirildi. Yeni Kod: İş Planlama Algoritması 2

İş planlaması için bir algoritma oluşturdum.
Algoritma, iç içe geçmiş iki for döngüsüyle alt listelerden geçer. İç içe yerleştirilmiş döngülerin içinde, algoritma her iş için kaç görevin tamamlandığını sayar. Bu görevlerin sayısına eşitse, o işin karı toplam kara eklenir.

Öğe başlangıcından Öğe sonuna kadar bu makineyi baştan sona kullanan bir öğedir. Makine başlangıcı Makine sonu, makinelerin öğeleri işleyebildiği zamandır. Tek bir görev, işleri yapan tek bir makinedir. Bir iş için gereken sayı, tamamlanan görevler programda bitecek görevlerdir. Bu iki sayım eşitse, iş yapılır ve kâr, kâr varlığına eklenir.

İşte 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()

Kod okunabilirliğini ve algoritmanın verimliliğini artırmanın yollarını arıyorum.

Answer 1

Fonksiyonlar

İşlevlerde kodu nasıl yakalayacağınızı düşünmeniz iyi, ancak işlevlere taşımak için özellikle doğru kodu seçmediniz.

Bu biraz önemsiz:

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

ve kendi işlevini hak etmiyor; sadece yaz

print(f'profit: {profit}')

dış seviyede. Aynısı output_subset, bir döngüye ihtiyaç duymayan ve olabilen

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

Bunun yerine, bir şey yok , ayrı bir işleve olmayı hak başlayan döngü sizin kümesidir for rowbir jeneratör tercüme edilebilir; ayrıca 0'ın aşağıdakiler için varsayılan başlangıç ​​olduğunu unutmayın 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)

Tip ipuçları

Bunu denemen iyi oldu. subset:[str]olmalıdır subset: List[str].

Endeksleme

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

bana garip geliyor. İlklendirmenize bağlı itemsolarak, ikinci boyut olarak dize indekslemeyi saymazsanız, iki boyutlu (iç içe geçmiş) bir liste değildir. rowve colbu nedenle bir şekilde yanlış adlandırılmıştır ve temelde startve end.

Yerinde ekleme

done_tasks[job_index] = done_tasks[job_index] + 1

olmalı

done_tasks[job_index] += 1

Jeneratörlerle toplama

        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]
        

olabilir

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

Yine de bu başka bir noktayı gündeme getiriyor. Her birinde aynı dizinin aynı şeyin açıklamasına karşılık geldiği birden çok dizi yerine veri yapınızı "döndürmeyi" düşünün, örneğin

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

bunun yerine @dataclassözniteliklere sahip bir es dizisi var :

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

Dayanak kombinasyonu

            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

sadece olabilir

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