Является ли добавление элемента быстрее, чем замена в Python?
Я получил свою первую задачу по коду leet, которая заключалась в создании функции последовательности Фибоначчи. Это было мое представление ниже. Как некоторые из вас могут заметить, я пришел из MATLAB, и я думаю, что они всегда сначала определяют матрицу.
Я посмотрел на другие решения после решения этой проблемы и заметил, что большая часть быстрого решения пошла на добавление. Мой не был медленным, но мне было любопытно. Как следует из моего заголовка, более эффективно ли добавлять в Python?
class Solution(object):
def runningSum(self, nums):
newnums=nums[0:]
for i in range(len(nums)):
newnums[i]=sum(nums[:i+1])
return(newnums)
Ответы 1
Для длинного списка, длина которого известна заранее, должно быть несколько выгодно сначала создать список (как вы это делаете), потому что повторное добавление будет время от времени изменять размер и копировать базовый массив. Что делает ваш подход квадратичным, так это повторное суммирование всего префикса списка, когда у вас есть предыдущая сумма, легко доступная в предыдущей ячейке вашего результата:
class Solution:
def runningSum(self, nums):
newnums = nums[:] # shallow copy
for i in range(1, len(nums)):
newnums[i] += newnums[i-1] # just add prev cell
return newnums
Кроме того, Leetcode обычно довольно либерально относится к изменению своих входных данных. Они не проверяют, мутируете ли вы их, так что даже проще
class Solution:
def runningSum(self, nums):
for i in range(1, len(nums)):
nums[i] += nums[i-1] # just add prev cell
return nums
работает. Оба линейны по временной сложности, но вы экономите усилия на создании нового списка. И как только вы разберетесь со спецификой Leetcode, вы сможете воспользоваться тем фактом, что они импортировали все itertools, в частности, accumulate здесь пригодится:
class Solution:
def runningSum(self, nums):
return [*accumulate(nums)]
Или, как умно предложили в комментариях:
class Solution:
runningSum = accumulate
который работает только при выборе Python3 в качестве интерпретатора, и в этом случае вы как бы нарушаете аннотацию типа, поскольку это возвращает ленивый итератор, и его принятие сильно зависит от реализации тестов.
Сомневаюсь в первом предложении. Изменение размера происходит редко и очень быстро, очень низкоуровневая работа. Я подозреваю, что это незначительно, и это больше о том, является ли вызов метода добавления медленнее или быстрее, чем работа с индексами. Я подозреваю, что это быстрее, но придется измерить.
Поскольку вы говорите об использовании специфики LeetCode... Это также принимается: class Solution: runningSum = accumulate
Я знаю, но это больно, потому что тогда вы действительно нарушаете возвращаемый тип с аннотацией типа =)
append-solution выглядит примерно в в два раза быстрее.
Это не Фибоначчи.