确定2D数组是否包含元素的最快方法？

Question

我们假设我有2d数组,如:

int[,] my_array = new int[100, 100];

数组充满了整数.检查数组中是否包含目标值元素的最快方法是什么？

(*这不是作业,我试图为这种情况提出最有效的解决方案)

Answer 1

如果数组没有以某种方式排序,我看不出有什么比使用两个for语句检查每个值更快的速度.如果它已排序,您可以使用二进制搜索.

编辑:如果您需要反复执行此操作,您的方法将取决于数据.如果此数组中的整数范围最多为256,则可以使用该长度的布尔数组,并浏览数据中的值,并翻转布尔数组中的位.如果整数可以更高,则可以使用HashSet.对contains函数的第一次调用会有点慢,因为它必须索引数据.但随后的呼叫将是O(1).

EDIT1:

这将在第一次运行时索引数据,基准测试发现Contains在第一次运行后运行需要0毫秒,13运行到索引.如果我有更多的时间,我可能多线程并让它返回结果,同时在第一次调用时异步继续索引.此外,由于数组是引用类型,因此更改在索引之前或之后传递的数据的值将提供奇怪的功能,因此这只是一个示例,应该在使用之前进行重构.

private class DataContainer
{
    private readonly int[,] _data;
    private HashSet<int> _index;

    public DataContainer(int[,] data)
    {
        _data = data;
    }

    public bool Contains(int value)
    {

        if (_index == null)
        {
            _index = new HashSet<int>();
            for (int i = 0; i < _data.GetLength(0); i++)
            {
                for (int j = 0; j < _data.GetLength(1); j++)
                {
                    _index.Add(_data[i, j]);
                }
            }
        }
        return _index.Contains(value);
    }
}