Circular Array Rotation

Question

My code works fine, but it's takes too much time, say around 65 seconds, for large input data. If there are 50,000 numbers in the list \$a\$ and we have to rotate the numbers 45,000 times then it takes 1 minute.

How can I reduce the time it takes to print all the numbers?

Problem: perform an operation called a right circular rotation on an array of integers [a0 , a1 , a2 , ..a(n-1)]. After performing one right circular rotation operation, the array is transformed to [a(n-1) , a0 , a1 ,..a(n-2)].

Input Format

• The first line contains 3 space-separated integers, \$n\$, \$k\$ and \$q\$ respectively.
• The second line contains \$n\$ space-separated integers, where each integer \$i\$ describes array element a[i] (where \$0 \le i<n\$).
• Each of the \$q\$ subsequent lines contains a single integer denoting \$m\$.

n,k,q = input().strip().split(' ') #n=no of integers in the list , k=no of rotation ,q=no of lines for integer m

n,k,q = [int(n),int(k),int(q)] 
a = [int(a_temp) for a_temp in input().strip().split(' ')]

for i in range(0,k):   
    a=[a.pop(n-1)]+a  #for putting the last element to the first position and del it from the last pos

for a0 in range(q):    # printing value of a at a given index
  m = int(input().strip())           
  print(a[m])

Sample Input

3 2 3
1 2 3
0
1
2

Sample Output

2
3
1

Explanation

• After the first rotation, the array becomes [3, 1, 2].
• After the second (and final) rotation, the array becomes [2, 3, 1].
• Let's refer to the array's final state as array \$b\$. For each query, we just have to print the value of b[m] on a new line:
• \$m=0\$, so we print \$2\$ on a new line.
• \$m=1\$, so we print \$3\$ on a new line.
• \$m=2\$, so we print \$1\$ on a new line.

Answer 1

1. You can change your array packing to use map instead.

   n, k, q = map(int, input().strip().split(' '))
   

2. When popping the last element you don't need to pass an argument.

3. Rather than popping each element, you can perform two slices and an addition. You would also have to use the modulo operator, %, for when \$k \ge n\$.

   k %= n
   a = a[-k:] + a[:-k]
   

4. You don't need to strip a number, as int will do this for you.

This can get you:

n, k, q = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
a = a[-k:] + a[:-k]
for _ in range(q):
    print(a[int(input()])

If you however want some sugar you can use collections.deque, it comes with deque.rotate that can perform the rotation in (3) for you. which can result in:

from collections import deque

n, k, q = map(int, input().strip().split(' '))
a = deque(map(int, input().strip().split(' ')))
a.rotate(k)
for _ in range(q):
    print(a[int(input()])

The above is good enough for the hackerrank challenge, however performs worse than the code above it. Rotating the array is \$O(n)\$, where the deque is \$O(k)\$. But indexing the array is \$O(1)\$, where the deque is \$O(n)\$. This means the first code block is \$O(n + q)\$ and the second is \$O(k + nq)\$. To make the second \$O(n + q)\$ all you need to do is change it to an array before the for loop, via list.

---

whenever you profile code, you should always take more than one timing, with more than one input. Hai Vu done neither of these. Using my wrapper to timeit, I wrote some code to profile; deque (Peilonrayz), adding slices (mkrieger), and deleting a slice (Hai Vu), as these are the fastest functions. However to keep things unbiased I've made a couple of adjustments:

• All code will be a Python function in __main__.
• All functions work correctly with any \$k\$ and when \$n \ne 0\$. (I use % to do this.)
• I run each function 10000 times per timeit.
• I run each timeit 10 times, and take the average and interquartile range.

This should give each and every function call the same amount of overhead. Here is the code that I use to time the functions.

from collections import deque

from graphtimer import time, GraphTimer, flat, time
import matplotlib.pyplot as plt

def mkrieger(a, k):
    k %= len(a)
    return a[-k:] + a[:-k]

def peilonrayz(a, k):
    a = deque(a)
    a.rotate(k)
    return a

def hai_vu(a, k):
    k %= len(a)
    b = a[-k:]
    del a[-k:]
    a[0:0] = b

class Timer(GraphTimer):
    functions = [
        'mkrieger',
        'peilonrayz',
        'hai_vu',
    ]
    inputs = [
        'a = list(range(100)); k = {}'
    ]
    domain = range(1, 101, 1)
    titles = [
        '100'
    ]

if __name__ == '__main__':
    fig, axs = plt.subplots(nrows=1, ncols=1, sharex=True)
    Timer(amount=10, number=10000, stmt='fn(a, k)').plot_axes(flat(axs), show_titles=True)
    plt.show()

Which outputs:

Answer 2

Instead of rotating the list \$k\$ times by one position, rotate it by \$k\$ positions in a single step.

In Python, this can be done by simple slice operations:

def rotate(a, k):
    """Rotate a by k positions to the right.

    >>> rotate([1, 2, 3], 1)
    [3, 1, 2]
    >>> rotate([0, 1, 2, 3, 4], -2)
    [2, 3, 4, 0, 1]
    """
    r = k % len(a)
    return a[-r:] + a[:-r]

• a[-r:] are the last r items of a.
• a[:-r] are all but the last r items of a.

Note that by taking \$k\$ modulo the length of a, values of \$k\$ outside the range \$0, \dots, n-1\$ will also work.

Answer 3

My first attempt is to do a loop k times, each time rotate one element of the list in place:

for _ in range(k):
    a.insert(0, a.pop()]

This turns out to be slightly better than the original poster (OP) Kriti Sahu's solution (we will see timing numbers later). However, my solution was far worse than other answers here.

Next up, I moved the last k elements to the beginning of the list in place (none of my solution creates a new array, all done in place--the key to performance):

b = a[-k:]  # Save off the last k elements
del a[-k:]  # Delete the last k elements
a[0:0] = b  # Insert to the front

This turns out to be the best timing so far. Here is a little script I wrote to compare solutions I see so far:

import timeit

def time_and_report(expression, setup, header):
    print '{}: {}'.format(header, expression)
    timing = timeit.timeit(stmt=expression, setup=setup)
    print '{} second(s)\n'.format(timing)

#
# Setup
#
array_size = 100
number_of_rotations = 10
setup = 'a=range({array_size}); k={number_of_rotations}'.format(**locals())
deque_setup = 'from collections import deque;' + setup
mkrieger1_setup = """
def rotate(a, k):
    r = k % len(a);
    return a[-r:] + a[:-r]
""" + setup

#
# Compare timings
#
time_and_report('for _ in range(k): a.insert(0, a.pop())', setup, 'Hai 1')
time_and_report('b = a[-k:]; del a[-k:]; a[0:0] = b', setup, 'Hai 2')
time_and_report('a = a[-k:] + a[:-k]', setup, 'Peilonrayz 1')
time_and_report('a = deque(a); a.rotate(k)', deque_setup, 'Peilonrayz 2')
time_and_report('a = rotate(a, k)', mkrieger1_setup, 'mkrieger1')
time_and_report('a = [a[(i+k) % len(a)] for i in range(0, len(a))]', setup, 'Andi Kleve')
time_and_report('for _ in range(k): a=[a.pop()]+a', setup, 'Original')

And here is the output of my timing tests for array of 100 elements:

Hai 1: for _ in range(k): a.insert(0, a.pop())
6.80668497086 second(s)

Hai 2: b = a[-k:]; del a[-k:]; a[0:0] = b
0.700757980347 second(s)

Peilonrayz 1: a = a[-k:] + a[:-k]
1.20484399796 second(s)

Peilonrayz 2: a = deque(a); a.rotate(k)
1.6975209713 second(s)

mkrieger1: a = rotate(a, k)
1.62001395226 second(s)

Andi Kleve: a = [a[(i+k) % len(a)] for i in range(0, len(a))]
39.2207920551 second(s)

Original: for _ in range(k): a=[a.pop()]+a
8.81602191925 second(s)

A Few Notes

• The deque solution turns out to be worse than the list solution because the overhead of turning a list into a deque
• When performance is important, operate the list in place will be faster than creating a new list
• Andi Kleve's solution it much worse than that of the OP

Answer 4

Don't rotate the array by copying - that is costly. Simply modify how you access the elements: the result of the N-th rotation can be output as follows (here N=2 as example):

a = range(0,5)
N = 2
[a[(i+N) % len(a)] for i in range(0, len(a))]

Answer 5

Put the elements in the shifted position directly removing the need to shift completely:

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int n; 
    int k; 
    int q; 
    scanf("%d %d %d",&n,&k,&q);
    int *a = malloc(sizeof(int) * n);
    for(int a_i = 0; a_i < n; a_i++){

        int la=floor((k+a_i)/n); 

       int j=a_i+k-la*n;
               scanf("%d",&a[j]);          
    }
    for(int a0 = 0; a0 < q; a0++){
        int m; 
        scanf("%d",&m);
       printf("%d\n",a[m]);
    }
    return 0;
}