Array rotation revisited
In the March of 2001 issue I wrote up an article about exchanging array segments, aka rotating an array. It turns out that the analysis there was not quite as acute as it might have. I (and apparently most other analysts) overlooked a key detail. The following is a reanalysis.
Statement of the problem:
Suppose we have an array A containing n equi-spaced elements. The object is to rotate the elements of A by k locations for some k, 0 < k < n. We can express this by
A[i] <- A[i+k], i < n-k <- A[i+k-n], i >= n-kAn alternative way to express it is to represent A as the concatenation of two arrays P and Q of lengths k and n-k respectively. Then we have
A = PQ rotate(A) = QPThere are three major approaches to effecting rotation that I know of; these are:
(1) Move one of the components into a scratch array, move the other component into its final position, and then move the component in the scratch array into its final position.
The cost of this method (excluding loop costs) is:
Data moves: n + min(k, n-k) Aux storage: min(k, n-k)The catch in assessing costs is that the method lends itself to bulk data moves (via hardware instructions or loop unrolling) so that data move costs are not comparable with those of other methods. Likewise the logic costs are not comparable except for naive implementations.
In short, it should be by far the fastest method of the three, but it does require a substantial amount of auxiliary storage.
(2) Reverse each component separately and then reverse the entire array. Let r() be the reversal function. Then we have
QP = r(r(P)r(Q))Calculating the costs of this method is straightforward. The reversal of an array of length n requires n/2 swaps. Each swap requires 3 data moves. Ergo, the number of data moves is 3n/2. Each element gets swapped twice, so the total number of data moves is 3n. The number of loop tests is n/2u where u is the loop unrolling factor.
(3) Treat the rotation as a permutation of the array, and execute each permutation cycle separately. This is the most complicated of the three, potentially requires the fewest operations, and has the most varied implementations.
Let d be the greatest common denominator of n and k. Then the permutation that carries A into rotate(A) has d cycles. For example, suppose that n=14 and k=6, so that d=gcd(14,6)=2. Then the permutation cycles are:
(0, 6, 12, 4, 10, 2, 8) (1, 7, 13, 5, 11, 3, 9)Each cycle is of length n/d (7 in this case). A cycle consists of runs of indices increasing by k. Thus in our example, the runs in the first cycle are
(0, 6, 12), (4, 10), and (2,8).When the cycle begins at the beginning of a run the length of a run is either ldiv(n,k) or udiv(n,k) where ldiv is integer division rounded down and udiv is integer division rounded up. In our example the lengths are ldiv(14,6)=2 and udiv(14,6)=3. If, however, we start the cycle in the middle or end of a run that run will be broken, e.g.,
(8, 0, 6, 12, 4, 10, 2)has two runs of length one, one run of length of two, and one run of length three.
When k > n/2 the long runs are descending runs. For example, suppose n=14, k=10. There are two cycles,
(13, 9, 5, 1, 11, 7, 3) (12, 8, 4, 0, 10, 6, 2)In this example there are descending runs of lengths ldiv(n,n-k)=ldiv(14,4)=3, and udiv(14,4)=3. In many implementations it is convenient to divide the algorithm into two cases, k < n/2, and k > n/2. In the latter case we replace k by n-k and change the direction of rotation.
There are two special cases, k=0, and k=n/2. If k=0 there is nothing to do. If k=n/2 we can swap the first and last halves. The swap requires 3n/2 data moves and n/2 loop tests; this cannot be improved upon. The cases are:
k = 0 Do nothing 0 < k < n/2 Increment = k, ascending runs k = n/2 Swap first and last halves n/2 < k < n Decrement = n-k, descending runsI will use the term “small slide” for a data move that is less than n/2 locations, and the term “big slide” for a data move that is greater than n/2,
When the runs are ascending big slides occur when the array index is in the last k elements; similarly, when runs are descending big slides occur when the array index is in the first k elements. In either case the total number of big slides is k. It follows that the number of big slides in a cycle is k/d; likewise the number of runs within a cycle is also k/d.
When effecting the rotation of a cycle the last big slide is not executed. Instead the saved initial value is used. In other words the sequence of events is:
An initial value is saved. A loop consisting of k/d runs of small slides alternates with k/d-1 big slides. Array[final index] is filled with the saved value.There are two things to settle in translating the above into code. The first is how to terminate the loop. The simplest way is to determine the final index in advance (it will be the starting index + n – k) and exit when the final index is reached.
The second is how to handle the alternation of small slide runs and big slides. One way is to use a simple loop with a test to determine if the current move is a big slide or a small slide. An example of this method is:
index = first last = first + n - k save = A[first] while (index .ne. last) begin next = index + k if (next .ge. n) next = next - k A[index] = A[next] index = next end A[last] = saveThe costs of this code for a single cycle of length n/d are:
Data moves: n/d + 1 loop tests: n/d if tests: n/d - 1The costs for processing the entire rotation (including a loop over d) are:
Data moves: n + d Tests 2nThe above code performs two tests per element, a loop test and a test to see whether the move is a big slide or a small slide.
Most implementations (including my March 2001 article) use some variant of the above loop. All are less efficient than they need be.We can reduce the number of tests per element by putting in an inner loop for the small slide runs. A naive (and slightly erroneous) implementation for ascending runs (k .lt. n/2)looks like this:
nk = n - k index = first last = first + nk save = A[first] while (index .ne. last) begin while (index .lt. nk) begin A[index] = A[index + k] index = index + k end A[index] = A[index - nk] index = index - nk end A[last] = saveThis code is wrong because the actual loop is a “loop and a half”. That is, the final big slide should not be made. Because it is being made, the loop termination test is also wrong. We can fix this is either of two ways. The first is to move a copy of the small slide loop outside the cycle loop. The second is to move the termination test to the middle of the cycle loop. The code for the second alternative looks like this:
nk = n - k index = first last = first + nk save = A[first] loop begin while (index .lt. nk) begin A[index] = A[index + k] index = index + k end if (index .eq. last) exitloop A[index] = A[index - nk] index = index - nk end A[last] = saveThe inner loop will be executed (n-k)/d times; costs for the loop are
Data moves: (n-k)/d Loop tests n/dThe loop termination test will be executed k/d times and the big slide will be executed k/d -1 times. The total costs for this code are:
Data moves: n + d Loop tests: n + k + dThe number of loop tests can be reduced by k by using an “until” loop instead of a “while” loop. This eliminates one loop test for each small slide loop.
A similar economy can be employed in the outer loop over the number of cycles. If for some reason it is desirable to avoid computing the gcd, we can count the number of small slide loops executed; when the last cycle is completed this number will be k. Thus our code for ascending runs can look like this:
nk = n - k first = 0 count = 0 until (count .ge. k) begin last = first + nk index = first save = A[first] loop begin count += 1 until (index .ge. nk) begin A[index] = A[index + k] index += k end if (index .eq. last) exitloop A[index] = A[index - nk] index -= nk end A[last] = save first += 1 endThe analogous code for descending runs is:
nk = n - k first = n - 1 count = 0 until (count .ge. nk) begin last = first - k index = first save = A[first] loop begin count += 1 until (index .lt. nk) begin A[index] = A[index - nk] index -= nk end if (index .eq. last) exitloop A[index] = A[index + k] index += k end A[last] = save first -= 1 endThis code clearly is the most economical method for rotating an array in terms of operations used since it uses n+d data moves and loop tests.
This page was last updated April 9, 2009.