{"id":15383,"date":"2010-01-06T07:00:00","date_gmt":"2010-01-06T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2010\/01\/06\/can-you-get-rotating-an-array-to-run-faster-than-on\/"},"modified":"2010-01-06T07:00:00","modified_gmt":"2010-01-06T07:00:00","slug":"can-you-get-rotating-an-array-to-run-faster-than-on","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20100106-00\/?p=15383","title":{"rendered":"Can you get rotating an array to run faster than O(n²)?"},"content":{"rendered":"

\nSome follow-up remarks to my old posting on\n\nrotating a two-dimensional array<\/a>:\n<\/p>\n

\nSome people noticed that the article I linked to purporting to rotate\nthe array actually transposes it.\nI was wondering how many people would pick up on that.\n<\/p>\n

\nI was surprised that people confused\nrotating an array (or matrix) with creating a rotation matrix.\nThey are unrelated operations;\nthe only thing they have in common are the letters r-o-t-a-t-i.\nA matrix is a representation of a linear transformation,\nand\na rotation matrix is a linear transformation which rotates vectors<\/i>.\nIn other words, applying the rotation matrix to a vector produces\na new vector which is a rotated version of the original vector.\nThe linear transformation is a function<\/i> of one parameter:\nIt takes a vector and produces a new vector.\nA rotation matrix is a matrix which rotates other things<\/i>.\nWhereas rotating an array is something you do to the array<\/i>.\nThe array is the thing being rotated, not the thing doing the rotating.\nIt didn’t even occur to me that people would confuse the two.\nIt’s the difference a phone dial and dialing a phone.\n<\/p>\n

\nShowing that you cannot rotate an array via matrix multiplication\nis straightforward.\nSuppose there were a matrix R<\/i> which rotated an array (laid\nout in the form of a matrix) clockwise.\nThe result of rotating the identity matrix would be a\na matrix with 1’s along the diagonal\nfrom upper right to lower left, let’s call that matrix J<\/i>.\nThen we have RI = J<\/i>, and therefore R = J<\/i>.\nNow apply R<\/i> to both sides:\nRRI = RJ = I<\/i>\nand therefore R² = I<\/i>.\nBut clearly rotating clockwise twice is not the identity\nfor n<\/i> ≥ 2.\n(Rotating clockwise twice is turning upside-down.)\n<\/p>\n

\nA more mechanical way to see this is to take the equation\nR = J<\/i> and show that J<\/i>\ndoes not perform the desired operation;\njust try it on the matrix with 1 in the upper left entry and 0’s everywhere\nelse.\n<\/p>\n

\nAnd since it’s one of those geeky math pastimes to see\n\nhow many differents proofs you can come up with for a single result<\/a>,\nthe third way to show that rotation cannot be effected by\nmatrix multiplication is to observe that the transformation is not linear.\n(That’s the magical algebra-theoretical way of showing it,\nwhich is either so obvious you can tell just by looking at it<\/i>\nor\nso obscure it defies comprehension<\/i>.)\n[The transformation viewed as a transformation on matrices rather\nthan a transformation on column vectors is indeed linear,\nbut the matrix for that would be an n² × n²<\/i>\nmatrix, and the operation wouldn’t be matrix multiplication,\nso that doesn’t help us here.]\n<\/p>\n

The last question raised by this exercise was\n\nwhether you could do better than O<\/i>(n<\/i>²)<\/a>.\nComputer science students spend so much time trying to push the\ncomplexity of an algorithm down\nthat they neglect to learn how to tell that you can’t go any lower.\nIn this case, you obviously can’t do better than O<\/i>(n<\/i>²)\nbecause every single one of the n<\/i>² entries in the array\nneeds to move (except of course the center element if n<\/i> is odd).\nIf you did less than O<\/i>(n<\/i>²) of work,\nthen for sufficiently large n<\/i>,\nyou will end up not moving some array elements, which would be a failure\nto complete the required operation.\n<\/p>\n

\nBonus chatter<\/b>:\nMind you, you can do better than\nO<\/i>(n<\/i>²) if you change the rules of the problem.\nFor example, if you allow pretending<\/i> to move the elements,\nsay by overloading the []<\/code> operator,\nthen you can perform the rotation in\nO<\/i>(1) time by just writing a wrapper:\n<\/p>\n

\nstruct IArray\n{\n  virtual int& Element(int x, int y) = 0;\n  virtual ~IArray() = 0;\n};\nclass RotatedArray : public IArray {\npublic:\n RotatedArray(IArray *p) : m_p(p) { }\n ~RotatedArray() { delete m_p; }\n int& Element(int x, int y) {\n  return m_p->Element(y, x);\n }\nprivate:\n IArray *m_p;\n};\nvoid RotateInPlace(IArray *& p, int N)\n{\n p = new RotatedArray(p);\n}\n<\/pre>\n
\nThis pseudo-rotates the elements by changing the accessor.\nCute but doesn’t actually address the original problem,\nwhich said that you were passed an array, not an interface\nthat simulates an array.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[26],"class_list":["post-15383","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-other"],"acf":[],"blog_post_summary":"
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 […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/15383","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=15383"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/15383\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=15383"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=15383"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=15383"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}