CODEWITHSUNDEEP
pythonalgorithmperformancebig-o
gaurav
gaurav

Reputation: 443

Performance Improvement Basics in Python

So this is an algorithms question I was working out on HackerRank. It passes all the test cases except one because it times out.

I tried making a couple of improvements but it still keeps timing out. I want to understand how you can look at your own code and find places where it is slow.

Please note that I am not looking at alternative logics to solve the problem. This is the solution that came to my mind and I want to try and quicken it.

The question is as follows:

Problem Statement

Given a list of N integers, your task is to select K integers from the list such that its unfairness is minimized.

If (x1,x2,x3,…,xk) are K numbers selected from the list N, the unfairness is defined as

max(x1,x2,…,xk)−min(x1,x2,…,xk) where max denotes the largest integer among the elements of K, and min denotes the smallest integer among the elements of K.

Input Format

The first line contains an integer N. The second line contains an integer K. N lines follow. Each line contains an integer that belongs to the list N.

Link to the problem: https://www.hackerrank.com/challenges/angry-children/copy-from/11910253

First attempt:

n, k = int(input()), int(input())
num = sorted([ int(input()) for i in range(0,n) ])
lower, min_unfairness, upper = 0, 0, k

while upper <= len(num):
    current    = num[lower:upper]
    unfairness = current[-1] - current[0]
    if lower == 0: 
        min_unfairness = unfairness
    else: 
        if unfairness < min_unfairness:
            min_unfairness = unfairness 

    if min_unfairness == 0:
        break

    lower += 1
    upper += 1

print (min_unfairness)

Second Attempt: Improved further by removing the check for lower == 0 from the loop since that happens only in the first iteration.

n, k = int(input()), int(input())
num = sorted([ int(input()) for i in range(0,n) ])
lower, min_unfairness, upper = 0, 0, k

#Finding the unfairness of the 1st set and assigning it as min
current    = num[lower:upper]
unfairness = current[-1] - current[0]
min_unfairness = unfairness
lower += 1
upper += 1

while upper <= len(num) and min_unfairness != 0:

    #Finding unfairness of current set
    current    = num[lower:upper]
    unfairness = current[-1] - current[0]

    #Set it as min if it is lower than current minimum
    if unfairness < min_unfairness:
        min_unfairness = unfairness 

    lower += 1
    upper += 1

print (min_unfairness)

I am not sure what approach I should take whilte trying to analyse this problem. Any suggestions are welcome.

Upvotes: 4

Views: 249

Answers (2)

gaurav
gaurav

Reputation: 443

With Kolmar and Steven's help, I wrote the following piece:

n, k = int(input()), int(input())
num = sorted([ int(input()) for i in range(0,n) ])
min_unfairness = min( max_value - min_value for min_value, max_value in    zip(num, num[k-1:]) )
print(min_unfairness)

Posting it as an answer here, so that if anyone wants to have a quick look at the answer, they can see this :)

Upvotes: 2

Kolmar
Kolmar

Reputation: 14224

The slowest thing you do is copying a part of the list: current = num[lower:upper]. This brings the complexity of this step up from O(n) to O(n•k).

What you really should do is just take the elements, which define the unfairness of this sublist directly by their indexes:

min_unfairness = min(num[i+k-1] - num[i] for i in range(n-k+1))

Clarification: When the index of the first element of some selection is i, the largest element has index i+k-1, so the unfairness of this selection is equal to num[i+k-1] - num[i]. The code (num[i+k-1] - num[i] for i in range(n-k+1)) gives the iterator over unfairnesses of the relevant selections. So min(num[i+k-1] - num[i] for i in range(n-k+1)) finds the smallest unfairness in this iterator.

Upvotes: 2

Related Questions