समय जटिलता संबंधी खतरों से सावधान रहें

यहाँ लिखें

एक बिलिबिली वीडियो यह भी दिखाता है: [बिलिबिली वीडियो][https://www.bilibili.com/video/BV16u4m1c7cU/?spm_id_from=333.999.0.0] और मुझे लगता है कि यह एक अच्छा वीडियो है, लेकिन इसकी भाषा चीनी है।

समय की जटिलता

• समय जटिलता का क्या अर्थ है?

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

• समय जटिलता की गणना कैसे करें?

• समय जटिलता की गणना करने के लिए, हमें इनपुट के आकार के एक फ़ंक्शन के रूप में एल्गोरिदम द्वारा किए गए संचालन की संख्या पर विचार करने की आवश्यकता है। ऑपरेशनों की संख्या को मापने का सबसे आम तरीका किसी विशेष ऑपरेशन को निष्पादित करने की संख्या की गणना करना है।

• समय जटिलता की गणना करते समय कुछ सामान्य नुकसान क्या हैं?

• 1. इनपुट आकार पर विचार नहीं करना: यदि हम केवल एल्गोरिदम द्वारा किए गए संचालन की संख्या पर विचार करते हैं, तो हम समय की जटिलता को कम आंक सकते हैं। उदाहरण के लिए, यदि हम एक लूप चलने की संख्या की गणना करते हैं, लेकिन हम इनपुट के आकार को ध्यान में नहीं रखते हैं, तो समय जटिलता बहुत अधिक हो सकती है।
• 1. एल्गोरिदम की दक्षता पर विचार नहीं करना: कुछ एल्गोरिदम इनपुट आकार छोटा होने पर भी कई ऑपरेशन कर सकते हैं, जिससे उच्च समय जटिलता हो सकती है। उदाहरण के लिए, बबल सॉर्ट और चयन सॉर्ट जैसे सॉर्टिंग एल्गोरिदम में द्विघात समय जटिलता होती है, भले ही उन्हें एक छोटे सरणी में केवल दो तत्वों को स्वैप करने की आवश्यकता हो सकती है।
• 1. एल्गोरिदम की सबसे खराब स्थिति पर विचार नहीं करना: कुछ एल्गोरिदम में सबसे अच्छी स्थिति होती है जहां वे सबसे खराब स्थिति की तुलना में कम ऑपरेशन करते हैं। उदाहरण के लिए, बाइनरी सर्च जैसे खोज एल्गोरिदम में सबसे अच्छी स्थिति होती है जहां वे लघुगणक समय में लक्ष्य तत्व ढूंढते हैं, लेकिन उनके पास सबसे खराब स्थिति होती है जहां उन्हें सरणी में सभी तत्वों की जांच करने की आवश्यकता होती है।

आइए समय जटिलता के कुछ उदाहरण देखें

यहां एक प्रश्न है:
किसी सूची में अधिकतम 10 पूर्णांक खोजें।

import random
ls = [random.randint(1, 100) for _ in range(n)]

यहां परीक्षण फ़ंक्शन है:

import time
def benchmark(func, *args) -> float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

समाधान1: ढेर का उपयोग करें

यहां वह समाधान है जो heapq मॉड्यूल का उपयोग करता है:

def find_max_n(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

या हम इसे पायथन तरीके से लिखते हैं:

def find_largest_n(nums, n):
    if n  max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index   1
    right = 2 * index   2
    largest = index

    if left  heap[largest]:
        largest = left

    if right  heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)

समाधान2: सॉर्ट का उपयोग करें

यहां वह समाधान है जो सॉर्ट फ़ंक्शन का उपयोग करता है:

def find_max_n(ls, n):
    return sorted(ls, reverse=True)[:n]

लगभग सभी लोग जानते हैं कि ढेर की समय जटिलता O(n log k) है, और सॉर्ट फ़ंक्शन की समय जटिलता O(n log n) है।

ऐसा लगता है कि पहला समाधान दूसरे से बेहतर है। लेकिन पायथन में यह सच नहीं है।

अंतिम कोड देखें:

import time
def benchmark(func, *args) -> float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

def find_max_n_heapq(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

def find_max_n_python_heap(nums, n):
    if n  max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index   1
    right = 2 * index   2
    largest = index

    if left  heap[largest]:
        largest = left

    if right  heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)


def find_max_n_sorted(ls, n):
    return sorted(ls, reverse=True)[:n]

# test
import random
for n in range(10, 10000, 100):
    ls = [random.randint(1, 100) for _ in range(n)]
    print(f"n = {n}")
    print(f"Use    Heapq: {benchmark(find_max_n_heapq, ls, n)}")
    print(f"Python Heapq: {benchmark(find_max_n_python_heap, ls, n)}")
    print(f"Sorted      : {benchmark(find_max_n_sorted, ls, n)}")

मैं इसे Python3.11 VScode में चलाता हूं, परिणाम यह है:

n बड़ा नहीं है

Heapq का उपयोग करें: 0.002430099993944168
पायथन हीपक: 0.06343129999004304
क्रमबद्ध: 9.280000813305378e-05
एन = 910
Heapq का उपयोग करें: 9.220000356435776e-05
पायथन हीपक: 0.07715500006452203
क्रमबद्ध : 9.360001422464848e-05
एन = 920
Heapq का उपयोग करें: 9.440002031624317e-05
पायथन हीपक: 0.06573969998862594
क्रमबद्ध: 0.00012450001668184996
एन = 930
Heapq का उपयोग करें: 9.689992293715477e-05
पायथन हीपक: 0.06760239996947348
क्रमबद्ध: 9.66999214142561e-05
एन = 940
Heapq का उपयोग करें: 9.600003249943256e-05
पायथन हीपक: 0.07372559991199523
क्रमबद्ध : 9.680003859102726e-05
एन = 950
Heapq का उपयोग करें: 9.770004544407129e-05
पायथन हीपक: 0.07306570000946522
क्रमबद्ध: 0.00011979998089373112
एन = 960
Heapq का उपयोग करें: 9.980006143450737e-05
पायथन हीपक: 0.0771204000338912
क्रमबद्ध: 0.00022829999215900898
एन = 970
हीपक का उपयोग करें: 0.0001601999392732978
पायथन हीपक: 0.07493270002305508
क्रमबद्ध: 0.00010840001050382853
एन = 980
Heapq का उपयोग करें: 9.949994273483753e-05
पायथन हीपक: 0.07698320003692061
क्रमबद्ध: 0.000103000008580088615
एन = 990
Heapq का उपयोग करें: 9.979994501918554e-05
पायथन हीपक: 0.0848745999392122
क्रमबद्ध: 0.00012620002962648869

यदि n बड़ा है?

एन = 10000
हीपक का उपयोग करें: 0.003642000025138259
पायथन हीपक: 9.698883199947886
क्रमबद्ध: 0.00107999995816499
एन = 11000
हीपक का उपयोग करें: 0.0014836000045761466
पायथन हीपक: 10.537632800056599
क्रमबद्ध: 0.0012236000038683414
एन = 12000
हीपक का उपयोग करें: 0.001384599949233234
पायथन हीपक: 12.328411899972707
क्रमबद्ध: 0.0013226999435573816
एन = 13000
हीपक का उपयोग करें: 0.0020017001079395413
पायथन हीपक: 15.637207800056785
क्रमबद्ध: 0.0015075999544933438
एन = 14000
हीपक का उपयोग करें: 0.0017026999266818166
पायथन हीपक: 17.298848500009626
क्रमबद्ध: 0.0016967999981716275
एन = 15000
हीपक का उपयोग करें: 0.0017773000290617347
पायथन हीपक: 20.780625900020823
क्रमबद्ध: 0.0017105999868363142

मैं क्या पाता हूं और इसे कैसे सुधारूं

जब n बड़ा होता है, तो Sorted में थोड़ा समय लगता है (कभी-कभी heapq के उपयोग से भी बेहतर), लेकिन Python Heapq में बहुत अधिक समय लगता है।

• सॉर्टेड में थोड़ा समय क्यों लगता है, लेकिन पायथन हेपक में बहुत अधिक समय लगता है?
• क्योंकि sorted() Python में एक बिल्ट-इन फ़ंक्शन है, आप इसके बारे में Python आधिकारिक दस्तावेज़ पा सकते हैं।

बुलिट-इन फ़ंक्शन heapq से तेज़ है क्योंकि यह C में लिखा गया है, जो एक संकलित भाषा है।

• इसे कैसे सुधारें?
• आप अपने कोड के प्रदर्शन को बेहतर बनाने के लिए heapq.sort() के बजाय अंतर्निहित फ़ंक्शन sorted() का उपयोग कर सकते हैं। सॉर्टेड() फ़ंक्शन पायथन में एक अंतर्निहित फ़ंक्शन है, जिसे सी में लागू किया गया है और इसलिए यह heapq.sort()
से बहुत तेज़ है।

सम्बोधन

जब हम बड़े डेटा के साथ काम कर रहे हैं, तो हमें अपने कोड के प्रदर्शन को बेहतर बनाने के लिए heapq.sort() के बजाय अंतर्निहित फ़ंक्शन का उपयोग करना चाहिए। बड़े डेटा के साथ काम करते समय हमें समय जटिलता के खतरों से सावधान रहना चाहिए। कभी-कभी समय जटिलता के नुकसान अपरिहार्य होते हैं, लेकिन हमें यथासंभव उनसे बचने का प्रयास करना चाहिए।

मेरे बारे में

हैलो, मैं मेंगकिनयुआन हूं। मैं एक छात्र हूँ। मुझे नई चीजें सीखना पसंद है।
आप मेरा जीथब देख सकते हैं: [मेंगक्यूइनयुआन का जीथब][https://github.com/mengqinyuan]