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

本文关键字:运算 大型 尽可能 列表 | 更新日期: 2023-09-27 18:35:29

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

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

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

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

如果我正确理解了你的问题,你想对照每个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

将所有

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

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

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