关于bitset速度的问题

学术版

LeavingZzz @ 2020-11-25 08:06:27

RT
刚刚在这个帖子里看到
有同学说了这样一句话

如果不开O2一定不要用bitset,慢到爆炸！

虽然说的有点夸张但是我认为没有说错，因为在NOIO的 P6569 一题中，我自己写的比较丑的一个bitset解法会直接T掉，但是开氧气就会跑的比bool数组还要快，然后又尝试了题解中的一份代码，在不开氧气的情况下，bitset解法的速度都显著劣于bool数组的解法

然而

@OceanLiu 扯淡，再怎么慢比bool数组快多了

@OceanLiu xxs不清楚就不要说话

我想请这两位同学教教我怎么在P6569一题上不开氧气用bitset跑的比bool数组快
或者有知道的同学也可以教教我，谢谢了/qq

by LeavingZzz @ 2020-11-25 08:10:07

或者有人教教我bitset什么操作比较慢/在什么情况下会有优势嘛/kel

by AsunderSquall @ 2020-11-25 08:11:32

bool数组和bitset在单位的时候都是除以\omega的，然而bitset在数组快很多
因为你用bool数组的时候只能用for去遍历，这就变得极慢无比

by noip @ 2020-11-25 08:23:25

@我知道了王子为什么很多人把w写成omega呢...

by AsunderSquall @ 2020-11-25 08:24:34

@noip 我是傻逼（这样看上去好看）

by Hexarhy @ 2020-11-25 08:24:45

艹

by noip @ 2020-11-25 08:25:06

怪

by mrsrz @ 2020-11-25 08:59:34

bitset 只是当 bool 数组用的话确实比较慢。

by lytqwq @ 2020-11-25 09:11:55

bitset不是卡空间的吗（没用过几次）

by Flan @ 2020-11-25 10:01:31

bitset 优化矩阵就是比 bool 快

您的 bool 最后只乘了向量复杂度是 O(n^3\log a+qn^2\log a)

bitset 却没有向量优化复杂度是 O(n^3\log a+qn^3\log a)

复杂度完全不同没有可比性您的实验是假的

by wocaicai @ 2020-11-25 14:58:06

%楼上GD前十