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?

row seems like a bad name for your 2d array. However, you can rotate in one line: rotate = zip(*row[::-1]) [Source](https://stackoverflow.com/questions/8421337/rotating-a-two-dimensional-array-in-python) — DarrylG, Dec 25 '19 at 13:34
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) — CrazyElf, Dec 25 '19 at 13:35
In check routine, you should break out of your double loops early if the condition is not satisfied. — DarrylG, Dec 25 '19 at 13:37

DarrylG · Accepted Answer · 2019-12-25T14:13:16.977

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)

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 — alibiineed, Dec 25 '19 at 14:01
@alibiineed--removed n = len(row). Forgot that zip(...) returns a iterator so has no length, but we can use the global n. — DarrylG, Dec 25 '19 at 14:05
@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). — DarrylG, Dec 25 '19 at 14:16

score 0 · Answer 2 · edited Dec 25 '19 at 17:00

0

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:

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

edited Dec 25 '19 at 17:00

amer

1,528
1
14
22

answered Dec 25 '19 at 13:52

naveen

23
1
5

score 0 · Answer 3 · answered Dec 25 '19 at 14:51

0

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)

answered Dec 25 '19 at 14:51

ksa

118
8

over here you rotate the matrix 90 degrees every time it doesn't satisfy your conditions – ksa Dec 25 '19 at 14:52

How to Optimize Python Programs

3 Answers3