0

У меня есть код, хотел бы узнать, как можно его ускорить, упростить(сделать красивее :)), сделать так, чтобы он кушал меньше памяти и вообще, возможно ли это сделать?

На данный момент у меня такие результаты: Время - 91 мс | Память - 3.98Mb | Python 3.7.3


Гоша реализовал структуру данных Дек, максимальный размер которого определяется заданным числом. Методы push_back(x), push_front(x), pop_back(), pop_front() работали корректно. Но, если в деке было много элементов, программа работала очень долго. Дело в том, что не все операции выполнялись за O(1). Помогите Гоше! Напишите эффективную реализацию. Внимание: при реализации нельзя использовать связный список.


Формат ввода

В первой строке записано количество команд n — целое число, не превосходящее 5000. Во второй строке записано число m — максимальный размер дека. Он не превосходит 1000. В следующих n строках записана одна из команд:

push_back(value) – добавить элемент в конец дека. Если в деке уже находится максимальное число элементов, вывести «error».

push_front(value) – добавить элемент в начало дека. Если в деке уже находится максимальное число элементов, вывести «error».

pop_front() – вывести первый элемент дека и удалить его. Если дек был пуст, то вывести «error».

pop_back() – вывести последний элемент дека и удалить его. Если дек был пуст, то вывести «error».

Value — целое число, по модулю не превосходящее 1000. Формат вывода

Выведите результат выполнения каждой команды на отдельной строке. Для успешных запросов push_back(x) и push_front(x) ничего выводить не надо.


Формат вывода

Выведите результат выполнения каждой команды на отдельной строке. Для успешных запросов push_back(x) и push_front(x) ничего выводить не надо.


Пример 1:

Ввод:

4
4
push_front 861
push_front -819
pop_back
pop_back

Вывод:

861
-819

Пример 2:

Ввод:

7
10
push_front -855
push_front 720
pop_back
pop_back
push_back 844
pop_back
push_back 823

Вывод:

-855
720
844

Пример 3:

Ввод:

6
6
push_front -201
push_back 959
push_back 102
push_front 20
pop_front
pop_back

Вывод:

20
102

Мой код:

class Dek:
    def __init__(self, max_size: int):
        self._elements = [None] * max_size
        self._max_size = max_size
        self._head = 0
        self._tail = 0
        self._size = 0

    def is_empty(self):
        return self._size == 0

    def push_back(self, value: int):
        if self._size != self._max_size:
            self._elements[self._tail] = value
            self._tail = (self._tail + 1) % self._max_size
            self._size += 1
        else:
            raise OverflowError

    def push_front(self, value: int):
        if self._size != self._max_size:
            self._elements[self._head - 1] = value
            self._head = (self._head - 1) % self._max_size
            self._size += 1
        else:
            raise OverflowError

    def pop_back(self):
        if self.is_empty():
            raise IndexError
        x = self._elements[self._tail - 1]
        self._elements[self._tail - 1] = None
        self._tail = (self._tail - 1) % self._max_size
        self._size -= 1
        return x

    def pop_front(self):
        if self.is_empty():
            raise IndexError
        x = self._elements[self._head]
        self._elements[self._head] = None
        self._head = (self._head + 1) % self._max_size
        self._size -= 1
        return x


def main():
    count_command = int(input())
    queue_size = int(input())

    queue = Dek(queue_size)
    commands = {
        'push_front': queue.push_front,
        'push_back': queue.push_back,
        'pop_front': queue.pop_front,
        'pop_back': queue.pop_back,
    }
    for i in range(count_command):
        command = input()
        operation, *value = command.split()
        if value:
            try:
                result = commands[operation](int(*value))
                if result is not None:
                    print(result)
            except OverflowError:
                print('error')
        else:
            try:
                result = commands[operation]()
                print(result)
            except IndexError:
                print('error')


if __name__ == '__main__':
    main()

1 ответ 1

2

Ваш код хорош. Он отвечает всем требованиям задачи, простых способов улучшить производительность или уменьшить требуемую память я не вижу. Его можно записать короче, но при этом он станет работать немного дольше. Функцию main можно записать проще, но задание касается в большей степени класса Dek. Посмотрите на вариант ниже, но, ещё раз повторюсь, он не лучше и не хуже вашего:

class Dek:
    def __init__(self, max_size):
        self._data = [None] * max_size
        self._front = max_size - 1
        self._back = 0
        self._size = 0

    def is_empty(self):
        return self._size == 0

    def push_back(self, value):
        self._back = self._push(self._back, 1, value)

    def pop_back(self):
        self._back, value = self._pop(self._back, 1)
        return value

    def push_front(self, value):
        self._front = self._push(self._front, -1, value)

    def pop_front(self):
        self._front, value = self._pop(self._front, -1)
        return value

    def _push(self, i, di, value):
        if self._size >= len(self._data):
            raise OverflowError
        self._data[i] = value
        self._size += 1
        return (i + di) % len(self._data)

    def _pop(self, i, di):
        if self._size <= 0:
            raise IndexError
        j = (i - di) % len(self._data)
        x = self._data[j]
        self._data[j] = None
        self._size -= 1
        return j, x
 

def main():
    count_command = int(input())
    queue_size = int(input())

    queue = Dek(queue_size)
    for _ in range(count_command):
        verb, *values = input().split()
        op = getattr(queue, verb)
        values = tuple(map(int, values))
        try:
            result = op(*values)
        except (IndexError, OverflowError):
            result = 'error'
        if result is not None:
            print(result)


if __name__ == '__main__':
    main()

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.