缓存友好且速度更快 - `InvokeMe()`

Question

我想知道这是否真的是最快的方法。我希望它尽可能快，缓存友好，并提供良好的时间复杂度。

private static void InvokeMe() 
{
    int hz = horizontal.GetLength(0) * horizontal.GetLength(1);
    int vr = vertical.GetLength(0) * vertical.GetLength(1);
    int hzcol = horizontal.GetLength(1);
    int vrcol = vertical.GetLength(1);
    
    //Determine true from Horizontal information:
    for (int i = 0; i < hz; i++)
    {
        if(horizontal[i / hzcol, i % hzcol] == true)
           System.Console.WriteLine("True, on position: {0},{1}", i / hzcol, i % hzcol);
    }

    //Determine true position from vertical information:
    for (int i = 0; i < vr; i++)
    {
        if(vertical[i / vrcol, i % vrcol] == true)
           System.Console.WriteLine("True, on position: {0},{1}", i / vrcol, i % vrcol);
    }
}

我阅读的页数：

Is there a "faster" way to iterate through a two-dimensional array than using nested for loops?
Fastest way to loop through a 2d array?
Time Complexity of a nested for loop that parses a matrix
Determining the big-O runtimes of these different loops?

编辑： 代码示例现在更接近我正在处理的内容。它是关于从 N*N 网格中确定一个真实点 x,y。可用的信息是：水平和垂直二维数组。

不要造成混淆。想象一下，随着时间的推移，某些垂直或水平位置被设置为 True。这目前非常有效。我所关心的是，当前的方法是像这样对每个二维数组使用一个 for 循环，而不是对每个二维数组使用两个 for 循环.

Answer 1

你考虑过吗

for (int i = 0; i < row; i++)
{
    for (int j = 0; j < col; j++)
    {
        Console.Write(string.Format("{0:00} ", matrix[i, j]));
        Console.Write(Environment.NewLine + Environment.NewLine);
    }
}

它基本上与您的循环相同，但没有 / 和 % 编译器可能会优化也可能不会优化。

Answer 2

使用一个循环和嵌套循环的方法的时间复杂度是相同的 - O(row * col)（对于 row == col 是 O(n^2)，如您的示例对于这两种情况），因此执行时间的差异将来自操作常量（因为遍历方向应该相同）。您可以使用 BenchmarkDotNet 来衡量这些。下一个基准：

[SimpleJob]
public class Loops
{
    int[, ] matrix = new int[10, 10];
    [Benchmark]
    public void NestedLoops()
    {
        int row = matrix.GetLength(0);
        int col = matrix.GetLength(1);
        for (int i = 0; i < row ; i++)
        for (int j = 0; j < col ; j++)
        {
            matrix[i, j] = i * row + j + 1;
        }
    }
    
    [Benchmark]
    public void SingleLoop()
    {
        int row = matrix.GetLength(0);
        int col = matrix.GetLength(1);
        var l = row * col; 
        for (int i = 0; i < l; i++)
        {
            matrix[i / col, i % col] = i + 1;
        }
    }
}

在我的机器上给出：

Method	Mean	Error	StdDev	Median
NestedLoops	144.5 ns	2.94 ns	4.58 ns	144.7 ns
SingleLoop	578.2 ns	11.37 ns	25.42 ns	568.6 ns

使单循环实际上更慢。

如果您将循环体更改为某些“虚拟”操作 - 例如增加一些外部变量或更新 martix 的固定（例如第一个）元素，您会发现两个循环的性能大致相同。

缓存友好且速度更快 - `InvokeMe()`

Cache friendly and faster way faster - `InvokeMe()`

c#

performance

time-complexity