在C ++中循环访问2d数组时提高O（n） [英] Improving O(n) while looping through a 2d array in C++

问题描述

我的目标是将我的O（n ^ 2）算法简化为O（n），因为这是Array2D类中的常见算法。 Array2D拥有类型T的多维数组。我看到的一个常见问题是使用双重嵌套的for循环遍历数组，具体速度取决于大小。

A goal of mine is to reduce my O(n^2) algorithms into O(n), as it's a common algorithm in my Array2D class. Array2D holds a multidimensional array of type T. A common issue I see is using doubly-nested for loops to traverse through an array, which is slow depending on the size.

如您所见，我在这里将双重嵌套的for循环简化为单个for循环。当我执行它时，它运行良好。速度肯定有所提高。还有其他方法可以提高此成员函数的速度吗？我希望将此算法用作其他对多维数组具有类似操作的成员函数的模型。

As you can see, I reduced my doubly-nested for loops into a single for loop here. It's running fine when I execute it. Speed has surely improved. Is there any other way to improve the speed of this member function? I'm hoping to use this algorithm as a model for my other member functions that have similar operations on multidimensional arrays.

        /// <summary>
        /// Fills all items within the array with a value.
        /// </summary>
        /// <param name="ob">The object to insert.</param>
        void fill(const T &ob)
        {
            if (m_array == NULL)
                return;

            //for (int y = 0; y < m_height; y++)
            //{
            //  for (int x = 0; x < m_width; x++)
            //  {
            //      get(x, y) = ob;
            //  }
            //}

            int size = m_width * m_height;
            int y = 0;
            int x = 0;

            for (int i = 0; i < size; i++)
            {
                get(x, y) = ob;

                x++;

                if (x >= m_width)
                {
                    x = 0;
                    y++;
                }
            }
        }

推荐答案

确保事情在内存中是连续的，因为缓存行为很可能会影响任何仅执行简单操作的代码的运行时。

Make sure things are contiguous in memory as cache behavior is likely to dominate the run-time of any code which performs only simple operations.

例如，don请勿使用：

For instance, don't use this:

int* a[10];
for(int i=0;i<10;i++)
  a[i] = new int[10];
//Also not this
std::vector< std::vector<int> > a(std::vector<int>(10),10);

使用此：

int a[100];
//or
std::vector<int> a(100);

现在，如果您需要2D访问，则使用：

Now, if you need 2D access use:

for(int y=0;y<HEIGHT;y++)
for(int x=0;x<WIDTH;x++)
  a[y*WIDTH+x];

使用1D访问进行紧密循环，不依赖邻居知识的全数组操作，或需要存储索引的情况：

Use 1D accesses for tight loops, whole-array operations which don't rely on knowledge of neighbours, or for situations where you need to store indices:

for(int i=0;i<HEIGHT*WIDTH;i++)
  a[i];

请注意，在以上两个循环中，触摸的项目数为 HEIGHT *两种情况下的宽度都为WIDTH 。尽管可能会出现，但其中一个的时间复杂度为 O（N ^ 2），而另一个 O（n） ，很明显，在两种情况下，完成的工作净额都是 HEIGHT * WIDTH 。最好将 N 视为操作涉及的项目总数，而不是涉及其接触方式的属性。

Note that in the above two loops the number of items touched is HEIGHT*WIDTH in both cases. Though it may appear that one has a time complexity of O(N^2) and the other O(n), it should be obvious that the net amount of work done is HEIGHT*WIDTH in both cases. It is better to think of N as the total number of items touched by an operation, rather than a property of the way in which they are touched.

这篇关于在C ++中循环访问2d数组时提高O（n）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！