在 c# 中尽可能快地在大型列表中进行按位运算

Question

>我有一个来自 10，000 个长值的列表我想将该数据与其他 100，000 个多头值进行比较比较是按位运算 -->

if (a&b==a) count++;

我可以使用哪种算法来获得最佳性能？

Answer 1

如果我正确理解了你的问题，你想对照每个b检查a某个谓词是否为真。因此，问题的天真解决方案如下：

var result = aList.Sum(a => bList.Count(b => (a & b) == a));

我不确定这对于任意谓词是否真的可以加快速度，因为您无法绕过检查每个a与每个b。您可以尝试并行运行查询：

var result = aList.AsParallel().Sum(a => bList.Count(b => (a & b) == a));

例：

aList：10，000个随机long值; bList：100，000 个随机long值。

• 不带AsParallel：00：00：13.3945187

带AsParallel ： 00：

• 00：03.8190386

Answer 2

将所有

a放入trie数据结构中，其中树的第一级对应于数字的第一级，第二级对应于第二位，依此类推。然后，对于每个b，沿着三重奏走下去;如果这个位是 1 in b ，则计算两个分支，或者如果这个位在 b 中是 0，则只计算 trie 的 0 分支。我认为这应该是 O（n+m），但我还没有认真考虑过。

通过对 a 列表进行排序并以与 trie 大致相同的方式使用排序列表，您可能会获得相同的语义，但具有更好的缓存特征。就操作数量而言，这会稍微差一些 - 因为您必须在很多时候搜索东西 - 但对CPU缓存的尊重可能足以弥补它。

注

：注：我还没有想到正确性，而不是考虑大O符号，也就是说可能还不够。