Как можно улучшить код? Стек - задача на питоне
У меня есть код, хотел бы узнать, как можно его ускорить, упростить(сделать красивее :)), сделать так, чтобы он кушал меньше памяти и вообще, возможно ли это сделать?
На данный момент у меня такие результаты: Время - 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 шт):
Ваш код хорош. Он отвечает всем требованиям задачи, простых способов улучшить производительность или уменьшить требуемую память я не вижу. Его можно записать короче, но при этом он станет работать немного дольше. Функцию 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()