Alqoritmlərin optimallaşdırma metodları

4.1 Alqoritmlərin optimallaşdırılmasına ümumi yanaşmalar.

Alqoritmlərin optimallaşdırılması effektiv proqram təminatının hazırlanmasında əsas rol oynayır, bu da icra müddətini və yaddaş istehlakını azaltmağa, habelə sistemlərin genişlənmə qabiliyyətini yaxşılaşdırmağa imkan verir. Konkret tapşırıqlara və şərtlərə əsasən müxtəlif üsullar və yanaşmalar tətbiq olunur.

Alqoritmlərin optimallaşdırılmasına yanaşmalar.

Profilləmə:

Koddakı performans "dar yerləri"ni müəyyən etmək üçün analiz. Python-da cProfile kimi profilləşdirmə alətlərindən istifadə zamanı və yaddaş baxımından ən çox resurs tələb edən kod hissələrini müəyyən etməyə kömək edir.

import cProfile

def example_function():


# sizin kod
cProfile.run('example_function()')

Böl və idarə et:

Tapşırığı daha kiçik alt tapşırıqlara bölmək, onları həll etmək daha asandır. Misal: sürətli çeşidləmə (QuickSort) və birləşmə ilə çeşidləmə (MergeSort) alqoritmləri.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

Dinamik proqramlaşdırma:

Təkrar hesablamalardan qaçmaq üçün alt tapşırıqların əvvəlcədən hesablanmış həllərindən istifadə. Misal: Fibonacci ədədlərinin hesablanması.

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

Münasib məlumat strukturlarından istifadə:

Əməliyyatların daha səmərəli icrasını təmin edən məlumat strukturlarının seçilməsi. Misal: sürətli axtarış üçün hash-tabloların (Python-da dictionaries) istifadəsi.

data = {'açar1': 'dəyər1', 'açar2': 'dəyər2'}
value = data.get('açar1')

4.2 Vaxt və yaddaş mürəkkəbliyinin optimallaşdırılması.

Vaxt mürəkkəbliyinin optimallaşdırılması bizə alqoritmin icra müddətinin əməliyyatların sayının azaldılması ilə azaldılmasını təmin edir.

Nümunə 1:

Sıradan axtarış alqoritmini sıralanmış massivlər üçün binary search ilə təkmilləşdirmək.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Yaddaş mürəkkəbliyinin optimallaşdırılması bizə daha kompakt məlumat strukturlarından istifadə etməklə və ya resursları yenidən bölüşdürməklə yaddaş istifadəsini azaltmağa imkan verir.

Nümunə:

Böyük ardıcıllıqlar ilə işləyərkən yaddaşa qənaət etmək üçün Python-da generatorlardan istifadə.

def large_sequence():
    for i in range(1000000):
        yield i

for number in large_sequence():
    print(number)

4.3 Axtarış və çeşidləmə alqoritmlərinin optimallaşdırılması nümunələri.

1 Axtarış alqoritmlərinin optimallaşdırılması:

Lineyar axtarış:

Sıralanmış məlumatlar üçün lineyar axtarışı binary axtarışla əvəz edin.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Həş-cədvəlində axtarış:

Axtarış üçün həş-cədvəlindən istifadə edərək əməliyyatları sabit vaxtda O(1) yerinə yetirmək mümkündür.

data = {'açar1': 'dəyər1', 'açar2': 'dəyər2'}
value = data.get('açar1')

2 Çeşidləmə alqoritmlərinin optimallaşdırılması:

Bubble çeşidləmə:

Bubble çeşidləməni daha effektiv alqoritmlərlə, məsələn, sürətli çeşidləmə (QuickSort) və ya birləşdirilmiş çeşidləmə (MergeSort) ilə əvəz edin.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

Daxili funksiyalardan istifadə edərək çeşidləmə:

Bir çox proqramlaşdırma dillərində daxili çeşidləmə funksiyaları optimallaşdırılıb və əksər hallarda əl ilə yazılmış alqoritmlərdən daha sürətli işləyir.

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
arr.sort()

Alqoritmlərin optimallaşdırılması effektiv proqram təminatının inkişafının mühüm bir hissəsidir. Profilinq, uyğun məlumat strukturlarından istifadə və dinamik proqramlaşdırma kimi müxtəlif optimallaşdırma metodlarını anlamaq, sizə sürətli və genişlənə bilən həllər yaratmağa imkan verir.