8.9K 674 107

Đã đăng vào thg 12 20, 2023 8:00 SA 22 phút đọc

1.5K

Các kĩ năng thi cử 10.1: Kĩ thuật tối ưu tốc độ chương trình C++

I. Lời mở đầu

Trong các kì thi lập trình thi đấu, ngoài việc suy nghĩ thuật toán, các thí sinh còn phải đau đầu với một công việc, đó là tối ưu thời gian chạy chương trình. Nguyên do là vì, trong các kì thi này, ràng buộc về thời gian chạy của các bài tập khá ngặt nghèo, thường là $1$ giây, thậm chí là $0,5$ hay $0,1$ giây. Trong những trường hợp như vậy, ngoài việc tìm ra thuật toán tốt, các kĩ thuật để tối ưu thời gian chạy chương trình cũng quan trọng không kém.

Bài viết hôm nay sẽ chia sẻ tới bạn đọc một số kĩ thuật cũng như kinh nghiệm thường được sử dụng trong các kì thi lập trình để tối ưu thời gian thực thi chương trình, giúp thí sinh vượt qua được những cái bẫy về thời gian chạy của Ban tổ chức.

Toàn bộ kiến thức trong bài viết này sẽ liên quan tới ngôn ngữ lập trình C++, bởi vì ngôn ngữ này có tốc độ thực thi nhanh nhất trong các ngôn ngữ thường được sử dụng ở các kì thi lập trình. Nếu như các bạn lập trình bằng Python hoặc Java, thì hãy bỏ qua bài viết này luôn nha~~

II. Các kĩ thuật trong lập trình

1. Sử dụng kĩ thuật đẩy nhanh tốc độ nhập xuất dữ liệu

Trong các bài tập lập trình kiểu multi - testcase (nhập xuất nhiều bộ dữ liệu), chắc hẳn các bạn đã từng nhìn thấy những dòng lệnh này được đưa vào đầu hàm main() trước các dòng code khác:

ios_base:sync_with_stdio(false);
cin.tie(nullptr);

Điều đáng nói ở đây là, trong những bài tập như vậy, nếu như có thêm các dòng lệnh này thì thời gian chạy chương trình tăng lên đáng kể, đôi khi chỉ cần sử dụng các dòng lệnh này thì thuật toán sẽ đạt điểm tối đa, còn nếu không có chúng thì vẫn sẽ bị TLE một số test case (tất nhiên xét cùng một thuật toán). Câu hỏi là chúng có ý nghĩa gì?

Để giải thích sâu xa về vấn đề này, thì sẽ cần đến kiến thức về Streams trong C và C++. Input/Output trong C++ diễn ra trong các luồng (streams), cụ thể là dãy các bytes. Nếu các bytes chảy từ một thiết bị, như bàn phím, disk drive, hoặc một kết nối mạng…, tới bộ nhớ chính, nó được gọi là hoạt động Input. Nếu các byte chảy từ bộ nhớ chính tới các thiết bị, như màn hình hiển thị, máy in, dist drive, hoặc một kết nối mạng…, nó được gọi là hoạt động Output.

Đối với các lệnh nhập xuất dữ liệu cin và cout thuộc thư viện <iostream>, chúng ta có các Luồng đầu vào chuẩn (Standard Input Stream) và Luồng đầu ra chuẩn (Standard Output Stream), sẽ hỗ trợ việc nhập xuất dữ liệu bằng hai câu lệnh này, thông qua các toán tử chèn luồng >> và toán tử trích luồng <<.

Tuy nhiên, khi lập trình C++ ta lại có thể lập trình cả C. Vì vậy, các câu lệnh scanf() và printf() cũng có thể sử dụng để nhập xuất dữ liệu, kể cả khi các bạn đang lập trình C++. Theo chế độ mặc định, thì luồng nhập xuất tiêu chuẩn của C và C++ được đồng bộ hóa, điều này cho phép các bạn nhập xuất dữ liệu theo kiểu C hay C++ đều thu được kết quả đúng như mong muốn. Tuy nhiên điều này sẽ gây ra một chút rắc rối về thời gian chạy chương trình nếu như chúng ta nhập xuất quá nhiều bộ dữ liệu. Câu lệnh dưới đây có tác dụng tắt chế độ đồng bộ hóa giữa cin, cout với luồng chuẩn của C, và sẽ giúp chương trình nhanh hơn.

ios_base::sync_with_stdio(false);

Vậy còn cin.tie(nullptr); thì sao? Thực ra, lệnh này có tác dụng tắt đồng bộ giữa cin và cout. Theo mặc định, các luồng được liên kết để đảm bảo một luồng sẽ được "xả" hết (tức là in ra màn hình console với lệnh cout và nhập xong dữ liệu với lệnh cin) trước khi một thao tác mới được thực hiện trên luồng kia. Có thể hiểu đơn giản là các đầu ra cũ sẽ bị xóa đi (flushed) trước khi có thao tác nhập tiếp theo.

Điều này cũng có thể khiến cho chương trình chạy chậm đi nếu như có quá nhiều bộ dữ liệu nhập xuất. Vì vậy, dòng lệnh cin.tie(nullptr); được sử dụng để tắt sự liên kết giữa cin và cout nói trên, giúp chương trình thực thi nhanh hơn. Sau khi thêm vào các dòng lệnh này, thì tốc độ của cin và cout sẽ nhanh lên đáng kể, gần như bằng với scanf() và print().

Trong trường hợp không muốn sử dụng hai dòng lệnh trên, các bạn nên sử dụng nhập xuất dữ liệu theo kiểu C (scanf() và print()) sẽ giúp tốc độ nhập xuất dữ liệu chương trình đạt hiệu suất tốt nhất.

2. Sử dụng kĩ thuật khác về code

Có một số kĩ thuật khác có thể sử dụng trong lập trình thi đấu giúp đẩy nhanh tốc độ chương trình, các bạn cũng nên sử dụng chúng như một thói quen. Sau đây là một số kĩ thuật như vậy:

Sử dụng '\n' thay vì endl: Khi cần in kí tự xuống dòng, hãy sử dụng \n thay cho endl, nó sẽ giúp câu lệnh xuống dòng chạy nhanh hơn.
Sử dụng ++i thay vì i++: Hai câu lệnh này đều có tác dụng tăng giá trị biến $i$ $i$ lên $1$ $1$ đơn vị, thường được sử dụng trong vòng lặp. Tuy nhiên, đối với i++ thì giá trị cũ của $i$ $i$ sẽ được lưu lại, vì vậy có thể khiến chương trình chậm đi (nhưng không đáng kể). Dù vậy, ta vẫn nên sử dụng ++i trong mọi trường hợp.
```
for (int i = 1; i <= n; ++i)	
```
Xử lý bit thay vì nhân và chia: Các con số trong máy tính đều được dịch về hệ nhị phân, vì vậy trong một số trường hợp, các phép toán có thể được thay thế bằng các thao tác bit, giúp chương trình thực thi nhanh hơn. Dưới đây là một số ví dụ:
- Nhân hoặc chia một số cho $2^x$ : Thực tế là đẩy toàn bộ các bits của số đó qua bên trái hoặc bên phải $x$ bits. Ta có thể sử dụng câu lệnh sau khi muốn thực hiện nhân/chia cho $2^x$ :
```
n << x; // Nhân n với 2^x, dịch trái x bits.
n >> x; // Chia n với 2^x, dịch phải x bits.
```
- Kiểm tra tính chẵn lẻ: Thực tế ta chỉ cần kiểm tra bit đầu tiên của số đó có bằng $0$ hay không, nếu có thì nó phải là số chẵn. Ta có thể viết:
```
if (n & 1)
    cout << "n là số lẻ";
```
Sử dụng mảng tĩnh thay vì vector: Mặc dù vector là một cấu trúc dữ liệu rất tiện lợi, tuy nhiên nếu so với mảng tĩnh thì nó chạy chậm hơn khoảng $400$ lần, một con số không hề nhỏ. Bởi vậy, nếu có thể thì ta nên sử dụng mảng tĩnh thay vì vector.
Truyền tham số bằng tham chiếu: Việc truyền tham số bằng tham trị có thể khiến cho chương trình chạy chậm đi nếu như hàm đó là hàm đệ quy chẳng hạn, bởi vì mỗi lần truyền chương trình sẽ phải copy lại giá trị của tham số thực sự bên ngoài. Hãy tưởng tượng nếu như tham số của một hàm đệ quy là một vector hay string có kích thước $n$ $n$ thì sao? Việc truyền tham trị như dưới đây sẽ khiến chương trình chạy quá thời gian:
```
void func(vector < int > a);
```
Thay vào đó, hãy truyền tham chiếu, nó sẽ giúp cho chương trình chạy nhanh hơn nhiều:
```
void func(vector < int > &a);
```
Nhưng nói chung các bạn vẫn nên sử dụng mảng tĩnh thì tốt hơn~~

III. Sử dụng các lệnh chỉ thị `#pragma`

1. Chỉ thị `#pragma` là gì?

Các chỉ thị tiền xử lý #pragma là những chỉ thị đặc biệt, sử dụng để bật hoặc tắt những tính năng nhất định liên quan tới chương trình biên dịch. Dưới đây là một số ví dụ về#pragma:

Chỉ thị #pragma startup và #pragma exit: Dùng để chỉ thị cho chương trình biên dịch bắt đầu thực thi chương trình từ một hàm nào đó trước hàm main() và sẽ phải thực thi một hàm nào đó trước khi kết thúc hàm main(). Tuy nhiên, chỉ thị này sẽ không hoạt động được trong chương trình biên dịch GCC.
```
#include<stdio.h>

void func1();
void func2();

#pragma startup func1
#pragma exit func2

void func1()
{
    printf("Inside func1()\n");
}

void func2()
{
    printf("Inside func2()\n");	
}

int main()
{
    printf("Inside main()\n");
	
	return 0;
}
```
Kết quả chạy đoạn chương trình trên sẽ là:
```
Inside func1()
Inside main()
Inside func2()
```
Chỉ thị #pragma GCC poison: Chỉ thị này được hỗ trợ bởi GCC, có tác dụng loại bỏ một định danh nào đó của ngôn ngữ. Chẳng hạn, các bạn muốn loại bỏ định danh cout của ngôn ngữ C++, các bạn có thể sử dụng đoạn code dưới đây;
```
#pragma GCC optimize("O2")
#pragma GCC poison cout

#include <bits/stdc++.h>
#define int long long

using namespace std;

main()
{
    cout << "Hello World";

    return 0;
}
```
Đoạn code trên khi được thực thi, sẽ báo lỗi sau do từ khóa cout đã bị loại bỏ bởi #pragma:
<center>
</center>

Còn khá nhiều loại chỉ thị #pragma khác trong C/C++, tuy nhiên chúng ta sẽ không bàn thêm nhiều về nó ở đây. Nếu muốn tìm hiểu về #pragma, các bạn có thể tìm đọc thêm ở bài viết này.

2. Sử dụng `#pragma` để tối ưu thời gian chạy

Như vậy, chúng ta đã biết rằng #pragma là các chỉ thị liên quan tới chương trình biên dịch. Vậy thì nếu muốn sử dụng nó để tối ưu tốc độ chương trình, thì chắc chắn là dùng để tối ưu thời gian biên dịch chương trình. Tuy nhiên, những chỉ thị này các bạn chỉ nên sử dụng trên các trang online judge như Codeforces, Hackkerank,... còn trong các kì thi offline như Học sinh giỏi hay Tin học trẻ thì không nên sử dụng, có thể gây ra các lỗi không mong muốn (do chương trình biên dịch Ban tổ chức sử dụng không phù hợp chẳng hạn).

Chương trình biên dịch cho C/C++ thường được sử dụng trong các kì thi lập trình là GCC, và ta có thể sử dụng các chỉ thị để cải thiện tốc độ của chương trình. Những chỉ thị #pragma thường được sử dụng đối với GCC (đặc biệt là trên codeforces) là #pragma GCC optimize và #pragma GCC target. Sau đây chúng ta sẽ cùng tìm hiểu chi tiết về chúng.

2.1. Chỉ thị `#pragma GCC optimize`

Cú pháp

#pragma GCC optimize ({options})

Theo nguồn tài liệu chính thức về #pragma cho GCC, thì chỉ thị này cho phép các bạn bật một số flags (chính là các options) liên quan tới việc tối ưu cho các hàm ở phía sau. Một số flags quen thuộc nhất có thể kể đến là:

O0, O1: Những flags này không có ý nghĩa nhiều trong lập trình thi đấu, vì vậy ta sẽ không bàn tới chúng.
O2: Đây là một flag giúp tối ưu tốc độ dịch cũng như cải thiện hiệu năng của chương trình. Tuy nhiên, trên Codeforces cũng như trên chương trình chấm bài Themis, chế độ này đã được sử dụng mặc định nên việc dùng thêm nó cũng không có ý nghĩa gì.
O3: Đây là một flag khá nguy hiểm. Đôi khi nó có thể khiến cho chương trình của bạn chạy chậm đi (mặc dù hiếm khi xảy ra trong lập trình thi đấu). Một số điều mà flag này có thể làm là:
- Tự động "vector hóa" code của bạn, nếu như có thể. Việc này có thể làm code nhanh hơn nhiều bằng cách sử dụng SIMD (các lệnh đơn, đa dữ liệu).
- Các hàm nội tuyến (inline functions) sẽ hoạt động tốt hơn nếu có thể.
- Tối ưu vòng lặp tốt hơn flag O2, tuy nhiên nếu mã lệnh biên dịch ra quá nhiều có thể dẫn đến miss bộ nhớ cache.
Ofast: Flag này cũng khá nguy hiểm. Nó cung cấp tất cả các tối ưu hóa của flag O3, tuy nhiên kèm theo một số tối ưu hóa khác không theo tiêu chuẩn. Đôi khi nó khiến chương trình chạy chậm đi, vì vậy chỉ nên sử dụng khi bạn chắc chắn biết flag này sẽ làm gì.
unroll-loops: Flag này giúp tối ưu các vòng lặp, giúp giảm số lượng nhánh sinh ra và tối ưu code đồng thời. Tuy nhiên nó cũng có thể khiến cho kích thước của đoạn mã biên dịch trở nên quá lớn.

Sử dụng chính xác những pragmas này trong khi lập trình có thể giúp chương trình của bạn chạy nhanh lên khá nhiều. Chẳng hạn, nếu bạn muốn sử dụng flag O3 kết hợp với flag unroll-loops, ta có thể viết:

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

hoặc:

#pragma GCC optimize("O3,unroll-loops")

hay thậm chí là:

#pragma GCC optimize("O3","unroll-loops")

Tất cả các cách viết trên đều hợp lệ, tuy nhiên lưu ý ở giữa các flag bên trong cặp ngoặc () không được có dấu cách.

2.2. Chỉ thị `#pragma GCC target`

Phần lớn các máy tính hiện đại và các máy chấm lập trình thi đấu đều được xây dựng dựa trên cấu trúc x86. Trong nhiều năm, các tính năng mới đã được bổ sung vào cấu trúc, đặc biệt là các chỉ thị bổ sung giúp cho các phép tính cũng như các tính năng sẵn có trở nên nhanh hơn nhiều.

Các chương trình biên dịch cho phép chúng ta tận dụng phần mở rộng của các tập lệnh chỉ thị bổ sung này để cải thiện hiệu năng của chương trình. Lấy ví dụ, CPUs hỗ trợ chỉ thị popcnt cho phép hàm __builtin_popcount() chạy nhanh hơn nhiều. Hay nếu bạn muốn tự động vector hóa code của mình, bạn sẽ cần một số chỉ thị liên quan tới vector. Dưới đây là một list các chỉ thị được hỗ trợ trên trang web online judge Codeforces:

avx và avx2: Cung cấp các chỉ thị hỗ trợ vectorization code (tạo ra code tối ưu hơn). Ưu tiên sử dụng avx2 hơn vì nó mới hơn.
sse, sse2, sse3, sse4, sse4.1, sse4.2: Cũng tương tự như avx và avx2, nhưng không tốt bằng vì chúng cũ hơn.
popcnt, lzcnt: Cung cấp các chỉ thị giúp tối ưu các hàm __builtin_popcount() và __builtin_clz(). Những bài nào có sử dụng các hàm trên thì nên dùng thêm các chỉ thị này.
abm, bmi, bmi2: Cung cấp các chỉ thị liên quan tới thao tác xử lý bit.

Cách khai báo và sử dụng các chỉ thị này giống như khi sử dụng #pragma GCC optimization. Các bạn chỉ cần lựa chọn cho phù hợp với mục đích của mình.

2.3. Sử dụng chúng như thế nào?

Thông thường, nếu sử dụng kết hợp cả các chỉ thị optimization lẫn các chỉ thị target, sẽ giúp chương trình chạy nhanh hơn từ $2$ tới $8$ lần. Do đó, trong điều kiện cho phép (chương trình biên dịch phù hợp, kỳ thi phù hợp), các bạn nên sử dụng kết hợp các chỉ thị này. Một cách sử dụng hợp lý có thể như dưới đây:

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

main()
{
    {Code here};
}

Một ví dụ khá kinh điển các bạn có thể xem qua đó là ở bài tập Examination thuộc kỳ thi JOI 2018 Spring Camp. Thí sinh QCFium đã AC bài này bằng thuật toán $O(n \times q),$ mặc dù giới hạn của bài tập là $1 \le n, q \le 10^5$ . Chỉ bằng cách thêm vào các dòng lệnh chỉ thị #pragma đã giúp thí sinh này full điểm một bài tập khó bằng thuật toán vô cùng đơn giản:

#include <iostream>

using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

int cnt = 0;

int main() {
    for (int i = 1; i <= 30000; i++) {
        for (int j = 1; j <= 30000; j++) {
            if (i % j <= 10) cnt++;
        }
    }

    cout << cnt << endl;
	
    return 0;
}

Một ví dụ khác có thể đưa ra để làm minh chứng cho khả năng tối ưu code của các chỉ thị #pragma là thuật toán Sàng số nguyên tố Eratosthenes chẳng hạn. Với đoạn code dưới đây (chưa có tối ưu), cùng xem tốc độ chạy chương trình ra sao:

#include <bits/stdc++.h>
#include <sys/time.h>
#define n 10000005

using namespace std;

vector < bool > prime;

// Eratosthenes sieve.
void sieve_of_eratosthenes()
{
    prime.resize(n, true);

    for (int i = 2; i * i <= n; ++i)
        if (prime[i])
            for (int j = i * i; j <= n; j += i)
                prime[j] = false;
}

int main()
{
    // Initialize clock to calculate time required to execute
    // without optimization.
    clock_t start, end;

    // Start clock.
    start = clock();

    // Function call to find Prime Numbers.
    sieve_of_eratosthenes();

    // End clock.
    end = clock();

    // Calculate the time difference.
    double time_taken = double(end - start) / double(CLOCKS_PER_SEC);

    // Print the Calculated execution time.
    cout << "Execution time: " << time_taken << " secs";

    return 0;
}

Kết quả:

Execution time: 0.534 secs

Thời gian biên dịch và thực thi chương trình là khoảng $0,5$ giây. Tuy nhiên, khi thêm vào các chỉ thị tối ưu thì kết quả thu được sẽ khác hẳn. Ta sẽ thử thêm vào các tối ưu về optimization và target:

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>
#include <sys/time.h>
#define n 10000005

using namespace std;

vector < bool > prime;

// Eratosthenes sieve.
void sieve_of_eratosthenes()
{
    prime.resize(n, true);

    for (int i = 2; i * i <= n; ++i)
        if (prime[i])
            for (int j = i * i; j <= n; j += i)
                prime[j] = false;
}

int main()
{
    // Initialize clock to calculate time required to execute
    // without optimization.
    clock_t start, end;

    // Start clock.
    start = clock();

    // Function call to find Prime Numbers.
    sieve_of_eratosthenes();

    // End clock.
    end = clock();

    // Calculate the time difference.
    double time_taken = double(end - start) / double(CLOCKS_PER_SEC);

    // Print the Calculated execution time.
    cout << "Execution time: " << time_taken << " secs";

    return 0;
}

Kết quả:

Execution time: 0.297 secs

Ta thấy thời gian biên dịch và thực thi chương trình đã giảm đi hẳn một nửa!

IV. Kết luận

Như vậy, chúng ta đã cùng nhau thảo luận về tất cả những kĩ thuật thường gặp nhất trong lập trình thi đấu để cải thiện tốc độ biên dịch và chạy chương trình. Điều cuối cùng các bạn cần chú ý là, hãy lựa chọn những phương pháp phù hợp với kì thi của mình. Chẳng hạn như đối với các kì thi HSG, hãy cân nhắc thật cẩn thận khi sử dụng các chỉ thị #pragma, vì có thể sẽ gây ra lỗi không đáng có.

Tất nhiên, đây chỉ là những kinh nghiệm được đúc kết để tăng tốc độ một chút, chứ không thể thay thế hoàn toàn cho thuật toán. Vì vậy, điều đầu tiên cần làm vẫn là phải tìm ra một thuật toán tốt, rồi mới nghĩ đến việc áp dụng những kĩ thuật này. Ngoài ra, hãy cẩn trọng với các chỉ thị, vì như đã nói, đôi khi chúng có thể làm chương trình của bạn chậm đi.

V. Tài liệu tham khảo

Competitive Programming Viblo Algorithm

I. Lời mở đầu

II. Các kĩ thuật trong lập trình

1. Sử dụng kĩ thuật đẩy nhanh tốc độ nhập xuất dữ liệu

2. Sử dụng kĩ thuật khác về code

III. Sử dụng các lệnh chỉ thị #pragma

1. Chỉ thị #pragma là gì?

2. Sử dụng #pragma để tối ưu thời gian chạy

2.1. Chỉ thị #pragma GCC optimize