كن حذرًا من مخاطر تعقيد الوقت

اكتب هنا

يُظهر فيديو بيليبيلي هذا أيضًا: [فيديو بيليبيلي] [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، وهذه هي النتيجة:

ن ليست كبيرة

استخدم 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
استخدم Heapq: 0.0001601999392732978
بايثون هيبك: 0.07493270002305508
مرتبة : 0.00010840001050382853
ن = 980
استخدم Heapq: 9.949994273483753e-05
بايثون هيبك: 0.07698320003692061
مرتبة : 0.00010300008580088615
ن = 990
استخدم Heapq: 9.979994501918554e-05
بايثون هيبك: 0.0848745999392122
مرتبة : 0.00012620002962648869

إذا ن كبيرة؟

ن = 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 يكلف الكثير من الوقت.

• لماذا تكلف عملية الفرز القليل من الوقت، بينما تكلف Python Heapq الكثير من الوقت؟
• نظرًا لأن وظيفةsorted()‎ هي دالة مدمجة في لغة Python، يمكنك العثور على مستند رسمي في لغة Python حول هذا الموضوع.

وظيفة Bulit-in أسرع من heapq لأنها مكتوبة بلغة C، وهي لغة مترجمة.

• كيفية تحسينه؟
• يمكنك استخدام الدالة المضمنةsorted() بدلاً من heapq.sort() لتحسين أداء التعليمات البرمجية الخاصة بك. الدالةsorted()‎ هي دالة مضمنة في لغة Python، ويتم تنفيذها في لغة C، وبالتالي فهي أسرع بكثير من heapq.sort()

التشنج

عندما نتعامل مع بيانات كبيرة، يجب علينا استخدام وظيفة مدمجة بدلاً من heapq.sort() لتحسين أداء التعليمات البرمجية الخاصة بنا. يجب أن نكون حذرين من مخاطر تعقيد الوقت عند التعامل مع البيانات الكبيرة. في بعض الأحيان لا يمكن تجنب مخاطر تعقيد الوقت، ولكن يجب أن نحاول تجنبها قدر الإمكان.

ْعَنِّي

مرحبًا، أنا منغكينيوان. أنا طالب. أحب أن أتعلم أشياء جديدة.
يمكنك رؤية جيثب الخاص بي: [MengQinYuan's Github][https://github.com/mengqinyuan]