Python Language
कार्यक्रम की पायथन गति

नोटेशन

मूल विचार

आपके पायथन प्रोग्राम की गति का वर्णन करते समय उपयोग किए जाने वाले नोटेशन को बिग-ओ नोटेशन कहा जाता है। मान लीजिए कि आपके पास एक फ़ंक्शन है:

def list_check(to_check, the_list):
    for item in the_list:
        if to_check == item:
          return True
    return False

यह जांचने के लिए एक साधारण कार्य है कि कोई आइटम किसी सूची में है या नहीं। इस फ़ंक्शन की जटिलता का वर्णन करने के लिए, आप O (n) कहेंगे। इसका अर्थ है "आदेश का n" क्योंकि O फ़ंक्शन को आदेश फ़ंक्शन के रूप में जाना जाता है।

O (n) - आमतौर पर n कंटेनर में वस्तुओं की संख्या है

O (k) - आम तौर पर k पैरामीटर का मान या पैरामीटर में तत्वों की संख्या है

सूची संचालन

संचालन: औसत केस (मानदंड अनियमित रूप से उत्पन्न होते हैं)

परिशिष्ट: O (1)

कॉपी: O (n)

डेल टुकड़ा: O (n)

आइटम हटाएं: O (n)

सम्मिलित करें: O (n)

आइटम प्राप्त करें: O (1)

सेट आइटम: O (1)

Iteration: O (n)

स्लाइस प्राप्त करें: O (k)

सेट टुकड़ा: O (n + k)

विस्तार: O (k)

सॉर्ट करें: O (n log n)

गुणा: O (nk)

x इन s: O (n)

न्यूनतम (s), अधिकतम (s): O (n)

लंबाई प्राप्त करें: O (1)

ऑपरेशन चलाएं

एक छल एक दोतरफा कतार है।

class Deque:
def __init__(self):
    self.items = []

def isEmpty(self):
    return self.items == []

def addFront(self, item):
    self.items.append(item)

def addRear(self, item):
    self.items.insert(0,item)

def removeFront(self):
    return self.items.pop()

def removeRear(self):
    return self.items.pop(0)

def size(self):
    return len(self.items)

संचालन: औसत केस (मानदंड अनियमित रूप से उत्पन्न होते हैं)

परिशिष्ट: O (1)

परिशिष्ट: ओ (1)

कॉपी: O (n)

विस्तार: O (k)

विस्तार: ओ (के)

पॉप: ओ (1)

चबूतरे: O (1)

निकालें: O (n)

घुमाएँ: O (k)

संचालन सेट करें

ऑपरेशन: औसत मामला (मानदंड अनियमित रूप से उत्पन्न): सबसे खराब मामला

x इन s: O (1)

अंतर s - t: O (len (s))

अंतर्ग्रहण s & t: O (min (len (s), len (t))): O (len (s) * len (t))

मल्टीपल चौराहा s1 & s2 & s3 & ... & sn:: (n-1) * O (l) जहां l अधिकतम है (len (s1), ..., len (sn))

s.difference_update (t): O (len (t)): O (len (t) * len (s))

s.symetric_difference_update (t): O (len (t))

सममित अंतर s ^ t: O (len (s)): O (len (s) * len (t))

संघ s | t: O (len (s) + लेन (t))

एल्गोरिथम सूचनाएँ ...

कुछ सिद्धांत हैं जो किसी भी कंप्यूटर भाषा में अनुकूलन पर लागू होते हैं, और पायथन कोई अपवाद नहीं है। जैसे ही आप जाते हैं, उसका अनुकूलन न करें : संभव अनुकूलन के संबंध में अपना कार्यक्रम लिखें, यह सुनिश्चित करने के बजाय कि कोड साफ, सही और समझने योग्य है। यदि आपके समाप्त होने पर यह बहुत बड़ा या बहुत धीमा है, तो आप इसे अनुकूलित करने पर विचार कर सकते हैं।

80/20 नियम याद रखें : कई क्षेत्रों में आप 20% प्रयास के साथ परिणाम का 80% प्राप्त कर सकते हैं (जिसे 90/10 नियम भी कहा जाता है - यह इस बात पर निर्भर करता है कि आप किससे बात करते हैं)। जब भी आप कोड का अनुकूलन करने वाले हों, तो यह पता लगाने के लिए प्रोफाइलिंग का उपयोग करें कि निष्पादन का 80% समय कहां जा रहा है, इसलिए आपको पता है कि आपके प्रयास को कहां केंद्रित करना है।

हमेशा "पहले" और "बाद में" बेंचमार्क चलाएं : आप कैसे जानेंगे कि आपकी आशाओं में वास्तव में अंतर आया है? यदि आपका अनुकूलित कोड मूल संस्करण की तुलना में केवल थोड़ा तेज या छोटा है, तो अपने परिवर्तनों को पूर्ववत करें और मूल, स्पष्ट कोड पर वापस जाएं।

सही एल्गोरिदम और डेटा संरचनाओं का उपयोग करें: ओ (एन लॉग एन) क्विकॉर्ट उपलब्ध होने पर एक हजार तत्वों को सॉर्ट करने के लिए ओ (एन 2) बुलबुला सॉर्ट एल्गोरिथ्म का उपयोग न करें। इसी तरह, एक हज़ार आइटम को किसी ऐसे ऐरे में स्टोर न करें, जिसके लिए ओ (एन) एन बाइनरी ट्री, या ओ (1) पाइथन हैश टेबल का उपयोग करने के लिए ओ (एन) खोज की आवश्यकता हो।

नीचे दिए गए लिंक पर अधिक जानकारी के लिए ... पायथन स्पीड अप

निम्नलिखित 3 स्पर्शोन्मुख संकेतन ज्यादातर एल्गोरिदम की समय जटिलता का प्रतिनिधित्व करने के लिए उपयोग किए जाते हैं।

1. Θ संकेतन : थीटा संकेतन ऊपर और नीचे से कार्यों को बांधता है, इसलिए यह सटीक विषम व्यवहार को परिभाषित करता है। एक अभिव्यक्ति की थीटा संकेतन प्राप्त करने का एक सरल तरीका है कम आदेश की शर्तों को छोड़ना और अग्रणी स्थिरांक को अनदेखा करना। उदाहरण के लिए, निम्नलिखित अभिव्यक्ति पर विचार करें। 3n3 + 6n2 + 6000 = 3 (n3) निचले क्रम की शर्तों को छोड़ना हमेशा ठीक होता है क्योंकि इसमें हमेशा एक n0 होता है जिसके बाद Θn2 की तुलना में thann (n3) के उच्च मान होते हैं, चाहे कॉन्स्टेबल शामिल हों। दिए गए फ़ंक्शन g (n) के लिए, हम Θ (g (n)) को दर्शाते हैं, जो कार्यों के सेट का अनुसरण कर रहा है। ) (जी (एन)) = {एफ (एन): वहाँ सकारात्मक स्थिरांक c1, c2 और n0 ऐसे हैं कि 0 <= c1 g (n) <= f (n) <= c2 g (n) सभी n> के लिए = n0} उपरोक्त परिभाषा का अर्थ है, यदि f (n) g (n) का थाटा है, तो मान f (n) हमेशा n1 (n) के बड़े मानों के लिए c1 g (n) और c2 g (n) के बीच है। = एन ०)। थीटा की परिभाषा में यह भी आवश्यक है कि f (n) n0 से अधिक n के मान के लिए गैर-ऋणात्मक होना चाहिए।

2. बिग ओ नोटेशन : बिग ओ नोटेशन एक एल्गोरिथ्म के ऊपरी हिस्से को परिभाषित करता है, यह केवल ऊपर से एक फ़ंक्शन को सीमा देता है। उदाहरण के लिए, प्रविष्टि सॉर्ट के मामले पर विचार करें। यह सबसे अच्छे मामले में रैखिक समय और सबसे बुरे समय में द्विघात समय लेता है। हम सुरक्षित रूप से कह सकते हैं कि प्रविष्टि सॉर्ट की समय जटिलता हे (n ^ 2) है। ध्यान दें कि O (n ^ 2) भी रैखिक समय को कवर करता है। यदि हम प्रविष्टि सॉर्ट की समय जटिलता का प्रतिनिधित्व करने के लिए we नोटेशन का उपयोग करते हैं, तो हमें सबसे अच्छे और बुरे मामलों के लिए दो बयानों का उपयोग करना होगा:

1. प्रविष्टि सॉर्ट की सबसे खराब स्थिति समय जटिलता n (n ^ 2) है।
2. प्रविष्टि सॉर्ट की सबसे अच्छी स्थिति समय जटिलता n (n) है।

बिग ओ नोटेशन तब उपयोगी होता है जब हम केवल एक एल्गोरिथ्म की समय जटिलता पर ऊपरी बाध्य होते हैं। कई बार हम आसानी से एल्गोरिथ्म को देखकर एक ऊपरी सीमा पाते हैं। O (g (n)) = {f (n): वहाँ सकारात्मक स्थिरांक c और n0 मौजूद हैं जैसे 0 <= f (n) <= cg (n) सभी n> = n0} के लिए

3. Ω संकेतन : जिस प्रकार बिग ओ संकेतन एक फ़ंक्शन पर एक असममित ऊपरी बाउंड प्रदान करता है, ation संकेतन एक स्पर्शोन्मुख निचला बाउंड प्रदान करता है। Ω नोटेशन <उपयोगी हो सकता है जब हमारे पास एक एल्गोरिथ्म की समय जटिलता पर कम होता है। जैसा कि पिछली पोस्ट में चर्चा की गई है, एल्गोरिथ्म का सबसे अच्छा मामला प्रदर्शन आम तौर पर उपयोगी नहीं है, ओमेगा संकेतन तीनों में सबसे कम इस्तेमाल किया जाने वाला अंकन है। दिए गए फ़ंक्शन g (n) के लिए, हम Ω (g (n)) फ़ंक्शन के सेट से दर्शाते हैं। ) (G (n)) = {f (n): वहाँ सकारात्मक स्थिरांक c और n0 मौजूद हैं जैसे कि 0 <= cg (n) <= f (n) सभी n> = n0} के लिए। आइए हम यहां समान प्रविष्टि प्रकार पर विचार करें। प्रविष्टि सॉर्ट की समय जटिलता को n (n) के रूप में लिखा जा सकता है, लेकिन यह प्रविष्टि प्रकार के बारे में बहुत उपयोगी जानकारी नहीं है, क्योंकि हम आम तौर पर सबसे खराब मामले में और कभी-कभी औसत मामले में रुचि रखते हैं।