5.5 Algoritmu efektivitāte

Teorija: Big O un optimizācija

Big O notācija apraksta, kā algoritma laiks pieaug ar datu apjomu.

O	Apraksts	Piemērs
O(1)	Konstants	Direct array access
O(log n)	Logaritmisks	Binary search
O(n)	Lineārs	Iteration
O(n log n)	Linearitmisks	Quicksort, Mergesort
O(n²)	Kvadrātisks	Nested loops
O(2^n)	Eksponenciāls	Brute force search

// O(n) - lineārs
for (int i = 0; i < n; i++) {
    cout << arr[i];
}

// O(n²) - kvadrātisks (slikti lielam n)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (arr[i] == arr[j]) ...
    }
}

// O(log n) - bināra meklēšana
int binary_search(vector<int>& arr, int target) {
    int lo = 0, hi = arr.size() - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Kā šo izmantot projektā

Atceries: ar redzamu efektu editorā nepietiek. Paskaidro, kura C++ klase glabā stāvokli, kura metode to maina un kā Godot node struktūra izmanto šo kodu.

Pārbaudi: C++ kods pārbauda failu kļūdas, validē datus, izmanto versijas lauku un pamato algoritmu sarežģītību.

#include <godot_cpp/variant/string.hpp>

using namespace godot;

struct PersistenceCheckpoint {
    String lesson = "5.5 Algoritmu efektivitāte";
    bool uses_cpp = true;
    bool handles_missing_file = true;
    bool validates_data = true;
    bool documents_complexity = true;
};

Praktiskie uzdevumi

1. uzdevums - Iesildies ar gatavu piemēru

Šis ir īss iesildīšanās uzdevums. Nokopē sagatavi, ielīmē to pareizajā koda vietā un palaid. Šeit pietiek droši izmēģināt tēmu 5.5 Algoritmu efektivitāte; detalizētu izpratni veidosi nākamajos uzdevumos.

Kopējamais piemērs vai sagatave: izmanto šo bloku kā starta punktu, nevis kā gala risinājumu.

#include <godot_cpp/variant/string.hpp>

using namespace godot;

struct PersistenceCheckpoint {
    String lesson = "5.5 Algoritmu efektivitāte";
    bool uses_cpp = true;
    bool handles_missing_file = true;
    bool validates_data = true;
    bool documents_complexity = true;
};

Atver darba failu vai rīku. C++ fragmentu ievieto atbilstošajā .cpp vai .hpp failā pie šīs stundas klases.
Nokopē visu piemēra bloku no šī uzdevuma un ielīmē to norādītajā vietā.
Palaid kodu tieši tādu, kāds tas ir, un pārliecinies, ka parādās rezultāts, izvade vai vismaz nav kļūdas paziņojuma.
Atrodi vienu drošu vietu, ko drīkst mainīt: tekstu, skaitli, krāsu, mainīgā vērtību vai testa ierakstu.
Maini tikai šo vienu vērtību un palaid kodu vēlreiz.
Salīdzini rezultātu pirms un pēc izmaiņas. Ja parādās kļūda, atcel pēdējo izmaiņu un palaid vēlreiz.
Turpini pie 2. uzdevuma tikai tad, kad šis mazais piemērs darbojas.

2. uzdevums - Ievieto algoritmu spēles projektā

Pievieno šīs stundas paņēmienu kā nelielu, strādājošu spēles mehānikas daļu.

Izvēlies vienu projekta vietu: spēlētāju, pretinieku, kameru, UI, datu glabāšanu, sadursmi vai līmeņa ģenerēšanu.
Nosauc klases, metodes un mainīgos pēc to lomas, piemēram, PlayerState, velocity, score vai update_ui().
Uzraksti metodi, kas nolasa stāvokli, veic vienu skaidru darbību un atgriež vai parāda rezultātu.
Izsauc šo metodi no piemērotas vietas: _ready(), _process(), _physics_process(), signāla apstrādātāja vai projekta palīgklases.
Pievieno vienu īsu komentāru pie sarežģītākās loģikas vietas.
Pārkompilē projektu un pārbaudi, ka editorā nav kļūdu.
Salabo pirmo atrasto kļūdu pirms pievieno nākamo mehānikas daļu.
Veic Git commit ar īsu tehnisku ziņu par pievienoto C++ funkcionalitāti.

3. uzdevums - Testē mehāniku un izdari secinājumu

Pārbaudi, vai C++ algoritms darbojas paredzami spēles vidē.

Izveido trīs testa scenārijus: parastu darbību, robežgadījumu un kļūdainu vai neērtu spēlētāja darbību.
Palaid parasto scenāriju un pārbaudi rezultātu spēles logā vai Godot konsolē.
Palaid robežgadījumu ar mazāko, lielāko, tukšo vai nulles vērtību, ko mehānika pieļauj.
Palaid kļūdaino scenāriju un pārbaudi, vai projekts neavarē.
Izlabo vienu konkrētu problēmu C++ kodā, node sasaistē vai datu inicializācijā.
Pārkompilē un pārbaudi labojumu vēlreiz ar visiem trim scenārijiem.
Beigās pieraksti vienu secinājumu: kura metode, klase vai algoritma solis vislabāk palīdzēja saprast tēmu 5.5 Algoritmu efektivitāte.

Papildu uzdevums - Pievieno mazu mehāniku

Ja pamatdarbs ir pabeigts, paplašini spēli ar vienu nelielu C++ uzlabojumu.

Izvēlies vienu mazu papildinājumu, kas izmanto to pašu šīs stundas paņēmienu.
Pievieno vienu jaunu atribūtu, metodi, signāla apstrādi, datu elementu vai UI atjauninājumu.
Savieno papildinājumu ar esošo scēnu vai klasi, nevis atstāj to atsevišķā demonstrācijā.
Pārkompilē un pārliecinies, ka pamatmehānika joprojām darbojas.
Saglabā izmaiņas ar Git commit tikai pēc veiksmīgas pārbaudes.

Biežākās kļūdas

Mēģini optimizēt bez profilēšanas: 'Premature optimization is root of all evil' - vienmēr profilē vispirms.
O(n²) paslēpts API: Some Godot funkcijas iekšēji ir O(n) - find_child cikls = O(n²).
Cache invalidation: Aizmirsis update cache pēc datu izmaiņas - bugs.

Godot ekrānuzņēmumi

Godot Profiler logs ar funkciju laika sadalīžumu - top 5 funkcijas un to CPU usage.

Diagramma ar Big O kompleksitāšu līknēm: O(1), O(log n), O(n), O(n²) krāsainas līnijas pa x ass elementu skaits.

Koda piemērs (paplašināts)

// Spatial hash priekš ātras kolīzijas
class SpatialHash {
private:
    static const int CELL_SIZE = 64;
    std::unordered_map<int64_t, std::vector<Node2D*>> grid;

    int64_t cell_key(int cx, int cy) {
        return ((int64_t)cx << 32) | (uint32_t)cy;
    }

public:
    void rebuild(const std::vector<Node2D*>& objects) {
        grid.clear();
        for (Node2D* obj : objects) {
            Vector2 pos = obj->get_position();
            int cx = pos.x / CELL_SIZE;
            int cy = pos.y / CELL_SIZE;
            grid[cell_key(cx, cy)].push_back(obj);
        }
    }

    std::vector<Node2D*> get_nearby(Vector2 pos) {
        int cx = pos.x / CELL_SIZE;
        int cy = pos.y / CELL_SIZE;
        std::vector<Node2D*> result;
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                auto it = grid.find(cell_key(cx + dx, cy + dy));
                if (it != grid.end()) {
                    result.insert(result.end(),
                        it->second.begin(), it->second.end());
                }
            }
        }
        return result;
    }
};

1000 objektu kolīzijas pārbaude: bez optimizācijas - 5 ms, ar spatial hash - 0.3 ms.