5.5 Algoritmu efektivitāte
Stundas uzdevums: Apgūt Big O notāciju un optimizēt spēles algoritmus.
80 min plāns: Teorija un paraugs (~10 min) · 1. uzdevums (~20 min) - izmēri divu algoritmu laiku · 2. uzdevums (~25 min) - atrodi un salabo lēno vietu savā spēlē · 3. uzdevums (~20 min) - pierādi uzlabojumu ar mērījumu · Iesniegšana (~5 min).
Pirms sāc: atver savu spēli no 4.6 vai 5.4 stundas. Šodien nemācīsimies jaunu mehāniku - padarīsim esošo ātrāku un to pierādīsim ar skaitļiem.
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++)
{
GD.Print(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 BinarySearch(List<int> arr, int target)
{
int lo = 0;
int hi = arr.Count - 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.
public class PersistenceCheckpoint
{
public string Lesson = "5.5 Algoritmu efektivitāte";
public bool UsesCSharp = true;
public bool HandlesMissingFile = true;
public bool ValidatesData = true;
public bool DocumentsComplexity = true;
}Praktiskie uzdevumi
1. uzdevums -
Izmēri divu algoritmu laiku
Beigās tu redzēsi, ka ligzdots cikls aug daudz straujāk.
- Uzraksti funkciju ar vienu ciklu pār 1000 elementiem.
- Uzraksti otru funkciju ar diviem ligzdotiem cikliem pār to pašu sarakstu.
- Izmēri abas ar
ulong t0 = Time.GetTicksUsec();pirms un pēc. - Izdrukā abus laikus mikrosekundēs.
- Atkārto mērījumu ar 100 elementiem un pieraksti abus rezultātus.
- Izrēķini, cik reižu pieauga katras funkcijas laiks.
- Pieraksti, kura no tām ir O(n) un kura O(n kvadrātā).
Gatavs, kad: palielinot datus 10 reizes, viena cikla laiks aug ~10 reizes, bet ligzdotā - ~100 reizes.
2. uzdevums -
Atrodi un salabo lēno vietu savā spēlē
Beigās tava spēle darbosies raitāk.
- Palaid savu spēli un atver Debugger -> Profiler.
- Nospied Start un spēlē 30 sekundes.
- Atrodi sarakstā funkciju, kas aizņem visvairāk laika.
- Pieraksti tās nosaukumu un laiku.
- Atrodi kodā vietu, kur tā tiek izsaukta katrā kadrā bez vajadzības.
- Pārvieto to ārpus cikla vai izsauc retāk.
- Būvē un palaid profileri vēlreiz.
Gatavs, kad: profilerī tavas izlabotās funkcijas laiks ir manāmi mazāks nekā pirms labojuma.
3. uzdevums -
Pierādi uzlabojumu ar mērījumu
Beigās tev būs skaitļi, nevis sajūta.
- Pieraksti tabulā FPS pirms labojuma un pēc tā.
- Pieraksti arī profilera laiku abos gadījumos.
- Palaid spēli ar dubultu objektu skaitu un atkārto mērījumu.
- Pieraksti, vai uzlabojums saglabājas arī ar lielāku slodzi.
- Izvēlies vēl vienu vietu, ko varētu uzlabot, un pieraksti to.
- Pieraksti, kāpēc nav vērts optimizēt kodu, kas izpildās reti.
- Veic commit ar ziņu par veikto optimizāciju.
Gatavs, kad: tavā tabulā ir četri skaitļi, kas parāda uzlabojumu gan ar parasto, gan ar dubultu slodzi.
Papildu uzdevums - Salīdzini List ar Dictionary meklēšanu
Ja pamatdarbs ir gatavs, izmēri datu struktūru atšķirību.
- Izveido
List<int>ar 10000 elementiem. - Izveido
Dictionary<int, int>ar tiem pašiem datiem. - Izmēri laiku, meklējot pēdējo elementu abās struktūrās.
- Izdrukā abus laikus.
- Pieraksti, kura struktūra bija ātrāka un par cik reizēm.
Gatavs, kad: meklēšana Dictionary ir manāmi ātrāka nekā ciklā pār List.
Ko sagatavo
Stundas mērķis: Tu proti izmērīt koda izpildes laiku, atrast lēnāko vietu ar Godot profileri, to izlabot un ar skaitļiem pierādīt, ka uzlabojums tiešām notika.
GitHub krātuvē jābūt:
- Tabula ar FPS un profilera laiku pirms un pēc labojuma, arī ar dubultu slodzi.
- Ekrānuzņēmums ar Godot profileri pirms labojuma un pēc tā.
- Commit ziņa, kurā aprakstīts, ko tieši optimizēji.
- README.md: kura funkcija bija O(n) un kura O(n kvadrātā) un kā tu to noteici.
Kā iesniedz: Veic commit un push. Skolotāja norādītajā vietā ievieto tikai GitHub krātuves saiti; visiem prasītajiem failiem, README.md pierakstiem un pierādījumiem jābūt pašā krātuvē.
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
Koda piemērs (paplašināts)
using Godot;
using System.Collections.Generic;
// Spatial hash priekš ātras kolīzijas
public class SpatialHash
{
private const int CellSize = 64;
private readonly Dictionary<long, List<Node2D>> grid = new();
private long CellKey(int cx, int cy)
{
return ((long)cx << 32) | (uint)cy;
}
public void Rebuild(IEnumerable<Node2D> objects)
{
grid.Clear();
foreach (Node2D obj in objects)
{
Vector2 pos = obj.Position;
int cx = (int)(pos.X / CellSize);
int cy = (int)(pos.Y / CellSize);
long key = CellKey(cx, cy);
if (!grid.ContainsKey(key)) grid[key] = new List<Node2D>();
grid[key].Add(obj);
}
}
public List<Node2D> GetNearby(Vector2 pos)
{
int cx = (int)(pos.X / CellSize);
int cy = (int)(pos.Y / CellSize);
List<Node2D> result = new();
for (int dx = -1; dx <= 1; dx++)
{
for (int dy = -1; dy <= 1; dy++)
{
if (grid.TryGetValue(CellKey(cx + dx, cy + dy), out List<Node2D> cell))
{
result.AddRange(cell);
}
}
}
return result;
}
}