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

Question

我有一个由10,000个长整型值组成的列表，我想将这些数据与另外100,000个长整型值进行比较。比较是一种按位操作-->

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

哪种算法可以让我的性能最佳？

- Hamid

---

你是否试图计算在A中，B拥有所有位都打开的Int64的数量？ - agent-j

如果您首先对这两个列表进行排序，那么您可以在一次并行遍历它们的过程中计算出匹配项的数量。 - Jon

@agent-j 是的，我正在尝试计数。 - Hamid

你可以尝试使用普通数组上的 for 循环。当然，这并不是渐近快速的，但是使用列表（特别是LINQ）会带来更多开销。 - harold

只是有点迂腐（抱歉）：如果a和b的类型为long，那么a & b == a将无法编译，因为它意味着a & (b == a)，而没有"and"（&）运算符重载一个long和一个bool。缺少括号。 - Jeppe Stig Nielsen

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

- dtb

---

仅仅因为你将工作分配给了更多的人并不意味着你正在更有效率地工作。 - J. Holmes

谢谢。为什么我使用并行性能减少和处理时间更长？ - Hamid

@32bitkid：如果我有足够的人手，为什么要更有效率地工作呢？;-) 我认为你的另一个评论很到位：首先尝试使用AsParallel的朴素解决方案，如果不符合要求，则考虑tries等其他方法。 - dtb

我的CPU是双核64位的，但在并行模式下性能会降低。为什么？ - Hamid

并行速度问题是由于我的错误，我会将您的回复标记为答案。当我测试时，AList.Foreach比较快，非常感谢。 - Hamid

Answer 2

将所有的a放入一个trie数据结构中，其中树的第一级对应于数字的第一位，第二级对应于第二位，以此类推。然后，对于每个b，在trie上向下遍历；如果b的这一位为1，则计算两个分支，或者如果b的这一位为0，则只计算trie的0分支。我认为这应该是O(n+m)，但我没有仔细思考过。

通过对a的列表进行排序并使用排序后的列表来执行与trie类似的操作，您可以获得相同的语义，但具有更好的缓存特征。从操作数量上来说，这可能会略微差一些——因为您必须经常搜索东西——但对CPU缓存的尊重可能会弥补这一点。

注：我对正确性的思考不够深入，就像我对大O符号的思考一样。

- Iain

---

在我对简单解决方案进行分析并确定它实际上是一个无法接受的瓶颈之后，我会尝试这个。 - J. Holmes