Improve the performance of array operations

user_11930602 0
Viewed 143

I am trying to solve this problem statement on codechef. The problem statement in a nutshell is: Find out the value(explanation coming up) of array with 'n' elements after updating the array each time, 'q' times.

value of the array means, sum of the absolute differences of consecutive elements of the array. e.g. 

array = [1,2,3,4,5]

value(array) = abs(1-2) + abs(2-3) + ... + abs(4-5)

I am learning python (3rd day into it) and am trying to solve the problem using the following python code.

def update(arr,find,replace):
    for i in range(len(arr)):
        if arr[i]==find:
            arr[i]=replace

def value(arr):
    sum = 0
    for i in range(len(arr)-1):
        sum = sum + abs(arr[i]-arr[i+1])
    return sum

test_case = int(input())
while test_case > 0 :
    n,q = map(int,input().split(" "))
    array = list(map(int,input().split()))
    for i in range(q):
        x,y = map(int,input().split(" "))
        update(array,x,y)
        print(value(array))
    test_case -= 1

This code, when I run on my machine is yielding correct results for custom test cases (even with large input) but on the site exceeds the time limit. Is there any way we can optimise the code to fit it into the given constraints...... time complexity : < 2secs and size : 50000bytes?

optimization arrays python performance
1 Answers

Two potential speedups (NOT tested):

def value(arr):
    return sum(abs(arr[i]-arr[i+1]) for i in range(len(arr)-1))

# in general, avoid using built-in names for variable names also...

And:

def update(arr,find,replace):
    for i in range(arr.count(find)):
       arr[arr.index(find)]=replace

# find the specific replacements and replace vs 
# iterating the entire list

In Python:

  1. Built-in functions are usually faster than what you would write yourself;
  2. Comprehensions are usually faster than a traditional for loop;
  3. Finding the specific replacement is faster than looping over an entire list.
user_2986070
Related