3

我有一些大型二维数据元素数组。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。

4

5 回答 5

2

我赌的是锯齿状阵列，除非 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();
    }
}
于 2011-08-03T10:46:07.870 回答
2
  • 多维 ( [,]) 数组几乎总是最慢的，除非在大量随机访问的情况下。理论上它们不应该是这样，但这是 CLR 的怪事之一。
  • 锯齿状数组 ( [][]) 几乎总是比多维数组快；即使在随机访问场景下。这些有内存开销。
  • 一维 ( []) 和代数数组 ( [y * stride + x]) 在安全代码中是最快的随机访问。
  • 通常，不安全代码在所有情况下都是最快的（只要您不重复固定它）。
于 2011-08-03T11:09:35.063 回答
1

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

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

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

另外考虑您需要查看完整的程序来决定在哪里进行优化。将循环加速 1% 可能对该循环有用，但如果它仅占整个运行时的 1%，那么它不会产生太大差异。

*但所有规则都有例外。

于 2011-08-03T10:40:22.323 回答
0

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

希望有帮助！

于 2018-09-28T01:51:43.637 回答
-2

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

字典？

于 2011-08-03T10:44:27.547 回答