16.2 vector สองมิติและความเร็ว

ตารางในบทที่ 7 ต้องจองขนาดสูงสุดไว้ก่อน เช่น int grid[1000][1000]; ถ้าโจทย์บอกแค่ว่าจำนวนช่องทั้งหมดไม่เกินล้าน ตารางอาจเป็น 1 × 1000000 หรือ 1000000 × 1 ก็ได้ อาเรย์สองมิติที่รับได้ทั้งสองแบบใหญ่เกินจะจองไหว หน้านี้สร้างตารางจาก vector ที่ขนาดมาจากข้อมูลเข้า ส่ง vector ให้ฟังก์ชันโดยไม่คัดลอกทิ้งเปล่าๆ แล้ววัดดูว่า push_back ช้ากว่าอาเรย์จริงไหม

ตารางที่ขนาดมาจากข้อมูลเข้า

vector สองมิติคือ vector ที่แต่ละช่องเป็น vector อีกตัว ชนิดจึงเขียนซ้อนกันเป็น vector<vector<int>> ตัวอย่างนี้รับคะแนนของนักเรียน R คน คนละ C วิชา แล้วพิมพ์คะแนนรวมของแต่ละคน

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int students, subjects;
    cin >> students >> subjects;
    vector<vector<int>> score(students, vector<int>(subjects)); // (1)!
    for (int i = 0; i < students; i++) {
        for (int j = 0; j < subjects; j++) {
            cin >> score[i][j]; // (2)!
        }
    }
    for (int i = 0; i < students; i++) {
        int total = 0;
        for (int x : score[i]) { // (3)!
            total += x;
        }
        cout << "student " << i + 1 << ": " << total << '\n';
    }
    return 0;
}

1. สร้าง students แถว แต่ละแถวคือ vector<int>(subjects) ซึ่งมี subjects ช่องที่เป็น 0 อ่านแบบเดียวกับ vector<int> a(n, x) ในหน้า 16.1 คือ n ช่อง แต่ละช่องเป็น x เพียงแต่ x คือแถวทั้งแถว
2. ใช้ [i][j] แถวก่อนคอลัมน์ เหมือนอาเรย์สองมิติในบทที่ 7
3. score[i] คือแถวที่ i ซึ่งเป็น vector<int> หนึ่งตัว จึงวนด้วย range-for ได้ ส่วนจำนวนแถวคือ score.size() และจำนวนช่องในแถวที่ i คือ score[i].size()

3 4
72 85 64 90
58 77 81 69
95 88 92 99

student 1: 311
student 2: 285
student 3: 374

แต่ละแถวยาวไม่เท่ากัน

แต่ละแถวเป็น vector ของตัวเอง จึงยาวไม่เท่ากันได้ และยืดทีละแถวด้วย push_back ได้ ซึ่งอาเรย์สองมิติทำไม่ได้ โรงเรียนมีชุมนุม K ชุมนุม นักเรียน N คน แต่ละคนเลือกหนึ่งชุมนุม ให้พิมพ์รายชื่อเลขที่ของสมาชิกแต่ละชุมนุม

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int k, n;
    cin >> k >> n;
    vector<vector<int>> members(k + 1);
    for (int student = 1; student <= n; student++) {
        int club;
        cin >> club;
        members[club].push_back(student);
    }
    for (int c = 1; c <= k; c++) {
        cout << "club " << c << " (" << members[c].size() << "):";
        for (int student : members[c]) {
            cout << ' ' << student;
        }
        cout << '\n';
    }
    return 0;
}

3 7
2 1 2 2 1 2 2

club 1 (2): 2 5
club 2 (5): 1 3 4 6 7
club 3 (0):

บรรทัดที่ 8 สร้าง K + 1 แถวที่ยังว่างทุกแถว บรรทัดที่ 12 ต่อท้ายเฉพาะแถวของชุมนุมที่นักเรียนเลือก ถ้าใช้อาเรย์สองมิติ ต้องจองทุกแถวยาวเท่ากับ N เผื่อทุกคนเลือกชุมนุมเดียวกัน ทั้งที่รวมแล้วมีสมาชิกแค่ N คน รูปแบบนี้จะได้ใช้อีกมากในบทที่ 27 ตอนเก็บว่าจุดไหนในกราฟเชื่อมกับจุดไหนบ้าง

ส่ง vector ให้ฟังก์ชัน

ในหน้า 8.3 อาเรย์ที่ส่งให้ฟังก์ชันไม่รู้ขนาดของตัวเอง ต้องส่งจำนวนช่องไปด้วยเสมอ vector พกขนาดไปด้วย และฟังก์ชันคืน vector กลับมาได้ด้วย สิ่งที่ต้องเลือกคือจะส่งแบบไหน

#include <bits/stdc++.h>
using namespace std;

long long total(const vector<int> &score)
{
    long long sum = 0;
    for (int s : score) {
        sum += s;
    }
    return sum;
}

void add_bonus(vector<int> &score, int bonus)
{
    for (int &s : score) {
        s = min(100, s + bonus);
    }
}

vector<int> passed(const vector<int> &score, int limit)
{
    vector<int> result;
    for (int s : score) {
        if (s >= limit) {
            result.push_back(s);
        }
    }
    return result;
}

int main()
{
    vector<int> score = {72, 45, 98, 49, 60};
    cout << "total = " << total(score) << '\n';
    add_bonus(score, 5);
    cout << "total = " << total(score) << '\n';
    vector<int> ok = passed(score, 60);
    cout << "passed = " << ok.size() << '\n';
    return 0;
}

total = 324
total = 346
passed = 3

add_bonus รับแบบ reference ที่แก้ได้ จึงบวกคะแนนเข้าไปใน score ของ main จริงๆ ส่วน min คืนค่าที่น้อยกว่าของสองค่า มีให้ใช้ใน C++ เลย ใช้กันคะแนนไม่ให้เกิน 100 คะแนน 98 จึงกลายเป็น 100 ไม่ใช่ 103 ผลรวมเลยเพิ่มขึ้น 22 ไม่ใช่ 25 ส่วน passed สร้าง vector ใหม่เก็บคะแนนที่ถึง 60 แล้วคืนกลับไปทั้งก้อน ภาษา C ทำแบบนี้กับอาเรย์ไม่ได้

เลือกใช้ vector หรืออาเรย์

อาเรย์ไม่ได้ผิด ถ้าขอบเขตชัดและไม่ใหญ่ เช่น ตารางไม่เกิน 100 × 100 หรืออาเรย์นับคะแนน 0 ถึง 100 อาเรย์ global แบบบทที่ 5 ยังใช้ได้ดี และคนแข่งจำนวนมากก็ยังเขียนแบบนั้น เอกสารนี้ตั้งแต่บทนี้ไปใช้ vector เป็นหลัก

push_back เร็วแค่ไหน

vector ต้องคอยยืดตัวเอง จึงน่าสงสัยว่าช้ากว่าอาเรย์ไหม วัดด้วย clock() แบบหน้า 4.5 เติมเลข 0 ถึง n - 1 ลงไปทีละตัว แล้วพิมพ์เวลาเป็นวินาที ทศนิยม 3 ตำแหน่ง ที่ต้องพิมพ์ช่องสุดท้ายด้วยก็เพื่อยืนยันว่าเติมครบจริง

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    clock_t start = clock();
    vector<int> v; // (1)!
    for (int i = 0; i < n; i++) {
        v.push_back(i); // (2)!
    }
    clock_t end = clock();
    cout << fixed << setprecision(3);
    cout << "n = " << n << ", last = " << v[n - 1] << ", time = " << (double)(end - start) / CLOCKS_PER_SEC << " seconds\n"; // (3)!
    return 0;
}

1. แบบ vector(n) เปลี่ยนเป็น vector<int> v(n); แบบ reserve เพิ่มบรรทัด v.reserve(n); ต่อจากบรรทัดนี้ ส่วนแบบอาเรย์ลบบรรทัดนี้ แล้วประกาศ int a[10000000]; ไว้นอก main
2. แบบ vector(n) เปลี่ยนเป็น v[i] = i; แบบอาเรย์เปลี่ยนเป็น a[i] = i; และบรรทัดที่ 15 พิมพ์ a[n - 1] แทน
3. clock() นับเป็นหน่วยย่อย CLOCKS_PER_SEC หน่วยต่อวินาที แปลงเป็น double ก่อนหารจึงได้วินาทีเป็นทศนิยม แล้วพิมพ์ 3 ตำแหน่งด้วย fixed กับ setprecision(3) จากหน้า 15.2

10000000

n = 10000000, last = 9999999, time = 0.076 seconds

วัดบนเครื่องเดียวกับหน้า 13.3 คือโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 Windows 11 เสียบสายชาร์จ โหมดพลังงาน Balanced คอมไพล์ด้วย g++ 14.2 ของ Code::Blocks ทั้งแบบ Code::Blocks (-Wall อย่างเดียว) และแบบ -O2 รันแต่ละช่อง 12 ครั้ง ทิ้งครั้งแรก ตารางเป็นค่ากลางของ 11 ครั้งที่เหลือ หน่วยเป็นวินาที ระหว่างวัดเครื่องมีงานอื่นรันอยู่ด้วย ตัวเลขของแต่ละรอบจึงแกว่งได้ราวหนึ่งในสาม

0.000 แปลว่าน้อยกว่าที่ clock() วัดได้ อ่านตารางได้สามเรื่อง

1. ทุกวิธีเร็วพอ สิบล้านตัว ช้าที่สุดก็ไม่ถึงหนึ่งในสิบวินาที โจทย์ส่วนใหญ่มีข้อมูลไม่เกินล้านตัว push_back ไม่ใช่ตัวที่ทำให้เกินเวลา
2. แบบ Code::Blocks push_back ช้ากว่าอาเรย์ราว 3 เท่า (0.076 กับ 0.026 วินาทีที่สิบล้านตัว) เพราะไม่ได้เปิด -O2 ทุก push_back จึงเป็นการเรียกฟังก์ชันจริงๆ พอเปิด -O2 ซึ่ง grader ใช้ ส่วนต่างเหลือแค่ไม่กี่มิลลิวินาที
3. reserve ช่วยได้นิดหน่อย แบบ -O2 จาก 0.016 เหลือ 0.006 วินาที ใช้เมื่อรู้จำนวนล่วงหน้าแต่อยากใช้ push_back

ทำไม push_back ไม่ช้า

เบื้องหลัง vector จองที่ไว้เกินจำนวนที่ใช้เสมอ จำนวนที่จองไว้ดูได้จาก capacity() ถ้า push_back แล้วที่เต็ม vector จะจองที่ใหม่ที่ใหญ่ขึ้น ย้ายข้อมูลเดิมไปทั้งหมด แล้วคืนที่เก่า ลองพิมพ์ดูทุกครั้งที่ capacity() เปลี่ยน

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> v;
    int last_capacity = 0;
    for (int i = 0; i < 100; i++) {
        v.push_back(i);
        if ((int)v.capacity() != last_capacity) {
            last_capacity = v.capacity();
            cout << "size " << v.size() << ", capacity " << v.capacity() << '\n';
        }
    }
    return 0;
}

size 1, capacity 1
size 2, capacity 2
size 3, capacity 4
size 5, capacity 8
size 9, capacity 16
size 17, capacity 32
size 33, capacity 64
size 65, capacity 128

g++ ขยายทีละเท่าตัว การย้ายข้อมูลจึงเกิดนานๆ ครั้ง และยิ่งนานขึ้นเรื่อยๆ เติม 100 ตัวย้ายแค่ 7 ครั้ง ถ้านับจำนวนค่าที่ถูกย้ายทั้งหมด จะได้ 1 + 2 + 4 + ... + 64 = 127 ค่า ไม่ถึงสองเท่าของจำนวนที่เติม ไม่ว่าจะเติมกี่ตัว ผลรวมแบบนี้จะน้อยกว่าสองเท่าของจำนวนที่เติมเสมอ โดยเฉลี่ย push_back หนึ่งครั้งจึงทำงานเพิ่มแค่ไม่กี่ขั้น compiler อื่นอาจขยายด้วยอัตราอื่น แต่ใช้หลักเดียวกัน

v.reserve(n) คือสั่งให้จองที่ n ช่องไว้ก่อนเลย size() ยังเป็น 0 เหมือนเดิม แต่ push_back n ครั้งต่อจากนั้นไม่ต้องย้ายข้อมูลอีก ต่างจาก vector<int> v(n) ที่สร้าง n ช่องจริงๆ ซึ่งถ้าตามด้วย push_back จะได้ 2n ช่องแบบในหน้า 16.1

ลองทำให้พัง

แบบที่ 1 สร้างแถวแต่ลืมขนาดของแถว

ในโปรแกรม grid ถ้าเขียนบรรทัดที่ 8 สั้นลงเป็น

vector<vector<int>> score(students);

คอมไพล์ผ่านไม่มีคำเตือน แต่พอป้อนข้อมูลชุดเดิม โปรแกรมปิดตัวทันที

Process returned -1073741819 (0xC0000005)

มี students แถวจริง แต่ทุกแถวเป็น vector ว่าง score[i][j] จึงเป็นการใช้ [] กับ vector ว่างแบบในหน้า 16.1 ตารางที่ทุกแถวยาวเท่ากันต้องบอกขนาดทั้งสองชั้น score(students, vector<int>(subjects)) ส่วนตารางที่แถวยาวไม่เท่ากันแบบ clubs ต้องเติมแต่ละแถวด้วย push_back เท่านั้น

แบบที่ 2 ส่ง vector ให้ฟังก์ชันโดยไม่ใส่ &

โปรแกรมนี้รวมค่าของช่องข้างเคียงทั้งสี่ทิศของทุกช่องในตาราง n × n แบบหน้า 7.4 โดยมีฟังก์ชัน cell คืนค่าในช่อง หรือคืน 0 ถ้าช่องนั้นอยู่นอกตาราง ทุกช่องในตารางเป็น 1

#include <bits/stdc++.h>
using namespace std;

int cell(vector<vector<int>> grid, int r, int c)
{
    if (r < 0 || r >= (int)grid.size() || c < 0 || c >= (int)grid[0].size()) {
        return 0;
    }
    return grid[r][c];
}

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> grid(n, vector<int>(n, 1));
    clock_t start = clock();
    long long total = 0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            total += cell(grid, r - 1, c) + cell(grid, r + 1, c) + cell(grid, r, c - 1) + cell(grid, r, c + 1);
        }
    }
    clock_t end = clock();
    cout << fixed << setprecision(3);
    cout << "total = " << total << ", time = " << (double)(end - start) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}

200

total = 159200, time = 5.088 seconds

ตารางแค่ 200 × 200 ใช้เวลาห้าวินาที ทั้งที่งานจริงคือเรียก cell 160,000 ครั้ง ซึ่งแต่ละครั้งทำแค่ if เดียว เพราะหัวฟังก์ชันรับ grid แบบสำเนา ทุกครั้งที่เรียก cell โปรแกรมจึงสร้างตารางใหม่ 200 แถว แล้วคัดลอก 40,000 ค่ามาใส่ เพื่อหยิบไปใช้แค่ค่าเดียว รวมแล้วคัดลอกถึง 6.4 พันล้านค่า แก้แค่หัวฟังก์ชันให้เป็น reference

int cell(const vector<vector<int>> &grid, int r, int c)

วัดบนเครื่องเดียวกับตารางข้างบน รันแต่ละช่อง 6 ครั้ง ทิ้งครั้งแรก ตารางเป็นค่ากลางของ 5 ครั้งที่เหลือ หน่วยเป็นวินาที

ต่างกันหลายพันเท่าจากตัวอักษรตัวเดียว และ -O2 ช่วยไม่ได้ เพราะ compiler ต้องคัดลอกตามที่เราสั่ง ยิ่งตารางใหญ่ยิ่งแย่ n เพิ่มสองเท่า เวลาแบบสำเนาเพิ่มราว 7 ถึง 10 เท่า compiler ไม่เตือนเรื่องนี้เลย หน้า 15.5 เห็นแล้วว่า string แบบสำเนาช้ากว่าราวสิบเท่า กับตารางสองมิติผลแย่กว่านั้นมาก ให้ตั้งเป็นนิสัยว่า vector string และ struct ที่ส่งให้ฟังก์ชันต้องมี & เสมอ ถ้าไม่แก้ใส่ const ด้วย

สรุป

• ตารางขนาด R × C สร้างด้วย vector<vector<int>> g(R, vector<int>(C)); ต้องบอกขนาดทั้งสองชั้น
• ตารางที่แถวยาวไม่เท่ากัน สร้างแค่จำนวนแถว แล้ว push_back ลงแต่ละแถว
• ส่ง vector ให้ฟังก์ชันด้วย const vector<int> & ถ้าแค่อ่าน vector<int> & ถ้าต้องแก้ ลืม & แล้วอาจช้าเป็นพันเท่า
• ฟังก์ชันคืน vector ทั้งก้อนได้
• push_back สิบล้านครั้งใช้ไม่ถึงหนึ่งในสิบวินาที เพราะ vector ขยายทีละเท่าตัว reserve(n) จองที่ไว้ก่อนได้