How to Optimize Python Programs

Question

I am trying to solve a contest question: https://dmoj.ca/problem/ccc18s2. Basically you're given an input where the first line gives you the number of lines the input is, then you're given a series of integers(max: 10^9). Sample Input:

3

4 3 1

6 5 2

9 7 3

Then the program has to rotate this grid until the first element of every column is less than the second element in every column and so on. Each row must also be in ascending order.

Sample Output:

1 2 3

3 5 7

4 6 9

import sys
n = int(sys.stdin.readline())
row=[]
appendtorow = row.append
for i in range(0,n):
 inputx = (sys.stdin.readline()).rstrip()
 inp = inputx.split(" ")
 appendtorow(inp)
def rotate(row):
 new =[]
 for i in range(0,n):
 temp=[]
 for j in range(0,n):
 temp.append(row[n-1-j][i])
 new.append(temp)
 return new
def printout():
 for i in range(0,n):
 for j in range(0,n):
 x=row[i]
 y=x[j]
 sys.stdout.write(y)
 sys.stdout.write(" ") 
 sys.stdout.write("\n")
def check(row):
 m=False
 g=False
 f=False
 for i in range(0,n):
 for j in range(0,n-1):
 if(row[n-1][i]>row[n-1-j][i]):
 m=True
 for i in range(0,n):
 for j in range(0,n-1):
 if(row[i][0]<row[i][j+1]):
 g=True
 if(g==True and m==True):
 f=True
 return f
flag=0
while(flag==0):
 g=check(row)
 if(g==True):
 printout()
 flag=1
 else:
 row = rotate(row)

I tried to increase it's speed with stdin, stdout and moving append out of loops as suggested by this guide: https://wiki.python.org/moin/PythonSpeed/PerformanceTips. But the program takes twice the time(2s) of the time limit(1s) and these don't seem to help.

How can I optimize this? Does calling functions increase the time a program takes to execute?

• DarrylG: row seems like a bad name for your 2d array. However, you can rotate in one line: rotate = zip(*row[::-1]) Source
• CrazyElf: 1) append to list is very slow, use arrays of constant size if you allowed to do so; 2) try shift and subtract lists and then check for all elements of new list (or better array again) is below/above zero instead of comparing every elements of two lists (one list with different indexes)
• DarrylG: In check routine, you should break out of your double loops early if the condition is not satisfied.

Answer 1

Think the following two mods should improve the performance of two routines (did not refactor name 'row' to keep as much of your original code--but this is a bad name).

rotate - simple one-liner that uses builtin function rather double for loops.

check - early termination of looping when rows or columns are not ascending.

import sys
def rotate(row):
 " Use builtin zip is much faster than double for loops "
 # From -- https://stackoverflow.com/questions/8421337/rotating-a-two-dimensional-array-in-python
 return list(zip(*row[::-1]))
def printout():
 for i in range(0,n):
 for j in range(0,n):
 x=row[i]
 y=x[j]
 sys.stdout.write(y)
 sys.stdout.write(" ") 
 sys.stdout.write("\n")
def check(row):
 " Early terminate when row or column not ascending "
 # Check each row and columns values are incresing
 # Done with single double for loop rather than two sets
 for i in range(1, n):
 for j in range(1, n):
 if not (row[i][j] > row[i][j-1] and row[i][j] > row[i-1][j]):
 # terminate, since not ascending along row or column
 return False
 return True
n = int(sys.stdin.readline())
row=[]
appendtorow = row.append
for i in range(0,n):
 inputx = (sys.stdin.readline()).rstrip()
 inp = inputx.split(" ")
 appendtorow(inp)
flag=0
while(flag==0):
 g=check(row)
 if(g==True):
 printout()
 flag=1
 else:
 row = rotate(row)

• alibiineed: I got this error: object of type 'zip' has no len() for line 24 and 35, n= len(row). And if I remove the line I get 'zip' object is not subscriptable
• DarrylG: @alibiineed--removed n = len(row). Forgot that zip(...) returns a iterator so has no length, but we can use the global n.
• DarrylG: @alibiineed--check latest code (another mod to rotate)
• DarrylG: @alibiineed--rearranged the order since in Python functions are normally placed before scripting code (i.e. the file I/O and calling of the functions you have).

Answer 2

import numpy as np
A = np.matrix('4 3 1; 6 5 2; 9 7 3')
check = True
m, n = A.shape
while(check):
 for i in range(m - 1):
 for j in range(n - 1):
 if A[i, j] <= A[i, j + 1] and A[i, j] <= A[i + 1, j]:
 check = check and False
 else:
 check = check and True
 if check == False:
 break;
 A = np.rot90(A)
print(A)

• ksa: over here you rotate the matrix 90 degrees every time it doesn't satisfy your conditions

Answer 3

First convert the input values in to matrix format and then arrange each row in ascending order and then find transpose of matrix.
For example:

1. x=torch.Tensor([4,3,1],[6,5,2],[9,7,3])
2. using torch.sort()
3. using torch.Transpose()