c#修正了读取速度最快的结构

本文关键字：结构 速度 读取 | 更新日期: 2023-09-27 18:04:16

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

c#修正了读取速度最快的结构

我打赌是锯齿数组，除非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();
    }
}
  • 多维([,])数组几乎总是最慢的，除非在大量随机访问场景下。理论上它们不应该是，但这是CLR的一个奇怪之处。
  • 锯齿数组([][])几乎总是比多维数组快;即使是在随机访问的情况下。这些都有内存开销。
  • 在安全码中，一维([])和代数数组([y * stride + x])的随机存取速度最快。
  • 不安全代码通常在任何情况下都是最快的(只要你不重复地钉住它)。

对于"哪个X更快"(对于所有X)，唯一有用的答案是:您必须进行反映您的需求的性能测试。

记住要考虑，一般*:

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

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

*但是所有规则都有例外

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

希望有帮助!

最好的方法是使用HashMap

的字典吗?

相关文章：