नौकरी निर्धारण एल्गोरिथम

Question

सुझावों के आधार पर परिवर्तित कार्यक्रम। नया कोड: नौकरी निर्धारण एल्गोरिथम 2

मैंने जॉब शेड्यूलिंग के लिए एक एल्गोरिथ्म बनाया है।
एल्गोरिथ्म लूप के लिए दो नेस्टेड के साथ उप-सूचियों के माध्यम से जाता है। छोरों के लिए नेस्टेड के अंदर, एल्गोरिथ्म गिनता है कि प्रत्येक कार्य के लिए कितने कार्य पूरे हुए हैं। यदि यह कार्यों की संख्या के बराबर है, तो उस नौकरी के लिए लाभ को कुल लाभ में जोड़ा जाता है।

आइटम प्रारंभ आइटम अंत में उस मशीन का उपयोग शुरू से अंत तक एक आइटम है। मशीन शुरू मशीन अंत है जब मशीनों आइटम संसाधित कर सकते हैं। एक एकल कार्य एक एकल मशीन आइटम है। किसी कार्य के लिए आवश्यक संख्या को पूरा करने के लिए कार्य हैं, जबकि किए गए कार्य ऐसे कार्य हैं जो अनुसूची में समाप्त होंगे। यदि वे दो गणनाएं समान हैं तो नौकरी की जाती है, और लाभ को लाभ संस्करण में जोड़ा जाता है।

यहाँ कोड है

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

मैं कोड की पठनीयता में सुधार और एल्गोरिथ्म की दक्षता में सुधार करने के तरीकों की तलाश कर रहा हूं।

Answer 1

कार्य

यह अच्छा है कि आप फ़ंक्शंस में कोड कैप्चर करने के बारे में सोच रहे हैं, लेकिन आपने फ़ंक्शंस में जाने के लिए विशेष रूप से सही कोड नहीं चुना है।

यह कुछ तुच्छ है:

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दो-आयामी (नेस्टेड) ​​सूची नहीं है - जब तक कि आप दूसरे आयाम के रूप में स्ट्रिंग अनुक्रमण की गणना नहीं करते हैं। 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गुण के साथ तों का क्रम है :

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