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

本文关键字：速度 单值 类型 查找 | 更新日期: 2023-09-27 18:05:52

.NET 4.5.1

我有一"堆"Int16 值，适合从 -4 到 32760 的范围。该范围内的数字不是连续的，但它们的顺序是从 -4 到 32760。换句话说，从 16-302 的数字不在"一堆"中，但数字 303-400 在那里，数字 2102 不存在，等等。

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

有效的示例代码 

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

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

谢谢。

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

听起来

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

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

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

当然，如果这对您来说确实是一个性能瓶颈，您应该在实际应用程序中比较此解决方案和bool[]方法 - 微基准测试在这里并不像实际应用程序的行为那么重要。

为每个可能的值创建一个布尔值：

var isPresentItems = new bool[32760-(-4)+1];

将相应的元素设置为 true 如果给定项存在于集合中。查找很简单：

var isPresent = isPresentItems[myIndex];

不能再快了。布尔值将适合 L1 或 L2 缓存。

我建议不要使用 BitArray，因为它每个字节存储多个值。这意味着每次访问都较慢。需要位算术。

如果您想要疯狂的速度，请不要让 LINQ 为每个项目调用一次委托。LINQ 不是性能关键型代码的首选。许多使 CPU 停滞的间接事件。

如果要

优化查找时间，请选择具有O(1)(恒定时间(查找的数据结构。 您有多种选择，因为您只关心设置成员资格，而不关心排序或排序。

HashSet<Int16>会给你这个，BitArray也会给你索引max - min + 1。 绝对最快的临时解决方案可能是一个简单的数组索引max - min + 1，正如@usr所建议的那样。 这些中的任何一个都应该足够"足够快"。 HashSet<Int16>可能会使用最多的内存，因为内部哈希表的大小是一个实现细节。 BitArray将是这些选项中最节省空间的选项。

如果您只有一个查找，那么内存应该不是问题，我建议先使用HashSet<Int16>。 该解决方案很容易推理并以无错误的方式处理，因为您不必担心停留在数组边界内;您可以简单地检查set.Contains(n). 如果您的值范围将来可能会更改，这将特别有用。 如果需要进一步优化速度或性能，可以回退到其他解决方案之一。

一种选择是使用 HashSet。要查找值是否在其中，它是一个 O(1( 操作

代码示例：

HashSet<Int16> evenNumbers = new HashSet<Int16>();
    for (Int16 i = 0; i < 20; i++)
    {
        evenNumbers.Add(i);
    }

    if (evenNumbers.Contains(0))
    {
       /////
    }

由于数字是排序的，所以我会遍历列表一次，并生成具有开始和结束编号的Range对象的列表。 该列表将比拥有数千个数字的列表或字典小得多。

如果你的"一堆"数字可以识别为一系列区间，我建议你使用区间树。间隔树允许动态插入/删除，还可以搜索间隔是否与树中的任何间隔相交是 O(log(n((，其中 n 是树中的间隔数。在您的情况下，间隔数将小于整数数，并且搜索速度要快得多。

相关文章：