C# 固定数组 - 哪种结构读取速度最快？

Question

我有一些大型二维数据元素数组。 A 和 B 的尺寸不相等。

A) 介于 5 到 20 之间

B) 介于 1000 到 100000 之间

初始化时间没有问题，因为它只是用于实时应用程序的查找表，因此通过了解值 A 和 B 来索引元素的性能至关重要。当前存储的数据是单个字节值。

我正在考虑这些解决方案：

byte[A][B] datalist1a;

或或

byte[B][A] datalist2a;

或

byte[A,B] datalist1b;

或

byte[B,A] datalist2b;

或可能会失去多维，因为我知道固定大小，只需在查找之前将其乘以值即可。

byte[A*Bmax + B] datalist3;

或者

byte[B*Amax + A] datalist4;

我需要知道，当我进行此设置时，应使用哪种数据类型/数组结构来在 C# 中进行最有效的查找。

编辑1 前两个解决方案应该是多维的，而不是多数组。

编辑2 每次查找时都会读取最小维度中的所有数据，但大维度一次仅用于索引一次。

所以它就像 - 从样本 B 中获取所有 A。

Answer 1

我敢打赌锯齿状数组，除非 Amax 或 Bmax 是 2 的幂。

我这么说是因为锯齿状数组需要两次索引访问，因此速度非常快。其他形式意味着隐式或显式的乘法。除非乘法是一个简单的移位，否则我认为可能比几次索引访问要重一些。

编辑：这是用于测试的小程序：

class Program
{
    private static int A = 10;
    private static int B = 100;

    private static byte[] _linear;
    private static byte[,] _square;
    private static byte[][] _jagged;



    unsafe static void Main(string[] args)
    {
        //init arrays
        _linear = new byte[A * B];
        _square = new byte[A, B];
        _jagged = new byte[A][];
        for (int i = 0; i < A; i++)
            _jagged[i] = new byte[B];

        //set-up the params
        var sw = new Stopwatch();
        byte b;
        const int N = 100000;

        //one-dim array (buffer)
        sw.Restart();
        for (int i = 0; i < N; i++)
        {
            for (int r = 0; r < A; r++)
            {
                for (int c = 0; c < B; c++)
                {
                    b = _linear[r * B + c];
                }
            }
        }
        sw.Stop();
        Console.WriteLine("linear={0}", sw.ElapsedMilliseconds);

        //two-dim array
        sw.Restart();
        for (int i = 0; i < N; i++)
        {
            for (int r = 0; r < A; r++)
            {
                for (int c = 0; c < B; c++)
                {
                    b = _square[r, c];
                }
            }
        }
        sw.Stop();
        Console.WriteLine("square={0}", sw.ElapsedMilliseconds);

        //jagged array
        sw.Restart();
        for (int i = 0; i < N; i++)
        {
            for (int r = 0; r < A; r++)
            {
                for (int c = 0; c < B; c++)
                {
                    b = _jagged[r][c];
                }
            }
        }
        sw.Stop();
        Console.WriteLine("jagged={0}", sw.ElapsedMilliseconds);

        //one-dim array within unsafe access (and context)
        sw.Restart();
        for (int i = 0; i < N; i++)
        {
            for (int r = 0; r < A; r++)
            {
                fixed (byte* offset = &_linear[r * B])
                {
                    for (int c = 0; c < B; c++)
                    {
                        b = *(byte*)(offset + c);
                    }
                }
            }
        }
        sw.Stop();
        Console.WriteLine("unsafe={0}", sw.ElapsedMilliseconds);

        Console.Write("Press any key...");
        Console.ReadKey();
        Console.WriteLine();
    }
}

Answer 2

• 多维 ([,]) 数组几乎总是最慢的，除非在严重的随机访问场景下。理论上它们不应该是这样，但这是 CLR 的奇怪之处之一。
• 锯齿状数组 ([][]) 几乎总是比多维数组快；即使在随机访问场景下。这些都有内存开销。
• 单维 ([]) 和代数数组 ([y * stride + x]) 是安全代码中随机访问速度最快的。
• 通常，不安全代码在所有情况下都是最快的（前提是您不重复固定它）。

Answer 3

对于“哪个X更快”（对于所有X）唯一有用的答案是：您必须进行反映您的要求的性能测试。

并记住要考虑，一般^*：

• 程序的维护。如果这不是一个快速的解决方案，那么在大多数情况下，稍慢但可维护的程序是更好的选择。
• 微观基准可能具有欺骗性。例如，仅从集合中读取的紧密循环可能会以在完成实际工作时不可能的方式进行优化。

另外，请考虑您需要查看完整的程序来决定优化哪些地方。将循环速度加快 1% 可能对该循环很有用，但如果它只占完整运行时间的 1%，则不会产生太大差异。

---

^* 但所有规则都有例外。

Answer 4

在大多数现代计算机上，算术运算比内存查找快得多。
如果您获取不在高速缓存中的内存地址，或者从错误的位置执行无序执行，则您正在查看 10-100 个时钟，则流水线乘法为 1 个时钟。
另一个问题是缓存局部性。
字节[BAmax + A] datalist4;如果您按顺序访问 A 的变化，这似乎是最好的选择。
当访问 datalist4[bAmax + a] 时，计算机通常会开始拉入 datalist4[bAmax + a+ 64/sizeof(dataListType)], ... +128 ... 等，或者如果检测到反向迭代，则 datalist4[bAmax + a - 64/sizeof(dataListType)]

希望有帮助！

Answer 5

对你来说最好的方法可能是使用 HashMap

字典？