python - 提高数组操作的性能

Question

我正在尝试解决 this关于 codechef 的问题陈述.简而言之，问题陈述是:每次更新数组'q'次后，找出​​具有'n'个元素的数组的值(即将解释)。

数组的值表示数组连续元素的绝对差之和。例如

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

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

我正在学习 python(学习它的第 3 天)并尝试使用以下 python 代码解决问题。

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

这段代码，当我在我的机器上运行时，为自定义测试用例(即使有大量输入)产生了正确的结果，但在网站上超过了时间限制。有什么方法可以优化代码以适应给定的约束……时间复杂度:< 2 秒和大小:50000 字节？

Answer 1

两个潜在加速(未测试):

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...

和:

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

在 Python 中:

1. 内置函数通常比您自己编写的函数更快；
2. 理解通常比传统的for循环更快；
3. 找到特定的替换项比遍历整个列表更快。