An answer to this question on Stack Overflow.

Question

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.

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++;
				}
			}
		}

Answer

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.

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);

Use this:

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

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];

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];

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.