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

Question

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

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

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

Answer 1

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

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

把你所有的as放到一个trie数据结构中，树的第一层对应数字的第一位，第二层对应第二位，以此类推。然后，对于每个b，走下特里；如果该位为 1 in b，则计算两个分支，或者如果该位为 0 in b，则仅计算 trie 的 0 分支。我认为这应该是 O(n+m)，但我并没有认真考虑过。

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

注意，我对正确性的考虑并不比我对大 O 表示法的考虑要困难得多，也就是说可能还不够。