比较bools的两个向量 [英] Comparing two vectors of bools
问题描述
我知道std :: vector< boolis专门用于存储单个bools
作为单个位。我对
对矢量< bool> s的比较操作有疑问。
比较是否一点一点地完成？那会很慢。从理论上说，只需要对所有位进行逐位XOR，然后将它们全部与
一起进行比较，然后将单个位进行比较吧？这将使它成为O（1）
而不是O（n）。这种方法有什么不好？
矢量的大小是否重要？例如，如果向量
是< = 32bits，它们可以放入两个寄存器中，并且很容易做到
XOR。但是如果它们不止于此那么它会更复杂
比较std :: bitset怎么样？比较工作方式是否相同
呢？
那么boost :: dynamic_bitset怎么样？有什么不同吗？
谢谢。
I know that std::vector<boolis specialized to store individual bools
as single bits. I have a question about the comparison operation on a
pair of vector<bool>s.
Is the comparison done bit by bit? That would be slow. In theory it''s
possible to just do a bit-wise XOR on all bits and then OR it all
together and compare the single bit right? That would make it O(1)
instead of O(n). What''s bad about this method?
Does the size of the vector matter here? For instance if the vectors
are <= 32bits they can fit into two registers and it''s easy to do the
XOR. But if they are more than that then it''s more complicated
What about comparison on std::bitset? Does compare work the same way
for it?
And what about boost::dynamic_bitset? Any difference for that?
Thanks.
推荐答案
fg ********* @ gmail.com 写道：
fg*********@gmail.com writes:
I知道std :: vector< boolis专门存储个人bools
作为单个位。我对
对矢量< bool> s的比较操作有疑问。
比较是否一点一点地完成？那会很慢。从理论上说，只需要对所有位进行逐位XOR，然后将它们全部与
一起进行比较，然后将单个位进行比较吧？这将使它成为O（1）
而不是O（n）。这种方法有什么不好的？
I know that std::vector<boolis specialized to store individual bools
as single bits. I have a question about the comparison operation on a
pair of vector<bool>s.
Is the comparison done bit by bit? That would be slow. In theory it''s
possible to just do a bit-wise XOR on all bits and then OR it all
together and compare the single bit right? That would make it O(1)
instead of O(n). What''s bad about this method?
不，它不会是O（1）。它仍然是O（n）。当然，这会更快，但是复杂性仍然是线性的，因为XOR运算的数量是与向量的大小成线性比例的。
。 />
No, it wouldn''t be O(1). It''s still O(n). This would be faster, of course,
but the complexity is still linear, since the number of XOR operations is
linearly proportional to the vector''s size.
>
向量的大小是否重要？例如，如果向量
>
Does the size of the vector matter here? For instance if the vectors
这将是实现定义的。如果可能的话，实现
将提供优化比较运算符是有意义的。
That would be implementation defined. It makes sense that an implementation
would provide an optimization comparison operator, if possible.
是< = 32bits它们可以适合两个注册并且很容易做到
XOR。但是如果它们超过那个则更复杂
are <= 32bits they can fit into two registers and it''s easy to do the
XOR. But if they are more than that then it''s more complicated
你需要阅读编译器'std :: vector<的实现。 bool>
确定它是如何完成的。
----- BEGIN PGP SIGNATURE -----
版本： GnuPG v1.4.9（GNU / Linux）
iEYEABECAAYFAkiTzeAACgkQx9p3GYHlUOI / 2gCdG7CLnV8rXSqol2mRDz1k9w75
38gAmgKzqUQpVZ2 + uPZ3 + UWcx0DEZ5fN
= 9Qpt
----- END PGP SIGNATURE -----
You''ll need to read the implementation of your compiler''s std::vector<bool>
to determine how it''s done.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
iEYEABECAAYFAkiTzeAACgkQx9p3GYHlUOI/2gCdG7CLnV8rXSqol2mRDz1k9w75
38gAmgKzqUQpVZ2+uPZ3+UWcx0DEZ5fN
=9Qpt
-----END PGP SIGNATURE-----
fg ********* @ gmail.com 写道：
fg*********@gmail.com wrote:
我知道std :: vector< boolis专门用于存储个人bools
作为单个位。
I know that std::vector<boolis specialized to store individual bools
as single bits.
实际上这被认为是一个黑客和AFAIR它将被删除
很快（在C ++ 0x？）。
Actually this is considered a bit of "hack" and AFAIR it will be removed
soon (in C++0x?).
8月1日，10：00 * pm，Sam< s ... @ email-scan.comwrote：
On Aug 1, 10:00*pm, Sam <s...@email-scan.comwrote:
fgh.vbn .... @ gmail.com写道：
fgh.vbn....@gmail.com writes:
我知道std :: vector< boolis专门用于存储单个bools
作为单个位。我有一个关于
对向量< bool> s的比较操作的问题。
I know that std::vector<boolis specialized to store individual bools
as single bits. I have a question about the comparison operation on a
pair of vector<bool>s.
比较完成比较？那会很慢。从理论上说，只需要对所有位进行逐位XOR，然后将它们全部与
一起进行比较，然后将单个位进行比较吧？这将使它成为O（1）
而不是O（n）。这种方法有什么不好的？
Is the comparison done bit by bit? That would be slow. In theory it''s
possible to just do a bit-wise XOR on all bits and then OR it all
together and compare the single bit right? That would make it O(1)
instead of O(n). What''s bad about this method?
不，它不会是O（1）。它仍然是O（n）。当然，这会更快，但是复杂性仍然是线性的，因为XOR运算的数量是与向量的大小成线性比例的。
。 />
No, it wouldn''t be O(1). It''s still O(n). This would be faster, of course,
but the complexity is still linear, since the number of XOR operations is
linearly proportional to the vector''s size.
嗯，如果我们有一个32位ALU，那么我们可以将两个向量加载到
对寄存器中并使用比较器来获取结果是一个周期。对？换句话说，我们正在并行执行所有异或后跟
后跟一个OR。如果我在这里错了，请纠正我。
当然，我不知道编译器是否真的会这样做。
谢谢。
Hmm, if we have a 32-bit ALU then we could load both vectors into a
pair of registers and use the comparator to get the result in "one
cycle" right? In other words, we are doing all XORs in parallel
followed by one OR. Please correct me if I''m wrong here.
Of course, I have no idea if the compiler would actually do this.
Thanks.
这篇关于比较bools的两个向量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
