18.4 STL และหน่วยความจำ

คำสั่งของ STL และ string ที่เรียนในบทที่ 15 ถึง 17 เขียนบรรทัดเดียวก็จริง แต่บางคำสั่งมีลูปซ่อนอยู่ข้างใน ถ้าไม่รู้ว่าคำสั่งไหนใช้เวลาเท่าไร โปรแกรมที่ดูเป็น O(N) อาจกลายเป็น O(N²) โดยไม่รู้ตัว ครึ่งหลังของหน้าดูอีกลิมิตหนึ่งที่ทุกโจทย์มี คือหน่วยความจำ ซึ่งส่วนใหญ่ให้ 256 MB

vector

ทำไม push_back เป็น O(1) โดยเฉลี่ย

หน้า 16.2 เห็นแล้วว่า vector ขยายทีละเท่าตัว และนับไว้แล้วว่า push_back N ครั้งย้ายของรวมกันไม่ถึง 2N ตัว การย้ายแต่ละครั้งเป็น O(N) แต่เกิดนานๆ ครั้ง เฉลี่ยแล้วครั้งละไม่ถึง 2 ตัว จึงเรียกว่า O(1) โดยเฉลี่ย บนเครื่องที่เขียนเอกสารนี้แบบ -O2 push_back 10⁷ ตัวใช้ 0.017 วินาที และ 10⁸ ตัวใช้ 0.145 วินาที (ค่ากลาง 5 ครั้ง วิธีวัดเหมือนหน้า 18.2)

กับดัก erase หัว vector

ร้านขนมมีลูกค้าต่อคิว N คน ขายให้คนหัวคิวทีละคน ถ้าเก็บคิวใน vector แล้วลบคนหัวคิวด้วย erase โค้ดสั้นและถูก

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

int main()
{
    int n;
    cin >> n;
    vector<int> line;
    for (int i = 0; i < n; i++) {
        line.push_back(i);
    }
    clock_t start = clock();
    long long served = 0;
    while (!line.empty()) {
        served += line.front();
        line.erase(line.begin());
    }
    clock_t end = clock();
    cout << "served = " << served << '\n';
    cout << "time = " << fixed << setprecision(3) << (double)(end - start) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}

แต่ erase(line.begin()) ต้องเลื่อนทุกคนที่เหลือขึ้นมาหนึ่งช่อง แบบที่เห็นในหน้า 5.5 ครั้งแรกเลื่อน N − 1 ตัว ครั้งต่อไป N − 2 ตัว รวมเป็น N(N − 1) / 2 คือ O(N²) ทั้งที่ลูปมีชั้นเดียว เป็นปัญหาเดียวกับการแทรกที่หัว vector ในหน้า 17.2 แต่อยู่ฝั่งลบ เทียบกับอีกสองวิธีที่ไม่ต้องเลื่อนใคร

• ใช้ queue<int> จากบทที่ 17 เปลี่ยน push_back เป็น push และ erase(line.begin()) เป็น pop()
• เก็บใน vector เหมือนเดิม แต่ไม่ลบจริง ใช้ตัวแปร head จำว่าหัวคิวอยู่ช่องไหน ขายแล้วก็ head++

วัดบนเครื่องเดียวกับหน้า 18.2 คือโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 Windows 11 คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks แบบ -O2 รันแต่ละช่อง 6 ครั้ง ทิ้งครั้งแรก ใช้ค่ากลางของ 5 ครั้งที่เหลือ ยกเว้นช่อง vector ที่ N เป็นล้านซึ่งรัน 3 ครั้ง ตารางอื่นในหน้านี้วัดแบบเดียวกัน

N สองแสนยังพอทน แต่ล้านคนใช้เวลากว่าหนึ่งนาที ถ้าต้องลบหัวแถวบ่อยๆ ให้ใช้ queue หรือ deque ซึ่งออกแบบมาให้ทำที่หัวแถวได้ใน O(1)

stack queue deque

stack กับ queue ไม่มีคำสั่งลบตรงกลางเลย ส่วน deque มี insert กับ erase ตรงกลางให้ใช้ แต่ต้องเลื่อนของที่อยู่ระหว่างตำแหน่งนั้นกับหัวหรือท้ายเหมือน vector จึงเป็น O(N) และทั้งสามแบบไม่มีคำสั่งค้นหา ถ้าต้องหาว่ามีค่า x อยู่ไหม ก็ต้องไล่ทีละตัวเองเป็น O(N) โจทย์ที่ต้องค้นบ่อยๆ ใช้ set กับ map ในบทที่ 20

string ต่อท้าย

string ทำงานเหมือน vector ของ char s += c และ s.push_back(c) ต่อท้ายตัวเดิมได้ใน O(1) โดยเฉลี่ย แต่ s = s + c ต่างกัน s + c สร้างสตริงใหม่ทั้งก้อนก่อน คัดลอกทุกตัวของ s ไปไว้ แล้วค่อยเอามาแทน s เดิม ทุกรอบจึงเป็น O(ความยาวของ s)

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

int main()
{
    int n;
    cin >> n;
    clock_t start = clock();
    string s;
    for (int i = 0; i < n; i++) {
        s = s + (char)('a' + i % 26);
    }
    clock_t end = clock();
    cout << "length = " << s.size() << '\n';
    cout << "time = " << fixed << setprecision(3) << (double)(end - start) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}

เทียบกับแก้บรรทัดที่ 11 เป็น s += (char)('a' + i % 26);

คำสั่งอื่นของ string ที่ต้องรู้เวลา s.size() เป็น O(1) ไม่ต้องนับใหม่ทุกครั้งแบบ strlen ในหน้า 6.4 ส่วน s.substr(i, k) คัดลอก k ตัวจึงเป็น O(k) และการต่อไว้ข้างหน้าอย่าง s = c + s เป็น O(ความยาวของ s) ทุกครั้งเหมือนกัน

หน่วยความจำ

โจทย์ส่วนใหญ่จำกัดหน่วยความจำไว้ 256 MB โปรแกรมที่ใช้เกินจะถูกหยุดแม้คำตอบถูก ขนาดของข้อมูลแต่ละชนิดดูได้ด้วย sizeof

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

int main()
{
    cout << "char " << (int)sizeof(char) << '\n';
    cout << "bool " << (int)sizeof(bool) << '\n';
    cout << "int " << (int)sizeof(int) << '\n';
    cout << "long long " << (int)sizeof(long long) << '\n';
    cout << "double " << (int)sizeof(double) << '\n';
    cout << "pair<int, int> " << (int)sizeof(pair<int, int>) << '\n';
    return 0;
}

char 1
bool 1
int 4
long long 8
double 8
pair<int, int> 8

หน่วยความจำของอาเรย์คือจำนวนช่องคูณขนาดของหนึ่งช่องเป็น byte แล้วหารด้วย 10⁶ ได้เป็น MB 1 MB จริงๆ คือ 1,048,576 byte การหารด้วยล้านจึงได้ตัวเลขที่เกินจริงเล็กน้อย ซึ่งปลอดภัยไว้ก่อน vector ก็คิดแบบเดียวกัน

ต้องรวมทุกอาเรย์ในโปรแกรม ไม่ใช่ดูทีละตัว และยังมีอีกลิมิตที่เจอในหน้า 5.5 คือตัวแปรที่ประกาศใน main ใช้ได้รวมราว 2 MB บนเครื่องน้อง อาเรย์ใหญ่จึงต้องประกาศนอก main ส่วน vector เก็บของไว้นอกพื้นที่ 2 MB นั้น บนเครื่องที่เขียนเอกสารนี้ vector<int> a(10000000) ใน main รันได้ปกติ แถว N = 10⁸ ในตารางหน้า 18.2 ใช้ vector ขนาด 400 MB จึงวัดเวลาบนเครื่องเราได้ แต่ส่งให้ grader ที่จำกัด 256 MB ไม่ได้

ลองทำให้พัง

ส่ง vector ให้ฟังก์ชันโดยลืม &

ฟังก์ชันที่รับ vector แบบธรรมดา จะได้สำเนาของทั้ง vector ทุกครั้งที่ถูกเรียก ตามหลักส่งค่าแบบสำเนาในหน้า 8.2 ถ้าเรียกฟังก์ชันนั้นในลูป N รอบ งานคือ N × N

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

long long count_above(vector<int> scores, int pos)
{
    return scores[pos] > 50 ? 1 : 0;
}

int main()
{
    int n;
    cin >> n;
    vector<int> scores(n);
    for (int i = 0; i < n; i++) {
        scores[i] = i % 101;
    }
    clock_t start = clock();
    long long above = 0;
    for (int i = 0; i < n; i++) {
        above += count_above(scores, i);
    }
    clock_t end = clock();
    cout << "above = " << above << '\n';
    cout << "time = " << fixed << setprecision(3) << (double)(end - start) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}

แก้บรรทัดที่ 4 เป็น long long count_above(const vector<int> &scores, int pos) ให้รับแบบ reference จากหน้า 15.5 ซึ่งไม่คัดลอกอะไรเลย ส่วน const บอกว่าฟังก์ชันจะไม่แก้ vector นั้น

ไม่มี error ไม่มี warning ผลลัพธ์ถูกทุกตัว ต่างกันแค่เครื่องหมาย & ตัวเดียว ถ้าฟังก์ชันรับ vector string หรือ struct ใหญ่ๆ ให้ใส่ & ไว้ก่อนเสมอ

ประกาศอาเรย์ตามขนาดที่คิดเอาเอง

โจทย์ให้ตาราง N × N ช่อง โดยที่ N ≤ 20000 น้องประกาศอาเรย์ int ไว้นอก main ตามขอบเขต

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

int grid[20000][20000];

int main()
{
    int n;
    cin >> n;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            grid[r][c] = r + c;
        }
    }
    cout << grid[n - 1][n - 1] << '\n';
    return 0;
}

คอมไพล์ผ่าน รันบนเครื่องที่เขียนเอกสารนี้ก็ผ่านทุกค่าของ n ไม่มีอะไรฟ้อง แต่ถ้าวัดหน่วยความจำ จะเห็นว่า Windows จองที่ไว้ให้ 1530 MB ตั้งแต่เปิดโปรแกรม ป้อน n = 1000 ใช้หน่วยความจำจริง 13.3 MB และป้อน n = 20000 ใช้จริง 1531.5 MB เกิน 256 MB ไปหลายเท่า ที่เครื่องเราไม่ฟ้องเพราะเครื่องมี RAM ราว 32 GB

คำนวณตามตารางข้างบนก่อนเขียนก็รู้แล้ว 20000 × 20000 × 4 byte คือ 1600 MB วิธีนี้ใช้ไม่ได้ตั้งแต่ต้น ต้องหาวิธีที่ไม่ต้องเก็บทั้งตาราง และอย่าวางใจว่าชุดทดสอบเล็กจะรอด grader แต่ละแบบนับหน่วยความจำต่างกัน บางแบบนับจากที่จองไว้ตั้งแต่เริ่มโปรแกรม ให้คิดจากขนาดที่ประกาศเสมอ

สรุป

• vector push_back pop_back v[i] เป็น O(1) แต่ erase หรือ insert ที่หัวเป็น O(N)
• ลบหัวแถวบ่อยๆ ใช้ queue หรือ deque หรือใช้ตัวแปร head
• s += c เป็น O(1) โดยเฉลี่ย s = s + c เป็น O(N) ทุกครั้ง
• ส่ง vector string หรือ struct ให้ฟังก์ชันด้วย & ไม่อย่างนั้นคัดลอกทุกครั้งที่เรียก
• หน่วยความจำคือจำนวนช่องคูณ sizeof หารล้านได้ MB รวมทุกอาเรย์แล้วต้องไม่เกินลิมิต ส่วนใหญ่คือ 256 MB