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