问题自然是 O(n),因此您的解决方案可能是最有效的。
由于您试图计算位的任意子集,因此您无法在设置位时对其进行计数(如果您不经常设置位,将提供速度提升)。
您可以检查您正在使用的处理器是否有一个将返回设置位数的命令。例如,根据这篇文章,具有 SSE4 的处理器可以使用 POPCNT 。这可能对您不起作用,因为.Net 不允许组装(因为它与平台无关)。此外,ARM 处理器可能没有等效的。
可能最好的解决方案是查找表(或者如果您可以保证开关将编译为单次跳转到 currentLocation + byteValue,则进行开关)。这将为您提供整个字节的计数。当然,BitArray 不提供对底层数据类型的访问权限,因此您必须制作自己的 BitArray。您还必须保证字节中的所有位始终是听起来不太可能的交集的一部分。
另一种选择是使用布尔数组而不是 BitArray。这具有不需要从字节中的其他位中提取位的优点。缺点是该数组将占用 8 倍的内存空间,这意味着不仅浪费空间,而且在您遍历数组以执行计数时还会推送更多数据。
标准数组查找和 BitArray 查找之间的区别如下:
数组:
- 偏移量 = 索引 * 索引大小
- 在位置+偏移处获取内存并保存到值
位数组:
- 索引 = 索引/索引大小
- 偏移量 = 索引 * 索引大小
- 在位置+偏移处获取内存并保存到值
- 位置 = 索引%indexSize
- 移位值位置位
- 价值 = 价值和 1
除了#2 for Arrays 和#3 之外,这些命令中的大多数都需要 1 个处理器周期才能完成。一些命令可以使用 x86/x64 处理器组合成 1 个命令,但可能不适用于 ARM,因为它使用的指令集减少了。
两者中哪一个(阵列或位阵列)性能更好取决于您的平台(处理器速度、处理器指令、处理器缓存大小、处理器缓存速度、系统内存量 (Ram)、系统内存速度 (CAS)、处理器和 RAM 之间的连接)以及要计算的索引的分布(是最常聚集的交叉点还是随机分布的)。
总而言之:您可能会找到一种使其更快的方法,但您的解决方案是使用 .NET 中的每个布尔模型为您的数据集获得的最快解决方案。
编辑:确保您正在访问要按顺序计算的索引。如果您按顺序访问索引 200、5、150、151、311、6,那么您将增加缓存未命中的数量,从而导致花费更多时间等待从 RAM 中检索值。