时间戳

首页 > 解决方案 > 提高数组操作的性能

python - 提高数组操作的性能

问题描述

我正在尝试解决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 字节？

标签： pythonarraysperformanceoptimization

解决方案

两个潜在的加速（未经测试）：

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. 查找特定替换比遍历整个列表更快。

推荐阅读