Trong Hội trại mùa xuân JOI 2018, một thiên tài trẻ tuổi nhật bản QCFium, đã viết một thuật toán ngây thơ trong bài Examination và đạt điểm tuyệt đối. Code như sau:
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
//Naive Solution as follows...
Thực tế, ngay cả , với 3 dòng ma thuật trên, độ phức tạp với thuật toán ngây thơ đã thực sự AC. Để kiểm tra xem việc tăng tốc này có thực sự hiệu quả hay không, tôi đã viết hai code sau: một code dùng ma thuật và một code không như bên dưới
Code A (With speedup)
#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;
}
Code B (Without speedup)
#include <iostream>
using namespace std;
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;
}
Khi tôi kiểm tra 2 code trên Codeforces thì kết quả là: code A sử dụng 2074ms nhưng code B sử dụng 2292ms. code A nhanh hơn ~10,5%. Thực tế trùm code Nhật Bản QCFium đã nói rằng "Code càng đơn giản thì càng nhanh với ma thuật 3 dòng tăng tốc." Vì vậy, có thể là khi dùng 3 dòng ma thuật trên, tốc độ tính toán tăng thành x1,2 hoặc x1,5.
Cảm ơn bạn đã đọc topic, hãy cho mình biết ý kiến của bạn phía dưới nhé ^_^
Tổng cộng 3 trả lời
ko biết như nào chứ cái default code của mình có 3 dòng là #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops")
mình chạy thử vòng for 1e9 mà nó vẫn chưa đến 1 s trong khi vứt đi phát thì chạy tận 1,5s ( trong vòng for ko viết gì nhá ) hình như 1e18 nó vẫn chưa đến 1s
Em cũng chưa gặp được bài nào trong thực tế mà sử dụng trâu với 3 dòng trên mà AC được Có lẽ tỉ lệ thật hiếm đáng kinh ngạc khi gặp được một bài như này trong một cuộc thi lớn như JOI, và ông QCFium kia thì thích chơi trội ¯_(ツ)_/¯
Thực ra, cái nhanh hơn ở đây (10-20%) là do cách trình biên dịch tối ưu hóa theo chỉ thị biên dịch thôi.
Trên các trang chấm bài sẽ để tham số biên dịch cố định, cí dụ như trang này C++ sử dụng trình biên dịch clang++ hoặc g++, tham số biên dịch:
(đối với C++ 11 và C++ 17, thay thế -std= số tương ứng)
Ta có thể thấy mặc định, chỉ thị biên dịch tối ưu là O2.
3 dòng "thần chú" ở trên:
Cái này có lẽ là tần dụng sức mạnh phần cứng (avx2) để tăng tốc các phép toán số học và xử lí bit
Là chỉ thị biên dịch tối ưu thành O3
Chỉ thị này có lẽ tối ưu hóa các vòng lặp gì đó
Và như vậy, về cơ bản các dòng "thần chú" này là các chỉ thị tối ưu cho việc biên dịch mã nguồn, tăng tốc được khoảng 10-20%.
Việc tăng 10-20% tốc độ thực thi nhưng việc biên dịch sẽ chậm hơn. Và trong lập trình thi đấu thì tăng khoảng 10% tốc độ cũng không có nhiều ý nghĩa.