比较bitset与bool的数据处理速度：性能分析与优化建议

前言&＃xff1a;

牛客2021多校Alice and Bob &＃xff0c;在这题中5000 * 5000 * 5000的复杂度&＃xff0c;用bitset 140ms&＃xff0c;bool 493ms。bitset快到起飞。
AcWing348–最优比率生成树&＃xff0c;这题用bitset会TLE&＃xff0c;用bool反而AC。

讨论&＃xff1a;

如果一直连续访问数组中的元素&＃xff0c;bool明显快于bitset。
bool : 26ms
bitset : 108ms

#include
using namespace std;
#define int long long
const int N &＃61; 1e6 &＃43; 5, mod &＃61; 1e9 &＃43; 7;
bitset<N> f;
signed main()
{srand((unsigned)time(0));freopen("data.in","r",stdin);freopen("data.out","w",stdout);clock_t start, stop;start&＃61;clock();int T &＃61; 50;while(T--){for (int i &＃61; 1; i <&＃61; N - 5; i&＃43;&＃43;) {f[i] &＃61; 1;}for (int i &＃61; 1; i <&＃61; N - 5; i&＃43;&＃43;){f[i] &＃61; 0;}}stop &＃61; clock();cout << endl << "time: " << stop - start;return 0;
}

但是访问较为随机的时候&＃xff0c;bitset又比bool更快&＃xff1a;
bool : 283ms
bitset : 224ms

#include
using namespace std;
#define int long long
const int N &＃61; 1e6 &＃43; 5, mod &＃61; 1e9 &＃43; 7;
bitset<N> f;
signed main()
{srand((unsigned)time(0));freopen("data.in","r",stdin);freopen("data.out","w",stdout);clock_t start, stop;start&＃61;clock();int T &＃61; 10;while(T--){for (int i &＃61; 1; i <&＃61; N - 5; i&＃43;&＃43;) {int x &＃61; rand() * rand() % (N - 5);f[x] &＃61; 1;}}stop &＃61; clock();cout << endl << "time: " << stop - start;return 0;
}

总结&＃xff1a;

随机访问时&＃xff0c;bitset更快&＃xff1b;连续访问时&＃xff0c;bool更快。所以多测如果要清空时&＃xff0c;建议选bool数组&＃xff0c;选bitset此时可能会TLE。牛客多校那题开头sg函数打表是比较随机的&＃xff0c;且多测不用清空&＃xff0c;所以bitset会非常快。