CODEWITHSUNDEEP
pythonmatrixtime-complexity
ailhahc
ailhahc

Reputation: 57

Python program for Rotating Matrix. Why is my program is taking so much time?

I wrote this program in Python 2.7 and it is showing a runtime error for some test cases and taking more than 10 seconds for some. I am new to coding and can't figure out why is it taking so much time.

This program is for rotating the elements of matrix counter-clockwise. 

Input
4 4 1

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Output
2 3 4 8 
1 7 11 12 
5 6 10 16 
9 13 14 15

First input is No of Rows(M), No of Columns(N), No of rotations(R). Then the elements of matrix are input line by line. The output shows the rotation. Smaller of M and N will always be even.

enter image description here

Here is my program:

def printAsNeeded(matrix):
    length = len(matrix)
    n = len(matrix[0])
    for i in range(length):
        a = str()
        for j in range(n):
            a = a+str(matrix[i][j])+' '
        print a

def rotate(matrix):
    count = 0
    M = len(matrix)
    N = len(matrix[0])
    rmatrix = []
    for i in range(M):
        rmatrix.append([])
        for j in range(N):
            rmatrix[i].append(0)
    if(M<N):
       mag = M/2
    else:
       mag = N/2
    #down: 
    for i in range(mag):
        for j in range(count, M - (count+1)):
            rmatrix[j+1][i] = matrix[j][i]
        count = count+1
    count = 0
    #up
    for i in range(N-1, mag-1, -1):
        for j in range(count, M - (count+1)):
            rmatrix[j][i] = matrix[j+1][i]
        count = count+1
    count = 0
    #right
    for i in range(M-1, mag-1, -1):
        for j in range(count, N - (count+1)):
            rmatrix[i][j+1] = matrix[i][j]
        count = count+1
    count = 0
    #left
    for i in range(mag):
        for j in range(count, N - (count+1)):
            rmatrix[i][j] = matrix[i][j+1]
        count = count+1
    count = 0


    return rmatrix


M, N, R = raw_input().split()
M = int(M) #No of rows
N = int(N) #No of columns
R = int (R) #No of rotations
omatrix = []

for i in range(M):
    omatrix.append([])
    data = raw_input().split()
    for j in range(len(data)):
        omatrix[i].append(int(data[j]))

def matrixRotation(matrix, n):
    for i in range(n):
        matrix = rotate(matrix)
    printAsNeeded(matrix)

matrixRotation(omatrix, R)

Upvotes: 1

Views: 165

Answers (1)

alexanderlukanin13
alexanderlukanin13

Reputation: 4715

For square matrix, your algorithm has O(M * M * R) complexity. It's easy to see:

def matrixRotation(matrix, n):
    for i in range(n):
        matrix = rotate(matrix)  # number of cycles = R

def rotate(matrix):
    mag = M/2
    count = 0
    for i in range(mag):  # number of cycles ~ M
        for j in range(count, M - (count+1)):  # number of cycles ~ M
            rmatrix[j+1][i] = matrix[j][i]
        count = count+1

So, total number of steps grows pretty fast, and for 1000x1000 matrix with 100 rotations you will have to do ~100M steps.

Inventing better algorithm is beyond the scope of this question (and in real life, you would be using NumPy anyway). But one obvious beginner's error I see is that you use range instead of xrange. It is grossly inefficient in this case, because you create a temporary list every time.

Upvotes: 1

Related Questions