c# - 查找单值类型 c# 的纯速度？

Question

.NET 4.5.1

我有一个“一堆”Int16 值，范围从 -4 到 32760。范围内的数字不是连续的，但它们是从 -4 到 32760 排序的。换句话说，从 16 开始的数字-302 不在“束”中，但数字 303-400 在那里，数字 2102 不在那里，等等。

确定特定值(例如 18400)是否在“束”中的最快方法是什么？现在它在一个 Int16[] 中，Linq Contains 方法用于确定一个值是否在数组中，但如果有人能说出不同结构为什么/如何更快地传递单个值，我将不胜感激。速度是此查找的关键(“bunch”是静态类的静态属性)。

有效的示例代码

Int16[] someShorts = new[] { (short)4 ,(short) 5 , (short)6};
var isInIt = someShorts.Contains( (short)4 );

我不确定这是否是可以完成的最高效的事情。

谢谢。

Answer 1

听起来你真的很想BitArray - 只需将该值偏移 4，这样您就得到了 [0, 32764] 的范围，您应该没问题。

这将分配一个大小为 4K (32764/8) 的数组，数组中每个值一位。它将处理查找数组中的相关元素，并应用位掩码。 (我不知道它是在内部使用了一个 byte[] 还是别的东西。)

与存储范围相比，这可能是一种不太紧凑的表示，但是获取/设置位所涉及的唯一成本将是计算索引(基本上是移位)，将相关的内存位获取到CPU，然后位掩码。它占用 bool[] 大小的 1/8，使您的 CPU 缓存使用效率更高。

当然，如果这对您来说真的是性能瓶颈，您应该在实际应用程序中比较此解决方案和 bool[] 方法 - 微基准测试在这里几乎没有如何重要你真正的应用行为。