Time Error на тесте для класса Buffer, который копит элементы и выводит сумму каждых пяти по мере их накопления

Question

Я сейчас прохожу задания на stepik. Вот ссылка на конкретное задание https://stepik.org/lesson/24461/step/9?discussion=611901&unit=6767

Реализуйте класс Buffer, который будет накапливать в себе элементы последовательности и выводить сумму пятерок последовательных элементов по мере их накопления.

Программу пишу, все работает на разных тестах... Сайт не принимает задание, пишет Time Error..Работает она вроде быстро, подскажите как что исправить?

class Buffer:
    def __init__(self):
         self.buff =[]

    def add(self, *a):

        for i in a:
            self.buff.append(i)
        while len(self.buff) >= 5:
            i = 0
            sum = 0
            while i != 5:
                sum += self.buff[0]
                self.buff.remove(self.buff[0])
                i += 1
            print(sum)

    # print(self.buff)
    def get_current_part(self):

        return self.buff


buf = Buffer()
buf.add(1, 2, 3,3,3,3,3,3,3,3,3,3,3,3)
print(buf.get_current_part())  # вернуть [1, 2, 3]
buf.add(4, 5, 6)  # print(15) – вывод суммы первой пятерки элементов
print(buf.get_current_part())
buf.add(7, 8, 9, 10)  # print(40) – вывод суммы второй пятерки элементов
print(buf.get_current_part())
buf.add(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)  # print(5), print(5) – вывод сумм третьей и четвертой пятерки
print(buf.get_current_part())  # вернуть [1]

Answer 1

Попробуйте:

class Buffer:
    def __init__(self):
        self._nums = []
def add(self, *a):
    part_size = 5

    # Добавить следующую часть последовательности
    self._nums += a

    while len(self._nums) >= part_size:
        # Сумма первой пятерки элементов
        print(sum(self._nums[:part_size]))

        # Удаление первой пятерки элементов
        self._nums = self._nums[part_size:]

def get_current_part(self):
    # Вернуть сохраненные в текущий момент элементы
    return self._nums

Answer 2

Ваш метод add() является квадратичным — O(len(a)**2): self.buff.remove(self.buff[0]) выполняется за O(len(self.buf)) время и при этом эта операция повторяется приблизительно len(self.buff) раз. У вас len(self.buf) приблизительно равен len(a), поэтому общее время пропорционально квадрату len(a). Подробнее, посмотрите в конце ответа объяснение, почему квадратичных решений лучше избегать, если ввод не ограничен.

Можно сделать add() операцию линейной — O(len(a)):

#!/usr/bin/env python3
from itertools import chain, zip_longest

class Buffer:
    def __init__(self):
        self.buff = []
        self.bufsize = 5

    def add(self, *a):
        # iterate bufsize items at a time
        for chunk in zip_longest(*[chain(self.buff, a)] * self.bufsize):
            if chunk[-1] is None:  # input is not divisible by bufsize
                break
            print(sum(chunk))
        else:  # all values are summed
            chunk = []
        self.buff[:] = (n for n in chunk if n is not None)  # keep unconsumed part

    def get_current_part(self):
        return self.buff

Здесь zip(*[iterator]*n) это идиома по обходу итератора по n элементов за раз.

Тест:

import io
import contextlib

def test_buf():
    with io.StringIO() as file, contextlib.redirect_stdout(file):
        buf = Buffer()
        assert file.getvalue() == ""
        buf.add(1, 2, 3)
        assert file.getvalue() == ""
        assert buf.get_current_part() == [1, 2, 3]
        buf.add(4, 5, 6)
        assert file.getvalue() == "15\n"
        assert buf.get_current_part() == [6]
        buf.add(7, 8, 9, 10)
        assert file.getvalue() == "15\n40\n"
        assert buf.get_current_part() == []
        buf.add(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
        assert file.getvalue() == "15\n40\n5\n5\n"
        assert buf.get_current_part() == [1]
        buf.add(0)
        assert file.getvalue() == "15\n40\n5\n5\n"
        assert buf.get_current_part() == [1, 0]