Can you get rotating an array to run faster than O(n²)?


Some follow-up remarks to my old posting on rotating a two-dimensional array:

Some people noticed that the article I linked to purporting to rotate the array actually transposes it. I was wondering how many people would pick up on that.

I was surprised that people confused rotating an array (or matrix) with creating a rotation matrix. They are unrelated operations; the only thing they have in common are the letters r-o-t-a-t-i. A matrix is a representation of a linear transformation, and a rotation matrix is a linear transformation which rotates vectors. In other words, applying the rotation matrix to a vector produces a new vector which is a rotated version of the original vector. The linear transformation is a function of one parameter: It takes a vector and produces a new vector. A rotation matrix is a matrix which rotates other things. Whereas rotating an array is something you do to the array. The array is the thing being rotated, not the thing doing the rotating. It didn't even occur to me that people would confuse the two. It's the difference a phone dial and dialing a phone.

Showing that you cannot rotate an array via matrix multiplication is straightforward. Suppose there were a matrix R which rotated an array (laid out in the form of a matrix) clockwise. The result of rotating the identity matrix would be a a matrix with 1's along the diagonal from upper right to lower left, let's call that matrix J. Then we have RI = J, and therefore R = J. Now apply R to both sides: RRI = RJ = I and therefore R² = I. But clearly rotating clockwise twice is not the identity for n ≥ 2. (Rotating clockwise twice is turning upside-down.)

A more mechanical way to see this is to take the equation R = J and show that J does not perform the desired operation; just try it on the matrix with 1 in the upper left entry and 0's everywhere else.

And since it's one of those geeky math pastimes to see how many differents proofs you can come up with for a single result, the third way to show that rotation cannot be effected by matrix multiplication is to observe that the transformation is not linear. (That's the magical algebra-theoretical way of showing it, which is either so obvious you can tell just by looking at it or so obscure it defies comprehension.) [The transformation viewed as a transformation on matrices rather than a transformation on column vectors is indeed linear, but the matrix for that would be an n² × n² matrix, and the operation wouldn't be matrix multiplication, so that doesn't help us here.]

The last question raised by this exercise was whether you could do better than O(n²). Computer science students spend so much time trying to push the complexity of an algorithm down that they neglect to learn how to tell that you can't go any lower. In this case, you obviously can't do better than O(n²) because every single one of the n² entries in the array needs to move (except of course the center element if n is odd). If you did less than O(n²) of work, then for sufficiently large n, you will end up not moving some array elements, which would be a failure to complete the required operation.

Bonus chatter: Mind you, you can do better than O(n²) if you change the rules of the problem. For example, if you allow pretending to move the elements, say by overloading the [] operator, then you can perform the rotation in O(1) time by just writing a wrapper:

struct IArray
{
  virtual int& Element(int x, int y) = 0;
  virtual ~IArray() = 0;
};

class RotatedArray : public IArray {
public:
 RotatedArray(IArray *p) : m_p(p) { }
 ~RotatedArray() { delete m_p; }

 int& Element(int x, int y) {
  return m_p->Element(y, x);
 }
private:
 IArray *m_p;
};

void RotateInPlace(IArray *& p, int N)
{
 p = new RotatedArray(p);
}

This pseudo-rotates the elements by changing the accessor. Cute but doesn't actually address the original problem, which said that you were passed an array, not an interface that simulates an array.

Comments (33)
  1. Alex says:

    Correct me if I’m wrong, but the RotatedArray doesn’t rotate at all. It flips the array according to the diagonal axis. For example, the item in position 0,0 stays in place where it should be in position n,0

    [Congratulations, you found the inside joke (see second paragraph). -Raymond]
  2. R says:

    You cannot take ownership of the IArray pointer just like that! This is disgraceful! :-)

  3. Mark (The other Mark) says:

    "It’s the difference a phone dial and dialing a phone."

    Particularly if you remember rotary phone dials.

  4. Duran says:

    You’re getting a little too meta with your humor, Raymond.

  5. Alexandre Grigoriev says:

    This problem is just a bunch of rotations of each 4 elements. But if you want to get fancy, you can: 1) transpose the matrix 2) then mirror it relative to the vertical axis of symmetry. This sequence of operations is equivalent to rotation.

  6. optimize says:

    Memory writes are not free, they are usually much more expensive than a conditional compare. If the correct value, by coincidence, already exist at the target position, it doesn’t need to be written there. All memory must be read anyway, only 1 temp value have to be stored in some register.

  7. Anonymous Coward says:

    >Cute but doesn’t actually address the original problem, which said that you were passed an array, not an interface that simulates an array.

    Yes it does. Array means “something that exports the interface Array”, you should know that by now. The way the bits are actually stored is unimportant as long as you can get the information in/out fast enough for your purpose. Any large array will be stored with a much greater degree of convolution than the adding of a flag or the changing of a method pointer anyway. You can make the program see a flat array, even if in reality stale pages of it are compressed to avoid hitting the disk. Surely that still qualifies as an array; surely adding an extra flag is a completely permissible solution to the problem.

    [What is this “Array” interface you talk about? I can’t find it in my C language reference. “Array” is not an interface in Java or C# either. And besides this “adding a flag” is not part of the original “Array” interface so that wouldn’t help anyway. Your solution wouldn’t rotate an Array; it would rotate an “augmented Array”. -Raymond]
  8. Alexandre Grigoriev says:

    @optimize,

    You forgot that memory writes go to the cache first, and get flushed by a cache line (64 bytes). It’s pretty likely at least one of items in the line will actually need to be written.

  9. J says:

    Indeed, would-be optimizers often fail to take into account one or more aspects of the actual hardware.

    Which is why the golden rule of optimization is "for the love of god, profile it!"

  10. A. Skrobov says:

    A related task that I was given at an interview: transpose a non-square matrix in-place.

    Anyone want to try to solve?

  11. Daniel says:

    To transpose a matrix quickly, you need to take into account the size of your processor cache; or use a cache oblivious algorithm.

    The trivial matrix transposition code will go through the array both in row-major and column-major order. So no matter how the matrix is stored; for sufficiently large matrices, that’s a cache miss on every second memory access. Ouch!

  12. Random832 says:

    Why is “n” the length of one dimension (and only meaningful for square arrays, not all two-dimensional arrays, though presumably for non-square arrays you would say “m*n” instead) rather than the number of elements?

    [Because in the original problem statement, “n” is the length of one dimension. -Raymond]
  13. J says:

    "[What is this "Array" interface you talk about? I can’t find it in my C language reference. "Array" is not an interface in Java or C# either. And besides this "adding a flag" is not part of the original "Array" interface so that wouldn’t help anyway. Your solution wouldn’t rotate an Array; it would rotate an "augmented Array". -Raymond]"

    If your function is defined to return an "Array" which happens to be the rotation of the original one, a custom accessor is easy to do. It’s all a matter of defining the spec well enough ;)

    (Well enough for the implementor at least)

  14. Marquess says:

    @J:

    Who said you are the implementor? For all you know, you were given a two-dimensional array whose only operations are reading and writing an element by row and column number. And you have to return it in the same format.

  15. NT says:

    Heh, I didn’t read the linked article, and I got most of the way through the post saying to myself, "why can’t it be done in O(n)?"  I decided that either 1) I was much more brilliant than Raymond (unlikely), or 2) I was missing something subtle about the definition of ‘rotate’ or a problem constraint.  Turns out we just didn’t agree on what ‘n’ meant. :)

  16. chustar says:

    One of the reasons I follow this blog so closely is because it allows me to learn a fair amount of new things (even in posts about his nieces).

    That said, I’m not sure I understand how this works exactly.

    Several things I noticed:

    1) He declared a function inside of a struct.

    2) He declared a virtual function to be 0.

    3) He created a class that inherits a from a struct.

    Also, in his declaration, he calls the function:

       return m_p->Element(y, x);

    However, earlier he declared that IArray::Element = 0, so how does the function call work?

  17. Marquess says:

    A blog post with an algebraic proof … *swoon*

  18. Marquess says:

    @J:

    Returning the same type is usually part of the exercise and, not surprisingly, real life.

  19. Bekenn says:

    @chustar:

    Just read everything here: http://www.parashift.com/c++-faq-lite/

  20. i says:

    "It’s the difference a phone dial and dialing a phone."

    The number you have dialed is imaginary.  Please rotate your phone 90 degrees and try again.

  21. Logan says:

    @chustar, the only difference between a class and a struct in C++ is the default visibility (public for struct, private for class). Knowing this, 1 and 3 should now make sense. ‘= 0’ denotes a pure virtual function. You cannot create an instance of a class with a pure virtual function, instead a descendant class must implement the method.

  22. chustar says:

    @Logan

    But isn’t m_p an instance of the pure struct?

    As in:

    private:

    IArray *mp;

    @Bekenn

    Checking it

  23. Evan says:

    "Computer science students spend so much time trying to push the complexity of an algorithm down that they neglect to learn how to tell that you can’t go any lower."

    Every once in a while you’ll see something like that. For instance, "you have to look at every element" is brought up as an argument for why finding, e.g., the maximum element in an unsorted array can’t be done in sublinear time, and the (Knuth’s?) proof that comparison-based sorting can’t be done in better than O(n*log n) seems to be reasonably standard fare for algo classes.

  24. "Computer science students spend so much time trying to push the complexity of an algorithm down that they neglect to learn how to tell that you can’t go any lower." ->  Proving what are called "lower bounds" is notoriously harder than "upper bounds".

    Stephan

  25. J says:

    Who says you have to return the exact same array?

    Unless your spec says you *must* modify the input array, you can return whatever subclass of your return type you want.

  26. James says:

    The thing about changing the accessor is cute, but it’s disingenuous to claim that it makes an O(n^2) operation O(1).  It’s just breaking up that O(n^2) operation into steps that are done lazily.  Actually applying those steps would still be O(n^2).

  27. Gabest says:

    And when those students leave the school they will realize 4×4 matrices are the most common and those are transposed with 4 raw dependent SSE shuffle pairs, doh.

  28. Levi says:

    It’s as if you were to asked to rotate a matrix written on a piece of paper and you just rotate the piece of paper == constant time. Brilliant!

  29. Dylan says:

    @James "Actually applying those steps would still be O(n^2)."

    Not quite.  With this augmented array datatype, while there is an overhead for access, you can rotate it as many times as you like during the time you spend using it at 0 additional cost.

  30. Alexandre Grigoriev says:

    @Dylan,

    The whole point of going into the array rotation trouble is to speed up the access to the rotated form. If you have to do index arithmetics, you just lose speed all the time.

  31. Joseph Koss says:

    Indexing is often very close to free these days, hidden in the latency of the memory operations that you are bottlenecked on.

  32. Harold De Armas says:

    Because I’m always game for a fun puzzle, to rotate using indices vs memory swapping:

    Rotated 0: ElementAt(x, y)

    Rotated 90 CC: ElementAt(n-y, x)

    Rotated 180 CC: ElementAt(n-x, n-y)

    Rotated 270 CC: ElementAt(y, n-x)

    Yet another thing to put on my list of "Clever tricks I wish I thought of during programming contests but did the quick & dirty way"

  33. Christian says:

    "ElementAt(n-y, x)" etc -> n-1-y?

Comments are closed.

Skip to main content