1.4 โครงสร้างข้อมูลและอัลกอริทึม

ตอนนี้คุณรู้แล้วว่า memory ทำงานยังไง: byte ที่มีเลข address, stack กับ heap, array ที่เรียงต่อกันเป็นแถว และทำไมข้อมูลที่อยู่ติดกันถึงอ่านได้เร็ว (cache locality — CPU ดึงข้อมูลก้อนที่อยู่ใกล้ ๆ เข้ามาทีเดียวทั้งก้อน) บทนี้ว่าด้วย data structure (วิธีจัดเรียงข้อมูลใน memory) และ algorithm (ขั้นตอนวิธีทำงานกับข้อมูลนั้น) การเลือกคู่ที่เหมาะสมมักเป็นตัวชี้ขาดระหว่างเกมที่รันนิ่ง 60 เฟรมต่อวินาที กับเกมที่กระตุก

ทุกหัวข้อในบทนี้จะเป็นรูปแบบเดียวกัน: โค้ดสั้น ๆ ที่รันได้จริง, output จริงที่มันพิมพ์ออกมา, แล้วค่อยอธิบายแบบเข้าใจง่าย ลองพิมพ์ตามแล้วรันดู การได้เห็น output จริงคือวิธีที่ทำให้จำได้

1. Big-O: งานเพิ่มขึ้นแค่ไหนเมื่อข้อมูลใหญ่ขึ้น

Big-O คือวิธีบอกว่าปริมาณงานที่ algorithm ต้องทำเปลี่ยนไปยังไงเมื่อ input ใหญ่ขึ้น มันไม่ใช่จำนวนวินาที และไม่ใช่ผลการจับเวลา มันตอบคำถามเดียวคือ ถ้าให้ข้อมูลมากขึ้น 10 เท่า งานจะเพิ่มขึ้น 10 เท่า, 100 เท่า หรือแทบไม่เพิ่มเลย?

ต่อไปนี้คือฟังก์ชันสองตัวที่ทำงานกับ std::vector<int> (array ที่ปรับขนาดได้) สังเกตว่าแต่ละตัวทำงานมากน้อยแค่ไหน

#include <vector>
#include <iostream>

int first(const std::vector<int>& v) {   // O(1): one step
    return v[0];                          // jump straight to slot 0
}

int sumAll(const std::vector<int>& v) {  // O(n): one step per element
    int total = 0;
    for (int x : v) total += x;           // loop runs n times
    return total;
}

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    std::cout << first(v) << "\n";
    std::cout << sumAll(v) << "\n";
}

Output:

10
150

first ทำงาน เท่าเดิม ไม่ว่า vector จะมี 5 ตัวหรือ 5 ล้านตัว เราเรียกแบบนี้ว่า O(1) — "constant time" (เวลาคงที่) ส่วน sumAll วนแตะทุกตัวหนึ่งครั้ง ดังนั้นถ้ามี n ตัวก็ทำประมาณ n ก้าว เราเรียกว่า O(n) — "linear time" (เวลาเชิงเส้น) ข้อมูลเพิ่มเป็นสองเท่า งานก็เพิ่มเป็นสองเท่า

ตัวอักษร n หมายถึง "ขนาดของ input" อัตราการโตที่พบบ่อย เรียงจากเร็วสุดไปช้าสุด:

อ่านบล็อกล่างอีกรอบ ที่ n = 1,000 วิธีแบบ O(n^2) ทำงานเป็นล้านก้าว ขณะที่วิธีแบบ O(n) ทำแค่พันก้าว ช่องว่างนี้แหละคือเหตุผลว่าทำไม "เลือก algorithm ตัวไหน" สำคัญกว่า "ใช้ทริกเขียนโค้ดแบบไหน" มาก เมื่อข้อมูลเริ่มใหญ่

algorithm แบบ O(log n) ("log n") จะตัดปัญหาลงครึ่งหนึ่งในทุก ๆ ก้าว การทายเลขระหว่าง 1 ถึง 1000 โดยทายตรงกลางเสมอใช้ประมาณ 10 ครั้ง ไม่ใช่ 1000 ครั้ง เพราะ 2^10 = 1024 การหารครึ่งเป็นพลังที่ทรงพลังมาก

Big-O ไม่สนใจ constant factor — แต่คุณยังรู้สึกถึงมันอยู่ดี

Big-O ตัดตัวคูณคงที่ทิ้ง โค้ดที่ทำ 2*n ก้าว กับโค้ดที่ทำ 100*n ก้าว ทั้งคู่ เป็น O(n) เพราะเมื่อ n โตขึ้น รูปทรงของมันเป็นเส้นตรงเหมือนกัน แต่บนเครื่องจริงตัวหลังช้ากว่า 50 เท่า Big-O บอก รูปทรง ของการโต มันไม่ได้บอก ความเร็ว ดังนั้นเวลาต้องเลือกระหว่างสองโครงสร้างที่มี Big-O เท่ากัน สิ่งที่ตัดสินคือ constant factor — และพฤติกรรม cache ซึ่งเราจะเจอในหัวข้อถัดไป

2. Array กับ linked list: ทำไม cache เป็นตัวตัดสิน

std::vector<int> เก็บสมาชิกแบบ ต่อเนื่อง (contiguous) — เป็น memory ก้อนเดียว ค่าเรียงติดกัน ส่วน std::list<int> (คือ doubly linked list) เก็บสมาชิกแต่ละตัวไว้ในก้อน heap เล็ก ๆ ของตัวเองที่เรียกว่า node และแต่ละ node เก็บ pointer ที่ชี้ไป node ถัดไปและก่อนหน้า node พวกนี้อยู่ตรงไหนใน memory ก็ได้

นี่คือจุดที่น่าประหลาดใจ การเดินไล่ทุกสมาชิกของ vector กับการเดินไล่ทุกสมาชิกของ list ทั้งคู่ เป็น O(n) — Big-O เท่ากัน แต่ vector มักเร็วกว่าหลายเท่า ทำไม? เพราะเรื่องในบท memory: เมื่อ CPU อ่าน address 1000 มันดึงทั้ง cache line (ก้อนที่อยู่ใกล้ ๆ ปกติ 64 byte) เข้ามาทีเดียว ก้อนนั้นมีสมาชิก vector ตัวถัด ๆ ไปอยู่แล้ว จึงอ่านได้ "ฟรี" ส่วน list แต่ละ node อยู่ address สุ่ม ทำให้เกือบทุกก้าวเป็น cache miss — CPU ต้องหยุดรอ memory ที่มันยังไม่มี

#include <vector>
#include <list>
#include <numeric>   // std::accumulate
#include <iostream>

int main() {
    std::vector<int> vec(1000000, 1);   // a million 1s, contiguous
    std::list<int>   lst(1000000, 1);   // a million 1s, scattered nodes

    // Both sum the same way, both are O(n).
    long long a = std::accumulate(vec.begin(), vec.end(), 0LL);
    long long b = std::accumulate(lst.begin(), lst.end(), 0LL);

    std::cout << a << " " << b << "\n";
}

Output:

1000000 1000000

ตัวเลขเท่ากันเป๊ะ แต่ถ้าจับเวลาการเรียก accumulate สองตัวนี้ ฝั่ง vector มักเสร็จเร็วกว่าหลายเท่าบนเครื่องเดียวกัน algorithm เดียวกัน Big-O เดียวกัน แต่ความเร็วจริงต่างกันมาก — การจัดวางใน memory คือทั้งหมดของเรื่อง

3. Dynamic array: std::vector โตยังไง

vector โตได้ แต่ memory ยืดไม่ได้ — ก้อน heap มีขนาดตายตัว ดังนั้นเมื่อ vector เต็ม มันทำสามอย่าง: จองก้อน ใหญ่ขึ้น, คัดลอก สมาชิกเก่าเข้าไปในก้อนใหม่, แล้วคืนก้อนเก่า ทริกที่ทำให้เรื่องนี้ราคาถูกคือ geometric growth (โตแบบทวีคูณ): มันไม่ได้เพิ่มทีละช่อง แต่มักจะ เพิ่มความจุเป็นสองเท่า เรามาสร้างเวอร์ชันจิ๋ว ๆ เพื่อดูของจริงกัน

#include <iostream>

struct IntVec {
    int* data = nullptr;   // heap block holding the elements
    int  size = 0;         // how many slots are used
    int  cap  = 0;         // how many slots exist in total

    void push_back(int value) {
        if (size == cap) {                      // full? make room first
            int newCap = (cap == 0) ? 1 : cap * 2;   // DOUBLE the capacity
            int* bigger = new int[newCap];      // bigger block
            for (int i = 0; i < size; i++)
                bigger[i] = data[i];            // copy old elements over
            delete[] data;                      // free old block
            data = bigger;
            cap  = newCap;
            std::cout << "grew to cap " << cap << "\n";
        }
        data[size] = value;                     // now there is room
        size++;
    }
};

int main() {
    IntVec v;
    for (int i = 0; i < 5; i++) v.push_back(i * 10);
    for (int i = 0; i < v.size; i++) std::cout << v.data[i] << " ";
    std::cout << "\n";
    delete[] v.data;
}

Output:

grew to cap 1
grew to cap 2
grew to cap 4
grew to cap 8
0 10 20 30 40

ไล่ดู: ความจุไปจาก 0 -> 1 -> 2 -> 4 -> 8 เรียก push_back ห้าครั้ง แต่โตแค่สี่ครั้ง และหลังถึงความจุ 8 การ push อีกไม่กี่ครั้งถัดไปก็ฟรี การ push ส่วนใหญ่แค่เขียนหนึ่งช่องแล้วเพิ่ม size จะมีบางครั้งเท่านั้นที่ push แล้วกระตุ้นให้ต้องคัดลอก เมื่อเฉลี่ยต้นทุนของการ push หลาย ๆ ครั้ง แต่ละครั้งจึงราคาถูก — เราเรียกว่า amortized O(1) ("amortized" = เฉลี่ยกระจายไปในหลาย ๆ operation) ถ้า vector โตทีละ +1 แทนที่จะเป็นสองเท่า ทุกครั้งที่ push จะต้องคัดลอกทั้งหมด และการ push n ครั้งจะมีต้นทุนรวม O(n^2) การเพิ่มเป็นสองเท่าคือสิ่งที่ทำให้มันเร็ว

reserve(): ข้ามการโตซ้ำ ๆ เมื่อรู้จำนวนอยู่แล้ว

ถ้าคุณรู้คร่าว ๆ อยู่แล้วว่าจะเพิ่มกี่ตัว ให้บอก vector ล่วงหน้าด้วย reserve มันจะจอง memory ครั้งเดียว ไม่มีการคัดลอกระหว่างลูป

#include <vector>

int main() {
    std::vector<int> v;
    v.reserve(1000);                 // one allocation, capacity now 1000
    for (int i = 0; i < 1000; i++)
        v.push_back(i);              // zero re-grows, zero copies
}

4. Hash map: หาของด้วย key แบบ O(1) โดยเฉลี่ย

Hash map (C++ เรียกว่า std::unordered_map) เก็บคู่ key -> value และให้คุณค้นหา value ด้วย key ได้แทบจะทันที ภายในมันเก็บ array ของ bucket (ช่อง) การจะเก็บ key มันรัน hash function — ฟังก์ชันที่แปลง key ให้เป็นเลขก้อนใหญ่ — แล้วเอาเลขนั้น modulo กับจำนวน bucket เพื่อเลือก index ของ bucket

key ต่างกันสองตัวอาจตกลงใน bucket เดียวกัน — นั่นคือ collision (การชนกัน) map จัดการโดยเก็บ chain (โซ่) เล็ก ๆ ไว้ใน bucket นั้นแล้วเช็ค key จริง ๆ ตราบใดที่ collision เกิดน้อย การค้นหาก็คือ: hash key, กระโดดไปหนึ่ง bucket, เช็คหนึ่งหรือสองรายการ นั่นคือเหตุผลที่การค้นหา, แทรก, และลบเป็น O(1) โดยเฉลี่ย

collision จะเกิดน้อยก็ต่อเมื่อ bucket ไม่แออัดเกินไป load factor คือ จำนวนรายการ / จำนวน bucket เมื่อมันโตเกินขีด (ราว ๆ 1.0 สำหรับ unordered_map) map จะทำ rehash: จอง bucket เพิ่มแล้วจัดวางทุกอย่างใหม่ แนวคิดเดียวกับ vector ที่โต — มีต้นทุนเป็นครั้งคราว แต่เฉลี่ยแล้วถูก

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> score;  // key: name, value: points
    score["alice"] = 10;
    score["bob"]   = 7;
    score["alice"] += 5;             // look up "alice", add 5 -> now 15

    std::cout << "alice: " << score["alice"] << "\n";
    std::cout << "has carol? " << score.count("carol") << "\n";  // 0 = not present

    for (const auto& [name, pts] : score)      // structured binding (C++17)
        std::cout << name << " = " << pts << "\n";
}

Output (ลำดับของลูป ไม่ รับประกัน — hash map ไม่มีลำดับ):

alice: 15
has carol? 0
bob = 7
alice = 15

5. Stack กับ queue

สองตัวนี้ง่าย แต่โผล่มาให้เจอทุกที่ ทั้งคู่มักสร้างทับบน vector หรือ deque อีกที ประเด็นสำคัญอยู่ที่ ลำดับ ที่ของออกมา

• Stack เป็น LIFO — last in, first out (เข้าทีหลัง ออกก่อน) เหมือนกองจาน คุณหยิบใบบนสุด push เพิ่มบนยอด pop เอาออกจากยอด
• Queue เป็น FIFO — first in, first out (เข้าก่อน ออกก่อน) เหมือนต่อแถวที่ร้าน คนมาก่อนได้ก่อน push เพิ่มด้านหลัง pop เอาออกด้านหน้า

#include <stack>
#include <queue>
#include <iostream>

int main() {
    std::stack<int> s;
    s.push(1); s.push(2); s.push(3);
    std::cout << "stack pops: ";
    while (!s.empty()) { std::cout << s.top() << " "; s.pop(); }
    std::cout << "\n";

    std::queue<int> q;
    q.push(1); q.push(2); q.push(3);
    std::cout << "queue pops: ";
    while (!q.empty()) { std::cout << q.front() << " "; q.pop(); }
    std::cout << "\n";
}

Output:

stack pops: 3 2 1
queue pops: 1 2 3

ที่ที่มันโผล่มาในเกม: stack ใช้ทำ "undo", ประวัติปุ่มย้อนกลับของเมนู, หรือ call stack ที่รันฟังก์ชัน recursive ของคุณ ส่วน queue ใช้ทำงานที่รอประมวลผลตามลำดับ, ข้อความ network, หรือ — ที่สำคัญ — frontier (แนวหน้า) ของ breadth-first search ซึ่งเป็นหัวข้อถัดไป

6. Tree กับ binary heap (priority queue ที่ A* ต้องใช้)

Tree คือข้อมูลที่จัดเรียงเป็นลำดับชั้นแบบพ่อ/ลูก: มี root หนึ่งตัวอยู่บนสุด แต่ละ node มีลูกได้หลายตัว ไม่มีวงวน scene graph ของคุณ (ตัวละครมีลำตัว ลำตัวมีแขน แขนมีมือ) เป็น tree ระบบไฟล์ก็เป็น tree

Binary heap เป็น tree พิเศษที่เก็บอย่างกระชับไว้ใน array โดยมีกฎเดียวคือ: ทุก parent เล็กกว่า (หรือเท่ากับ) ลูกของมัน นั่นแปลว่า ค่าที่เล็กที่สุดอยู่บนยอดเสมอ (เรียกว่า min-heap) คุณขอ "ตัวที่ 3" จาก heap ไม่ได้ แต่คุณคว้าตัวที่เล็กที่สุดได้ทันทีเสมอ และการแทรกหรือเอาตัวเล็กสุดออกเป็น O(log n) เพราะตัวนั้นแค่ต้องลอยขึ้นหรือจมลงตามความสูงของ tree ซึ่งราว ๆ log n ชั้น

โครงสร้างที่ยื่นตัวที่เล็กที่สุด (หรือใหญ่ที่สุด) ให้คุณเสมอเรียกว่า priority queue ใน C++ คือ std::priority_queue นี่คือเครื่องมือที่ A* pathfinding ใช้เป๊ะ ๆ เพื่อขยายไปยังช่องที่มีแววดีที่สุดตัวถัดไปเสมอ จึงควรรู้จักไว้ตั้งแต่ตอนนี้

#include <queue>
#include <vector>
#include <iostream>

int main() {
    // A MIN-heap: std::greater makes the smallest value come out first.
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    pq.push(50); pq.push(10); pq.push(30); pq.push(20);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";   // always the current smallest
        pq.pop();
    }
    std::cout << "\n";
}

Output:

10 20 30 50

เรา push เข้าไปแบบสับสน แต่มันออกมาเรียงจากเล็กไปใหญ่ ทีละ pop โดยดีฟอลต์ (ไม่ใส่ std::greater) std::priority_queue เป็น max-heap และจะยื่นตัวใหญ่สุดให้ก่อน

7. Graph กับ BFS: จำนวนก้าวที่สั้นที่สุด

Graph คือ node (หรือเรียก vertex) ที่เชื่อมกันด้วย edge (เส้นเชื่อม) แผนที่ถนน, social network, และช่องเดินได้ของด่านเกม ล้วนเป็น graph วิธีเก็บที่พบบ่อยคือ adjacency list: สำหรับแต่ละ node เก็บ list ของ node ที่มันเชื่อมถึง

Breadth-first search (BFS) ตอบคำถาม "จาก A ไป B ใช้กี่ก้าวน้อยที่สุด?" ใน graph ที่ทุก edge นับเป็นหนึ่งก้าว (graph แบบ unweighted คือไม่มีน้ำหนัก) มันทำงานเหมือนคลื่นน้ำที่แผ่ออก: ไปเยี่ยมทุกอย่างที่ห่าง 1 ก้าว แล้วทุกอย่างที่ห่าง 2 ก้าว เรื่อย ๆ เพราะมันขยายเป็นวงแหวน ครั้งแรกที่ BFS ไปถึง node หนึ่งมันไปถึงด้วยเส้นทาง ที่สั้นที่สุด เครื่องมือที่รักษาลำดับวงแหวนนั้นคือ queue จากหัวข้อ 5

ต่อไปนี้คือ BFS บน grid ช่องกระเบื้อง — เคสคลาสสิกของเกม # คือกำแพง, . คือเดินได้, S คือจุดเริ่ม, G คือเป้าหมาย

#include <iostream>
#include <queue>
#include <vector>
#include <string>

int main() {
    std::vector<std::string> grid = {
        "S....",
        ".###.",
        ".#G#.",
        ".#.#.",
        "....."
    };
    int rows = grid.size();
    int cols = grid[0].size();

    int sr = 0, sc = 0, gr = 0, gc = 0;      // find S and G
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 'S') { sr = r; sc = c; }
            if (grid[r][c] == 'G') { gr = r; gc = c; }
        }

    // dist = steps from S; -1 means "not visited yet"
    std::vector<std::vector<int>> dist(rows, std::vector<int>(cols, -1));
    std::queue<std::pair<int,int>> q;
    dist[sr][sc] = 0;
    q.push({sr, sc});

    int dr[4] = {-1, 1, 0, 0};   // up, down, left, right
    int dc[4] = { 0, 0,-1, 1};

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; // off grid
            if (grid[nr][nc] == '#') continue;                          // wall
            if (dist[nr][nc] != -1)  continue;                          // seen
            dist[nr][nc] = dist[r][c] + 1;   // one more step than here
            q.push({nr, nc});
        }
    }

    std::cout << "shortest steps to goal: " << dist[gr][gc] << "\n";
}

Output:

shortest steps to goal: 8

ดูมันแผ่ออก แต่ละช่องข้างล่างแสดงว่า BFS ใช้กี่ก้าวถึงจะไปถึงมันครั้งแรก ตัวเลขโตออกจาก S เหมือนคลื่นน้ำ และเป้าหมายลงเอยที่ห่าง 8 ก้าว เพราะกำแพงบังคับให้ต้องเดินอ้อมวงแหวนยาว ๆ:

BFS เป็น O(V + E) — มันดูทุก node (V) และทุก edge (E) อย่างมากที่สุดอย่างละหนึ่งครั้ง บน grid ก็ประมาณ "จำนวนช่องกระเบื้อง" นี่คือเครื่องมือที่ถูกต้องเมื่อทุกการเคลื่อนที่มีต้นทุนเท่ากัน เมื่อการเคลื่อนที่มีต้นทุน ต่างกัน (โคลนช้ากว่าถนน) คุณต้องใช้หัวข้อถัดไป

8. เส้นทางสั้นสุดแบบมีน้ำหนัก: Dijkstra และแอบดู A*

คราวนี้ให้แต่ละ edge มี weight (น้ำหนัก คือต้นทุน) BFS ใช้ไม่ได้แล้ว เพราะเส้นทางที่มี edge น้อยสุดอาจไม่ใช่เส้นที่ถูกสุด Dijkstra's algorithm แก้เรื่องนี้ มันคือ BFS ที่ใช้ priority queue แทน queue ธรรมดา: แทนที่จะขยายไปยัง node ที่ใกล้ที่สุดในแง่จำนวนก้าว มันขยายไปยัง node ที่มี ต้นทุนรวมน้อยที่สุดจนถึงตอนนี้ เสมอ นั่นคือสิ่งที่ min-heap จากหัวข้อ 6 ให้เราพอดี

#include <iostream>
#include <vector>
#include <queue>

int main() {
    int n = 5;
    // adjacency list: graph[u] = list of (neighbor, weight)
    std::vector<std::vector<std::pair<int,int>>> graph(n);
    auto addEdge = [&](int u, int v, int w) {
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});     // undirected: goes both ways
    };
    addEdge(0, 1, 4);
    addEdge(0, 2, 1);
    addEdge(2, 1, 2);
    addEdge(1, 3, 1);
    addEdge(2, 3, 5);
    addEdge(3, 4, 3);

    std::vector<int> dist(n, 1000000000);   // "infinity" = not reached yet
    dist[0] = 0;

    using P = std::pair<int,int>;           // (cost so far, node)
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;   // min-heap
    pq.push({0, 0});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;          // an old, worse entry -> skip
        for (auto [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {     // found a cheaper way to v
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i = 0; i < n; i++)
        std::cout << "dist to " << i << " = " << dist[i] << "\n";
}

Output:

dist to 0 = 0
dist to 1 = 3
dist to 2 = 1
dist to 3 = 4
dist to 4 = 7

สังเกต node 1: edge ตรง 0-1 มีต้นทุน 4 แต่ไปทาง 0 -> 2 -> 1 มีต้นทุน 1 + 2 = 3 ซึ่งถูกกว่า Dijkstra จึงรายงาน 3 มันลงเอยที่ต้นทุนรวมที่ถูกที่สุดเสมอ

A* คือ Dijkstra ที่มีคำใบ้

Dijkstra แผ่ออกอย่างสม่ำเสมอไปในทุกทิศทางจนบังเอิญไปถึงเป้าหมาย — มันไม่รู้ว่าเป้าหมายอยู่ทางไหน A* (อ่านว่า "เอ-สตาร์") คือลูปเดียวกัน แต่มันหันหัวไปทางเป้าหมายโดยใช้ heuristic (การเดาต้นทุนที่เหลือถึงเป้าหมายแบบราคาถูก เช่น ระยะเส้นตรงหรือระยะบน grid) priority queue ถูกจัดลำดับด้วย:

ตราบใดที่ heuristic ไม่เคย ประเมินสูงเกิน ต้นทุนที่เหลือ A* ก็ยังหาเส้นทางสั้นที่สุดจริงได้ — เพียงแต่มันตรวจ node น้อยลงมาก เพราะมันเลิกเดินหลงออกจากเป้าหมาย นี่คือเหตุผลที่เกือบทุกเกมใช้ A* ทำ pathfinding การเขียน A* เต็มรูปแบบเป็นบทหลัง ตอนนี้ประเด็นสำคัญคือมันคือ BFS/Dijkstra บวก priority queue บวกการเดาที่ดี

9. Sorting: ใช้ std::sort และรู้ว่าทำไมมันเป็น O(n log n)

การเรียงลำดับโผล่มาตลอด: ลำดับการวาด, leaderboard, เรียงตามระยะทางเพื่อจัดการของที่ใกล้ที่สุดก่อน การเรียงแบบไร้เดียงสาที่วนหาตัวเล็กสุดตัวถัดไปซ้ำ ๆ เป็น O(n^2) — ของพันตัวคือการเปรียบเทียบเป็นล้านครั้ง การเรียงที่ดีเป็น O(n log n) เพราะใช้ทริกหารครึ่ง: แบ่งข้อมูล, เรียงแต่ละครึ่ง, แล้วรวม (merge) ค่า log n คือจำนวนครั้งที่หารครึ่งได้ ส่วน n คืองานในแต่ละชั้น

คุณไม่ต้องเขียน sort เอง std::sort เป็นรูทีน O(n log n) ที่ปรับแต่งมาอย่างหนัก ใช้มันเถอะ

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {5, 2, 9, 1, 5, 6};

    std::sort(v.begin(), v.end());               // ascending, O(n log n)
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";

    // custom order: pass a comparator (returns true if a should come first)
    std::sort(v.begin(), v.end(), [](int a, int b){ return a > b; });
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";
}

Output:

1 2 5 5 6 9
9 6 5 5 2 1

comparator (ฟังก์ชันเล็ก ๆ [](int a, int b){ ... } ที่เรียกว่า lambda) ให้คุณเรียงตามอะไรก็ได้: ศัตรูตามเลือด, ไอเทมตามราคา, sprite ตามพิกัด y คืนค่า true เมื่อ a ควรมาก่อน b

10. Dynamic programming: แก้แต่ละ subproblem ครั้งเดียว แล้วจำไว้

Dynamic programming (DP) ฟังดูหรู แต่แก่นของมันเล็กนิดเดียว: ถ้าปัญหาของคุณแตกออกเป็น subproblem ย่อย ๆ และ subproblem เดิม ๆ โผล่มาซ้ำแล้วซ้ำอีก (overlapping subproblems คือปัญหาย่อยที่ทับซ้อนกัน) ก็ให้คำนวณแต่ละอันครั้งเดียวแล้วเก็บคำตอบไว้ จะได้ไม่ต้องทำซ้ำ การเก็บคำตอบที่คำนวณแล้วเรียกว่า memoization ("memo" เหมือนโน้ตเตือนตัวเอง)

ตัวอย่างคลาสสิกคือลำดับ Fibonacci (fib(n) = fib(n-1) + fib(n-2)) นี่คือ recursion แบบไร้เดียงสา:

long long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);   // recomputes the same values endlessly
}

ดูว่า fib(5) ทำอะไรจริง ๆ fib(3) ถูกคำนวณสองครั้ง, fib(2) สามครั้ง และยิ่งแย่หนักขึ้นมากเมื่อ n โต:

ต้นไม้แบบไร้เดียงสาโตเป็นสองเท่าคร่าว ๆ ทุกครั้งที่ n เพิ่ม +1 — นั่นคือ exponential ใกล้ ๆ O(2^n) การคำนวณ fib(45) แบบนี้เรียกฟังก์ชันประมาณ 3.7 พันล้าน ครั้ง และใช้เวลาหลายวินาที ทีนี้มา cache แต่ละคำตอบครั้งแรกที่หาเจอ:

#include <iostream>
#include <vector>

long long fibMemo(int n, std::vector<long long>& cache) {
    if (n < 2) return n;
    if (cache[n] != -1) return cache[n];      // already solved? reuse it
    cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
    return cache[n];
}

int main() {
    std::vector<long long> cache(50, -1);      // -1 means "not computed yet"
    std::cout << fibMemo(45, cache) << "\n";
}

Output:

1134903170

เวอร์ชัน memoized คำนวณ fib(k) แต่ละตัวเพียงครั้งเดียว ดังนั้น fib(45) ทำการคำนวณจริงประมาณ 46 ครั้ง แทนที่จะเป็น 3.7 พันล้านครั้ง คำตอบเดิม แต่ตอนนี้มันเป็น O(n) และเสร็จทันที นี่คือทั้งหมดของทริก DP: มองหางานที่ทำซ้ำ, เก็บมันไว้, แล้วเปิดดูครั้งหน้า มันขับเคลื่อนเครื่องมือ diff ข้อความ, ปัญหาต้นทุน crafting/inventory, และตัวแก้เกมปริศนามากมาย

11. มุมมองฝั่ง engine: วัดผล อย่าเดา

นี่คือบทเรียนที่แยกความรู้ในตำราออกจากการทำเกมจริง Big-O บอกว่าอะไร scale ยังไง แต่ CPU ยังแคร์อย่างมากว่า ข้อมูลวางตัวยังไงใน memory (หัวข้อ 2) ในทางปฏิบัติ โครงสร้างที่มี Big-O "แย่กว่า" แต่มี layout แบบ contiguous ที่เป็นมิตรกับ cache มักชนะโครงสร้างที่ Big-O "ดีกว่า" แต่ต้องไล่ pointer กระจายไปทั่ว heap

ตัวอย่างเป็นรูปธรรม: ถ้าจะลบของออกจาก collection ที่คุณวนไล่ทุกเฟรม linked list ให้การลบแบบ O(1) ขณะที่การลบจาก vector เป็น O(n) (ต้องขยับสมาชิก) Big-O บอกว่า list ชนะ แต่ในความเป็นจริง vector มักชนะภาพรวม เพราะการ วนไล่ vector ทุกเฟรมเร็วกว่าหลายเท่า (ไม่มี cache miss) และการวนไล่นั้นแหละที่ครองต้นทุนรวม แนวคิดแบบนี้ — จัดข้อมูลเป็น array แบน ๆ แล้วไหลผ่านมัน — เรียกว่า data-oriented design และนี่คือวิธีที่ engine ประสิทธิภาพสูงจัดวาง entity, particle, และ physics body

12. จับเวลา Big-O ของจริง: วัดเป็นมิลลิวินาที

หัวข้อ 1 นับ จำนวนก้าว บนกระดาษ ตอนนี้มาจับเวลาเป็น มิลลิวินาที บนเครื่องจริงกัน เพื่อให้เส้นโค้งการโตเลิกเป็นนามธรรม <chrono> คือนาฬิกาจับเวลามาตรฐาน: อ่านนาฬิกาก่อนเริ่มงาน อ่านอีกทีหลังจบ แล้วลบกัน เราจะรันงานเดิมที่ n ใหญ่ขึ้นเรื่อย ๆ แล้วพิมพ์ว่าแต่ละครั้งใช้เวลาเท่าไร

#include <chrono>
#include <cstdio>
#include <vector>

using Clock = std::chrono::steady_clock;
static double ms(Clock::time_point a, Clock::time_point b){
    return std::chrono::duration<double,std::milli>(b-a).count();
}

int main(){
    printf("O(n) linear scan (sum every element once):\n");
    for(long long N : {1000LL,10000LL,100000LL,1000000LL,10000000LL}){
        std::vector<int> v(N,1);
        auto t0=Clock::now();
        long long s=0;
        for(long long i=0;i<N;i++) s+=v[i];
        auto t1=Clock::now();
        printf("  N=%9lld  time=%9.3f ms\n", N, ms(t0,t1));
    }
    printf("\nO(n^2) nested loop (touch every pair):\n");
    for(int N : {2000,4000,8000,16000}){
        auto t0=Clock::now();
        long long c=0;
        for(int i=0;i<N;i++) for(int j=i+1;j<N;j++) c++;
        auto t1=Clock::now();
        printf("  N=%6d  pairs=%12lld  time=%9.3f ms\n", N, c, ms(t0,t1));
    }
}

Output (ตัวเลขจริงจะต่างกันตามเครื่องและแต่ละรอบ — ให้ดู อัตราส่วน ไม่ใช่เวลาสัมบูรณ์):

O(n) linear scan (sum every element once):
  N=     1000  time=    0.001 ms
  N=    10000  time=    0.011 ms
  N=   100000  time=    0.105 ms
  N=  1000000  time=    1.021 ms
  N= 10000000  time=   13.590 ms

O(n^2) nested loop (touch every pair):
  N=  2000  pairs=     1999000  time=    1.018 ms
  N=  4000  pairs=     7998000  time=    4.055 ms
  N=  8000  pairs=    31996000  time=   16.175 ms
  N= 16000  pairs=   127992000  time=   64.552 ms

อ่านบล็อก O(n): ทุกครั้งที่ n โต 10 เท่า เวลาก็โตราว 10 เท่าตาม (0.001 → 0.011 → 0.105 → 1.02 → 13.6 ms) เป็นเส้นตรง — นั่นคือความรู้สึกของ "linear" บนนาฬิกา

ทีนี้บล็อก O(n^2) ที่ n แค่ เพิ่มเป็นสองเท่า ในแต่ละแถว: เวลากลับ เพิ่มเป็นสี่เท่า (1.0 → 4.1 → 16.2 → 64.6 ms) เพิ่ม input สองเท่าแต่งานเพิ่มสี่เท่า เพราะ 2 ยกกำลังสองเท่ากับ 4 นั่นคือลายนิ้วมือของการโตแบบ quadratic และเป็นเหตุผลว่าทำไมลูป O(n^2) ที่รู้สึกว่าทันใจตอน 2,000 ตัว กลับช้าลง 60 เท่าตอน 16,000 ตัว — และจะใช้เวลาเป็น ชั่วโมง ๆ ตอน 10 ล้านตัว

13. Array กับ linked list จับเวลาบนนาฬิกาจริง ๆ

หัวข้อ 2 กล่าวอ้าง ว่า std::vector ชนะ std::list ที่งาน O(n) เท่ากันเพราะ cache มาเลิกกล่าวอ้างแล้วมาวัดกัน จำนวนเต็มสิบล้านตัวเท่ากัน ลูป "บวกทุกตัว" เดียวกัน ต่างกันแค่ layout ใน memory สองแบบ

#include <vector>
#include <list>
#include <chrono>
#include <cstdio>
using Clock=std::chrono::steady_clock;
static double ms(Clock::time_point a,Clock::time_point b){
    return std::chrono::duration<double,std::milli>(b-a).count();
}
int main(){
    const int N=10000000;
    std::vector<int> v(N,1);
    std::list<int>   l(N,1);

    long long s=0;
    auto t0=Clock::now();
    for(int x: v) s+=x;                // straight sweep through one block
    auto t1=Clock::now();

    long long s2=0;
    for(int x: l) s2+=x;               // hop pointer-to-pointer across the heap
    auto t2=Clock::now();

    printf("vector sum=%lld  time=%8.3f ms\n", s,  ms(t0,t1));
    printf("list   sum=%lld  time=%8.3f ms\n", s2, ms(t1,t2));
    printf("list is %.1fx slower for the SAME O(n) work\n", ms(t1,t2)/ms(t0,t1));
}

ถ้า compile แบบธรรมดา (clang++ -std=c++17 ไม่เปิด optimizer) list ออกมาช้ากว่าแค่ราว 1.6 เท่าบนเครื่องนี้ — build ที่ไม่ optimize จะใส่ต้นทุนก้อนหนา ๆ เท่า ๆ กันให้ทุกบรรทัด ซึ่งกลบความต่างด้าน memory ไป แต่เกมปล่อยจริงเปิด optimizer เสมอ ลอง rebuild ด้วย -O2 (release build) ช่องว่างจริงจะโผล่:

vector sum=10000000  time=   2.959 ms
list   sum=10000000  time=  28.665 ms
list is 9.7x slower for the SAME O(n) work

ช้ากว่าเกือบ สิบเท่า ทั้งที่ไม่มีบรรทัดไหนของ algorithm เปลี่ยนเลย — ทั้งคู่เป็น O(n) ทั้งคู่บวกเลขหนึ่งสิบล้านตัว optimizer เปลี่ยนการกวาดของ vector ให้เป็นลูปกระชับที่เดินตรงผ่าน memory ก้อนเดียว hardware prefetcher จึงป้อน cache line ถัดไปให้ก่อนที่จะถูกร้องขอด้วยซ้ำ ส่วน list เร่งแบบนั้นไม่ได้: แต่ละ node เก็บ pointer ไป node ถัดไป และ CPU ดึง node k+1 ไม่ได้จนกว่าจะอ่าน node k เพื่อรู้ address ของมันก่อน การไล่ pointer แบบอนุกรมที่ถูกบังคับนี้ พร้อม cache miss เกือบทุกก้าว คือภาษีที่หัวข้อ 2 เตือนไว้ — ตอนนี้คุณเห็นขนาดของมันแล้ว

std::vector ตัวจริงก็เพิ่มเป็นสองเท่าเหมือนกัน

หัวข้อ 3 สร้าง vector ของเล่นที่เพิ่มความจุเป็นสองเท่า std::vector ตัวจริงก็ทำแบบเดียวกันเป๊ะ และคุณพิมพ์ capacity() ออกมาดูมันเกิดขึ้นได้:

#include <vector>
#include <cstdio>
int main(){
    std::vector<int> v;
    size_t last=(size_t)-1;
    for(int i=0;i<17;i++){
        v.push_back(i);
        if(v.capacity()!=last){
            printf("size=%2zu  capacity=%2zu\n", v.size(), v.capacity());
            last=v.capacity();
        }
    }
}

Output:

size= 1  capacity= 1
size= 2  capacity= 2
size= 3  capacity= 4
size= 5  capacity= 8
size= 9  capacity=16
size=17  capacity=32

ความจุไต่ขึ้น 1, 2, 4, 8, 16, 32 — เพิ่มเป็นสองเท่า ตรงตามที่ทำนายไว้ การ push สิบเจ็ดครั้งจองก้อน memory รวมแค่หกก้อน (ก้อนแรก แล้วเพิ่มเป็นสองเท่าอีกห้าครั้ง) การ push ที่เหลือแค่เขียนลงในพื้นที่ที่ vector มีอยู่แล้ว ตัวคูณ การโตไม่ได้ถูกกำหนดตายตัวโดยมาตรฐาน — บาง library ใช้ 1.5 เท่าแทน 2 เท่า — แต่มันเป็นแบบ geometric เสมอ และนั่นคือสิ่งที่ทำให้ push_back เป็น amortized O(1) ถ้าคุณรู้ว่าจะเพิ่มราว 5,000 ตัว เรียก v.reserve(5000) ครั้งเดียวก็ข้ามการจองใหม่ทั้งหกครั้งนั้นไปได้

14. เลือก container: ตารางตัดสินใจ

standard library ยื่นชั้นวาง container มาให้เพียบ การเลือกตัวที่ถูกขึ้นกับสองคำถาม: จะเพิ่มและลบของยังไง และ จะหามันเจอได้ยังไง ต่อไปนี้คือห้าตัวที่คุณจะคว้ามาใช้บ่อยที่สุด พร้อมเหตุผลหนึ่งบรรทัดว่าแต่ละตัวมีไว้ทำไม

มีสองตัวที่ใหม่ในที่นี้ std::deque ("เด็ค" คือ double-ended queue คิวสองปลาย) เหมือน vector ที่ push และ pop ด้านหน้าได้ถูก ๆ ด้วย — เป็นตัวที่ std::queue จากหัวข้อ 5 ใช้อยู่ข้างใน ส่วน std::map เก็บ key แบบ เรียงลำดับ โดยใช้ balanced binary search tree (red-black tree) การวนไล่มันจึงออกมาเรียงตามลำดับเสมอ และคุณถามคำถามช่วง (range) ได้ เช่น "key ที่เล็กที่สุดที่ไม่น้อยกว่า K" — สิ่งที่ hash map ทำไม่ได้เลย ราคาคือ O(log n) แทน O(1) และไล่ pointer ตาม node เหมือน list

#include <map>
#include <unordered_map>
#include <deque>
#include <string>
#include <cstdio>
int main(){
    std::map<std::string,int>           ord;   // red-black tree, sorted
    std::unordered_map<std::string,int> hsh;    // hash table, no order
    const char* keys[]={"delta","alpha","charlie","bravo"};
    for(auto k:keys){ ord[k]=1; hsh[k]=1; }

    printf("insertion order:          delta alpha charlie bravo\n");
    printf("std::map order:           ");
    for(auto&kv:ord) printf("%s ", kv.first.c_str());
    printf("\nstd::unordered_map order: ");
    for(auto&kv:hsh) printf("%s ", kv.first.c_str());

    std::deque<int> d;
    d.push_back(2); d.push_back(3);
    d.push_front(1); d.push_front(0);           // O(1) at BOTH ends
    printf("\n\nstd::deque after push_front 0,1 / push_back 2,3: ");
    for(int x:d) printf("%d ", x);
    printf("\n");
}

Output (ลำดับของบรรทัด unordered_map เป็น implementation-defined — ของคุณอาจต่างไป):

insertion order:          delta alpha charlie bravo
std::map order:           alpha bravo charlie delta
std::unordered_map order: charlie bravo alpha delta

std::deque after push_front 0,1 / push_back 2,3: 0 1 2 3 

std::map พิมพ์ key ออกมาเรียงตามตัวอักษรไม่ว่าจะใส่เข้าไปลำดับไหน — tree ที่เรียงลำดับทำงาน ส่วน hash map พิมพ์ตามลำดับ bucket ซึ่งดูมั่ว ๆ และไม่ใช่สิ่งที่ควรพึ่งพา และ deque โตจากทั้งสองปลาย ลงเอยเป็น 0 1 2 3 ทั้งที่ 0 กับ 1 ถูก push เข้าด้าน หน้า หลังจาก 2 กับ 3 ถูก push เข้าด้านหลัง

15. เจาะข้างใน hash map: hash function, collision, load factor

หัวข้อ 4 บอกว่า hash map รัน hash function เพื่อเลือก bucket มาดูของจริงกันว่าฟังก์ชันนั้นคายอะไรออกมา และดูกลไกที่ทำให้การค้นหาเป็น O(1) std::hash คือ object แฮชมาตรฐาน คุณเรียกใช้มันเหมือนฟังก์ชัน

#include <unordered_map>
#include <string>
#include <functional>
#include <cstdio>
int main(){
    std::hash<std::string> h;
    const char* names[]={"alice","bob","carol"};
    for(auto s:names){
        size_t hv=h(s);
        printf("hash(%-6s) = %20zu   %% 8 = %zu\n", s, hv, hv%8);
    }
    printf("\ngrowing an unordered_map<int,int> (watch buckets jump):\n");
    std::unordered_map<int,int> m;
    printf("  start           buckets=%2zu  load=%.2f  (max %.1f)\n",
        m.bucket_count(), m.load_factor(), m.max_load_factor());
    for(int i=1;i<=20;i++){
        size_t before=m.bucket_count();
        m[i]=i;
        const char* note = (m.bucket_count()!=before) ? "  <-- REHASH" : "";
        printf("  after insert %2d  buckets=%2zu  load=%.2f%s\n",
            i, m.bucket_count(), m.load_factor(), note);
    }
}

Output (ตัวเลข hash จริงขึ้นกับ library ของ compiler คุณ; แพตเทิร์น ต่างหากที่เป็นประเด็น):

hash(alice ) = 12039928513911456776   % 8 = 0
hash(bob   ) = 13671481681542908696   % 8 = 0
hash(carol ) =  2926835018909119080   % 8 = 0

growing an unordered_map<int,int> (watch buckets jump):
  start           buckets= 0  load=0.00  (max 1.0)
  after insert  1  buckets= 2  load=0.50  <-- REHASH
  after insert  2  buckets= 2  load=1.00
  after insert  3  buckets= 5  load=0.60  <-- REHASH
  after insert  4  buckets= 5  load=0.80
  after insert  5  buckets= 5  load=1.00
  after insert  6  buckets=11  load=0.55  <-- REHASH
  after insert  7  buckets=11  load=0.64
  after insert  8  buckets=11  load=0.73
  after insert  9  buckets=11  load=0.82
  after insert 10  buckets=11  load=0.91
  after insert 11  buckets=11  load=1.00
  after insert 12  buckets=23  load=0.52  <-- REHASH
  after insert 13  buckets=23  load=0.57
  after insert 14  buckets=23  load=0.61
  after insert 15  buckets=23  load=0.65
  after insert 16  buckets=23  load=0.70
  after insert 17  buckets=23  load=0.74
  after insert 18  buckets=23  load=0.78
  after insert 19  buckets=23  load=0.83
  after insert 20  buckets=23  load=0.87

ค่า hash เป็นเลข 64-bit ก้อนมหึมาที่เกือบสุ่ม — นั่นคืองานทั้งหมดของ hash function: ปั่น key ให้ key ต่างกันกระจายออกอย่างสม่ำเสมอ แต่ทีนี้ดูคอลัมน์ % 8 สิ: ทั้งสามชื่อออกมาเป็น 0 หมด การลดค่า hash ด้วย % 8 เก็บไว้แค่ 3 bit ล่างสุด และตรงนี้ bit พวกนั้นบังเอิญเป็นศูนย์สำหรับทุก key เหล่านี้ — ทั้งสามจึงกองรวมกันใน bucket 0 collision เต็ม ๆ และการค้นหาใน bucket นั้นก็ตกลงเป็นการเดินไล่แบบ O(n)

นั่นแหละคือเหตุผลที่ unordered_map ตัวจริง ไม่ ลดค่าด้วยเลขยกกำลังสองอย่าง 8 ดูจำนวน bucket ในบล็อกที่สอง: 2, 5, 11, 23 — เลข เฉพาะ (prime) การเอา hash modulo กับเลขเฉพาะจะผสม bit ทั้งหมด ไม่ใช่แค่ไม่กี่ bit ล่าง key จึงกระจายแม้ hash ดิบจะมีแพตเทิร์นสม่ำเสมอแบบนี้

บล็อกที่สองยังแสดง load factor (จำนวนรายการหารด้วยจำนวน bucket) ทำหน้าที่ของมัน map ตัวนี้มี max_load_factor เป็น 1.0 ทันทีที่ insert ดัน load factor ขึ้นถึง 1.0 การ insert ครั้งถัดไปจะกระตุ้น rehash: ตารางกระโดดไปที่จำนวน bucket เลขเฉพาะถัดไป (2 แล้ว 5 แล้ว 11 แล้ว 23) และจัดวางทุกรายการใหม่ เป็นการต่อรองแบบ amortized เดียวกับ vector ที่โต — insert ส่วนใหญ่เป็น O(1) มีบางครั้งจ่ายค่าโต และเฉลี่ยออกมาเป็น O(1)

Chaining เทียบกับ open addressing

เมื่อ key สองตัวตกลงใน bucket เดียวกันจริง ๆ map ต้องมีแผน standard library ใช้ separate chaining: แต่ละ bucket เป็น linked list เล็ก ๆ ของรายการที่แฮชมาลงตรงนั้น การค้นหาก็เดินไล่ chain สั้น ๆ นั้นเทียบ key ทางเลือกอีกแบบ ที่ hash map ประสิทธิภาพสูงในเกมส่วนใหญ่ใช้ (dense_hash_map ของ Google, robin_hood, container ของ EA) คือ open addressing: เมื่อชน ก็เขยิบไปดูช่องถัดไป แล้วถัดไปอีก จนเจอช่องว่าง — ทุกรายการอยู่ใน array แบนก้อนเดียว ซึ่งเป็นมิตรกับ cache กว่าการไล่ pointer ของ chain มาก ถ้าคุณต้องการ map ที่เร็วกว่า std::unordered_map flat map แบบ open-addressed มักเป็นคำตอบ ด้วยเหตุผลเรื่อง cache ที่คุณวัดในหัวข้อ 13 เป๊ะ ๆ

16. Sorting ของจริง: std::sort คือ introsort และเรื่อง stability

หัวข้อ 9 บอกว่า "ใช้ std::sort สิ มันเป็น O(n log n)" มีสองเรื่องที่ควรรู้ว่าจริง ๆ แล้วมัน คืออะไร

เรื่องแรก std::sort ไม่ใช่ algorithm เดียว — มันคือ introsort (introspective sort) ตัวลูกผสม มันเริ่มด้วย quicksort ซึ่งเร็วในทางปฏิบัติและมีพฤติกรรม cache ที่ยอดเยี่ยม จุดอ่อนของ quicksort คือการเจอ pivot แย่ ๆ ติดกันอาจฉุดมันลงเป็น O(n^2) introsort จึง เฝ้าดูความลึกของ recursion ตัวเอง และถ้ามันดำดิ่งลึกเกินไป ก็สลับไปใช้ heapsort (รับประกัน O(n log n) สร้างบน heap จากหัวข้อ 6) เพื่อหนีกรณีแย่สุด และสำหรับชิ้นเล็ก ๆ ที่ก้นของ recursion — ปกติ 16 ตัวหรือน้อยกว่า — มันเปลี่ยนไปใช้ insertion sort ซึ่งแทบไม่มี overhead และรวดเร็วกับชุดเล็ก ๆ ที่เกือบเรียงแล้ว quicksort เพื่อความเร็วดิบ, heapsort เป็นตาข่ายนิรภัย, insertion sort สำหรับของชิ้นเล็ก: นั่นคือเหตุผลที่ library บดขยี้ bubble sort ที่เขียนเอง และทำไมคุณไม่ควรปล่อย sort ของตัวเองลงเกม

เรื่องที่สอง และเรื่องนี้กัดคนไม่ทันระวัง: std::sort ไม่ stable "stable" หมายความว่าของสองชิ้นที่เทียบแล้ว เท่ากัน ยังคงลำดับสัมพัทธ์เดิม std::sort ไม่รับประกันแบบนั้น เมื่อคุณต้องการ ให้ใช้ std::stable_sort นี่คือความต่างที่ทำให้เห็นภาพ — event 25 ตัว แต่ละตัวติดป้ายลำดับที่มันมาถึง เรียงตาม priority ที่เป็น 0 หรือ 1 เท่านั้น:

#include <algorithm>
#include <vector>
#include <cstdio>

struct Event { int priority; int arrived; };   // arrived = original order

int main(){
    std::vector<Event> base;
    for(int i=0;i<25;i++) base.push_back({ i%2, i });  // priorities 0,1,0,1,...

    auto cmp=[](const Event&a,const Event&b){ return a.priority<b.priority; };
    auto s1=base, s2=base;
    std::sort(       s1.begin(), s1.end(), cmp);
    std::stable_sort(s2.begin(), s2.end(), cmp);

    printf("arrival order of the priority-0 events:\n");
    printf("  std::sort   : ");
    for(auto&e:s1) if(e.priority==0) printf("%d ", e.arrived);
    printf("\n  stable_sort : ");
    for(auto&e:s2) if(e.priority==0) printf("%d ", e.arrived);
    printf("\n");
}

Output:

arrival order of the priority-0 events:
  std::sort   : 0 24 4 6 8 10 12 14 16 18 2 20 22
  stable_sort : 0 2 4 6 8 10 12 14 16 18 20 22 24 

event priority-0 ทุกตัว "เท่ากัน" ในสายตาของ comparator ผลลัพธ์ทั้งคู่จึงเรียงตาม priority ถูกต้อง แต่ดูเลขลำดับการมาถึงของมันสิ stable_sort คงลำดับที่มันมาถึงไว้ — 0 2 4 6 ... ส่วน std::sort สับมันใหม่ — 24 กับ 2 กระโดดออกนอกที่ — เพราะมันมีอิสระที่จะเรียงของที่เท่ากันใหม่ และการแบ่งพาร์ทิชันของ quicksort ก็ทำแบบนั้นพอดี (การสับที่แน่นอนขึ้นกับ implementation; สิ่งเดียวที่รับประกันคือ stable_sort คงลำดับ ส่วน std::sort ไม่คง)

17. Object pool: ใช้ซ้ำแทนการจองใหม่

การขอ memory จากระบบ (new หรือ container ที่ต้องโต) ไม่ฟรี — การจองครั้งเดียวอาจกินเวลาหลายร้อยนาโนวินาที มันอาจติดล็อกภายใน และเมื่อเวลาผ่านไปมันทำให้ heap แตกเป็นเสี่ยง (fragment) เกมที่ทำ new Bullet() ทุกครั้งที่ผู้เล่นยิงและ delete ทุกครั้งที่โดน คือการจอง memory หลายพันครั้งต่อวินาที ตรงในลูปเฟรมพอดี และนั่นโผล่มาเป็นอาการกระตุก ทางแก้คือ object pool: จองก้อนของ object ขนาดตายตัว ครั้งเดียว แล้วแจกออกไปและรับกลับมาโดยไม่ต้องจองใหม่อีกเลย

pool เก็บ free list — index ของช่องที่ยังไม่ถูกใช้ spawn ดึง index ว่างออกมาแล้วเติมช่องนั้น despawn ดัน index กลับเข้าไป หลังจากสร้างเสร็จ ไม่มีการจองใด ๆ อีกเลย

#include <vector>
#include <cstdio>

struct Bullet { float x, y; bool active=false; };

struct BulletPool {
    std::vector<Bullet> slots;   // fixed block, allocated ONCE
    std::vector<int>    freeList;// indices currently free

    BulletPool(int n) : slots(n) {
        for(int i=n-1;i>=0;i--) freeList.push_back(i);
    }
    int spawn(float x,float y){
        if(freeList.empty()) return -1;         // pool exhausted
        int i=freeList.back(); freeList.pop_back();
        slots[i]={x,y,true};
        return i;
    }
    void despawn(int i){ slots[i].active=false; freeList.push_back(i); }
};

int main(){
    BulletPool pool(3);
    int a=pool.spawn(0,0);
    int b=pool.spawn(1,1);
    printf("spawn a -> slot %d\n", a);
    printf("spawn b -> slot %d\n", b);
    pool.despawn(a);                            // a dies, its slot goes free
    int c=pool.spawn(2,2);                       // no new allocation
    printf("despawn a, spawn c -> slot %d  (reused a's slot: %s)\n",
           c, c==a ? "yes" : "no");
    int d=pool.spawn(3,3);
    int e=pool.spawn(4,4);                        // nothing left
    printf("spawn d -> slot %d\n", d);
    printf("spawn e -> slot %d  (-1 means pool full)\n", e);
}

Output:

spawn a -> slot 0
spawn b -> slot 1
despawn a, spawn c -> slot 0  (reused a's slot: yes)
spawn d -> slot 2
spawn e -> slot -1  (-1 means pool full)

เมื่อ a ถูก despawn ช่อง 0 กลับเข้า free list ดังนั้น spawn ครั้งถัดไปจึงยื่นช่อง 0 ให้ c ทันที — memory เดียวกัน จองศูนย์ครั้ง พอทั้งสามช่องถูกใช้หมด pool คืน -1 แทนที่จะโต งบตายตัวมักเป็นสิ่งที่คุณต้องการในเกม: คุณอยากจำกัดจำนวนกระสุนมากกว่าปล่อยให้เฟรมที่ยุ่ง ๆ เฟรมเดียวจอง memory ไม่จำกัด

เพราะ object อยู่ใน std::vector ก้อนเดียวแบบ contiguous การกวาดไล่ตัวที่ยังมีชีวิตทุกเฟรมก็เป็นมิตรกับ cache ด้วย — pool ซื้อทั้ง "ไม่จอง memory ต่อเฟรม" และ "layout ที่ดีใน memory" มาให้ในหมัดเดียว แพตเทิร์นนี้อยู่ทุกที่ในเกม: กระสุน, particle, ศัตรู, audio voice, network packet, ตัวเลขดาเมจที่เด้งขึ้นมา อะไรก็ตามที่ถูก spawn และทำลายอย่างรวดเร็วแทบจะควรมาจาก pool เสมอ

18. Spatial partitioning: "มีอะไรอยู่ใกล้ฉันบ้าง?"

คำถามที่เกมถามทุก ๆ เฟรม: object ไหนอยู่ใกล้ตัวนี้บ้าง? การชน, รัศมีระเบิด, "ศัตรูที่มองเห็นผู้เล่น", เก็บของที่อยู่ใกล้ คำตอบไร้เดียงสาคือเทียบ object ทุกตัวกับทุกตัว — นั่นคือลูปคู่ O(n^2) จากหัวข้อ 1 และมันพังเร็ว: 1,000 object คือการเช็คครึ่งล้านครั้ง ต่อเฟรม; 10,000 object คือห้าสิบล้านครั้ง

ทางแก้คือ spatial structure: สับโลกเป็นช่อง (cell) หย่อนแต่ละ object ลงในช่องที่มันอยู่ แล้วเทียบเฉพาะ object ที่อยู่ช่องเดียวกัน (หรือติดช่องข้าง ๆ) object ที่อยู่ไกลกันจะไม่ถูกเทียบเลย เวอร์ชันที่ง่ายที่สุดคือ uniform grid: ช่องขนาดตายตัว เก็บเป็น hash map จากพิกัดช่องไปยัง list ของ object ในช่องนั้น

ด้านล่างเราโปรย 1,000 จุดแล้วนับจำนวนคู่ที่อยู่ในรัศมี R ครั้งหนึ่งแบบไร้เดียงสาและอีกครั้งด้วย grid เพื่อให้คุณเห็นว่ามันหาคู่ ชุดเดียวกัน ได้ด้วยปริมาณงานที่ต่างกันลิบลับ

#include <vector>
#include <unordered_map>
#include <cstdio>

struct V2 { float x, y; };

int main(){
    std::vector<V2> pts;
    for(int i=0;i<1000;i++)
        pts.push_back({ (float)((i*37)%100), (float)((i*53)%100) });

    const float R=5.0f;

    // --- naive: test every pair, O(n^2) ---
    long long naiveChecks=0, naivePairs=0;
    for(size_t i=0;i<pts.size();i++)
        for(size_t j=i+1;j<pts.size();j++){
            naiveChecks++;
            float dx=pts[i].x-pts[j].x, dy=pts[i].y-pts[j].y;
            if(dx*dx+dy*dy<=R*R) naivePairs++;
        }

    // --- uniform grid: bucket by cell of size R, only check the 3x3 block ---
    const int cell=(int)R;
    auto key=[&](int cx,int cy){ return (long long)cx*100000+cy; };
    std::unordered_map<long long,std::vector<int>> grid;
    for(int i=0;i<(int)pts.size();i++)
        grid[key((int)(pts[i].x/cell),(int)(pts[i].y/cell))].push_back(i);

    long long gridChecks=0, gridPairs=0;
    for(int i=0;i<(int)pts.size();i++){
        int cx=(int)(pts[i].x/cell), cy=(int)(pts[i].y/cell);
        for(int ox=-1;ox<=1;ox++) for(int oy=-1;oy<=1;oy++){
            auto it=grid.find(key(cx+ox,cy+oy));
            if(it==grid.end()) continue;
            for(int j:it->second){
                if(j<=i) continue;              // count each pair once
                gridChecks++;
                float dx=pts[i].x-pts[j].x, dy=pts[i].y-pts[j].y;
                if(dx*dx+dy*dy<=R*R) gridPairs++;
            }
        }
    }

    printf("naive: %8lld distance checks, found %lld pairs\n", naiveChecks, naivePairs);
    printf("grid : %8lld distance checks, found %lld pairs\n", gridChecks, gridPairs);
    printf("grid did %.1fx fewer checks for the same answer\n",
           (double)naiveChecks/gridChecks);
}

Output:

naive:   499500 distance checks, found 4500 pairs
grid :    10000 distance checks, found 4500 pairs
grid did 50.0x fewer checks for the same answer

ทั้งคู่หาคู่ได้ 4,500 คู่เท่ากัน — grid ไม่ใช่การประมาณ มันแม่นยำ แต่ลูปไร้เดียงสาทำการเช็คระยะ 499,500 ครั้ง (ทุกคู่จาก 1,000 จุด) ขณะที่ grid ทำแค่ 10,000 ครั้ง เพราะแต่ละจุดมองแค่ไม่กี่ตัวที่อยู่ในย่าน 3x3 ของมัน ช่องว่าง 50 เท่านั้นยิ่งกว้างขึ้นเมื่อโลกใหญ่ขึ้น: วิธีไร้เดียงสายังเป็น O(n^2) ส่วน grid เป็นราว ๆ O(n) เมื่อ object กระจายตัวสม่ำเสมอ

เมื่อ grid ไม่พอ: quadtree

uniform grid สมบูรณ์แบบเมื่อ object กระจายสม่ำเสมอและคุณเลือกขนาดช่องที่ดีได้ตัวเดียว มันมีปัญหาเมื่อ object กระจุกตัว — หน่วยพันตัวอัดกันในเมืองเดียว ที่เหลือเป็นป่ารกร้างว่างเปล่า — เพราะช่องที่แออัดจะเต็ม (ดริฟต์กลับไปทาง O(n^2) ภายในช่องเดียว) ขณะที่ช่องว่างเปล่านับล้านสิ้นเปลือง memory ทางแก้คือโครงสร้างที่ ปรับตัว ตามความหนาแน่น: quadtree

ญาติ 3 มิติของมันคือ octree (แบ่งลูกบาศก์เป็น 8) และ BVH (bounding-volume hierarchy) ซึ่งเป็นตัวที่ ray tracer และ physics engine ใช้ตอบคำถาม "ray นี้ หรือ body ที่กำลังเคลื่อนนี้ อาจชนอะไรได้บ้าง?" โดยไม่ต้องเทียบทุกอย่าง คุณไม่ต้องเขียนมันวันนี้ แนวคิดที่ควรพกติดตัวไปคือแนวคิดที่บทนี้วนกลับมาย้ำตลอด: อย่าจ่ายค่างาน O(n^2) เมื่อโครงสร้างช่วยโยนทิ้งการเปรียบเทียบที่ยังไงก็ไม่มีความหมายได้

19. Glossary

• Big-O — งานของ algorithm โตขึ้นแค่ไหนเมื่อขนาด input n โตขึ้น; ไม่สนใจ constant factor
• O(1) / O(log n) / O(n) / O(n log n) / O(n^2) — การโตแบบ constant / logarithmic / linear / linearithmic / quadratic เรียงจากเร็วสุดไปช้าสุด
• Cache locality — ข้อมูลที่อยู่ใกล้กันใน memory อ่านได้เร็ว เพราะ CPU โหลดทั้ง cache line เข้ามาทีเดียว
• Cache miss — CPU ต้องการ memory ที่ยังไม่ได้โหลด จึงต้องหยุดรอ RAM
• Contiguous — เก็บติดกันในก้อนเดียว (vector) ตรงข้ามกับ node ที่กระจัดกระจาย (list)
• Amortized O(1) — เฉลี่ยแล้วถูกเมื่อคิดข้ามหลาย operation แม้บาง operation จะแพงเป็นครั้งคราว (push_back ของ vector)
• Geometric growth — เพิ่มความจุแบบทวีคูณ (เป็นสองเท่า) ซึ่งทำให้ push_back เป็น amortized O(1)
• Hash function — แปลง key เป็นเลขที่ใช้เลือก bucket
• Collision — key สองตัวตกลงใน bucket เดียวกัน
• Load factor — จำนวนรายการหารด้วยจำนวน bucket; สูงเกินไปจะกระตุ้น rehash
• Stack / queue — ลำดับแบบ LIFO (เข้าทีหลังออกก่อน) / FIFO (เข้าก่อนออกก่อน)
• Binary heap / priority queue — tree ใน array ที่ยื่นตัวเล็กสุด (หรือใหญ่สุด) ให้คุณแบบ O(log n)
• Graph, node, edge, adjacency list — ข้อมูลเป็นจุดที่เชื่อมกัน; adjacency list เก็บเพื่อนบ้านของแต่ละ node
• BFS — breadth-first search; หาจำนวนก้าวน้อยที่สุดใน graph แบบ unweighted ด้วย queue
• Dijkstra / A* — เส้นทางสั้นสุดที่มี edge weight; A* คือ Dijkstra ที่นำทางด้วย heuristic (การเดาระยะที่เหลือ) ผ่าน priority queue
• Heuristic — การประเมินแบบราคาถูก; ใน A* คือต้นทุนที่เดาไว้จาก node ไปถึงเป้าหมาย
• Memoization / dynamic programming — เก็บคำตอบของ subproblem ที่ซ้ำ ๆ ไว้ เพื่อคำนวณแต่ละอันครั้งเดียว
• Data-oriented design — จัดข้อมูลเป็น array แบน ๆ แบบ contiguous เพื่อประมวลผลเร็วและเป็นมิตรกับ cache
• std::chrono — library จับเวลามาตรฐาน; อ่านนาฬิกาก่อนและหลังงานเพื่อวัดเวลาที่ผ่านไปเป็นมิลลิวินาที
• Debug vs release build — -O0 (ไม่ optimize) เทียบกับ -O2; มีแต่ optimized release build ที่สะท้อนความเร็วตอนปล่อยจริง จง profile ตัวนั้น
• std::deque — double-ended queue; push/pop เป็น O(1) ทั้งด้านหน้าและด้านหลัง; เป็นฐานของ std::queue
• std::map (ordered map) — balanced binary search tree (red-black tree); key เรียงลำดับเสมอ; insert/find เป็น O(log n); รองรับ range query
• std::unordered_map (hash map) — map แบบ hash table; insert/find เฉลี่ย O(1); ไม่มีลำดับ
• Rehash — hash map เพิ่มจำนวน bucket (ไปเลขเฉพาะถัดไป) และจัดวางทุกรายการใหม่เมื่อ load factor เกินขีด
• Separate chaining / open addressing — สองวิธีจัดการ collision: linked list ต่อ bucket (standard library) เทียบกับการเขยิบไปช่องว่างถัดไปใน array แบนก้อนเดียว (map เกมที่เร็ว ๆ)
• Introsort — สิ่งที่ std::sort เป็น: quicksort ที่ถอยไป heapsort เมื่อ recursion ลึก และ insertion sort กับชิ้นเล็ก ๆ
• Stable sort — การเรียงที่คงลำดับสัมพัทธ์เดิมของสมาชิกที่เท่ากัน; std::stable_sort รับประกัน ส่วน std::sort ไม่
• Object pool / free list — ก้อน object ขนาดตายตัวที่จองครั้งเดียวแล้วใช้ซ้ำผ่าน list ของ index ว่าง เพื่อเลี่ยงการจอง memory ต่อเฟรม
• Uniform grid — spatial structure ที่หย่อน object ลงช่องขนาดตายตัวเพื่อให้เทียบเฉพาะ object ที่อยู่ใกล้กัน; ราว ๆ O(n) เมื่อ object กระจายสม่ำเสมอ
• Quadtree / octree / BVH — spatial structure ที่ปรับตามความหนาแน่นด้วยการซอยย่อยบริเวณที่แออัด; ใช้กับการชน, culling, และ query การชน/ray

20. แบบฝึกหัด

int a(const std::vector<int>& v) {
    return v.empty() ? 0 : v[v.size() - 1];   // (A)
}

int b(const std::vector<int>& v) {           // (B)
    int best = 0;
    for (int i = 0; i < (int)v.size(); i++)
        for (int j = i + 1; j < (int)v.size(); j++)
            if (v[i] + v[j] > best) best = v[i] + v[j];
    return best;
}

grew to cap 1
grew to cap 2
grew to cap 4
grew to cap 8
grew to cap 16

นี่คือกล่องเครื่องมือ ตอนนี้คุณรู้วิธีคิดเรื่อง ต้นทุน ของโค้ด (Big-O), รู้ว่าโครงสร้างที่พบบ่อยวางตัวใน memory ยังไงและทำไม cache เป็นตัวตัดสินระหว่างตัวเลือกที่ Big-O เท่ากัน, และรู้ algorithm หลัก ๆ — hashing, heap, BFS, Dijkstra/A*, sorting, และ DP — ที่เกมพึ่งพาทุกเฟรม ธีมที่วนกลับมาเรื่อย ๆ และคุ้มที่จะพกติดตัวไปทุกบทถัดไปคือ: เลือก Big-O ที่สมเหตุสมผล, เก็บข้อมูลให้ contiguous, และวัดผลก่อนจะเชื่อคำกล่าวอ้างเรื่องความเร็วใด ๆ