Эффективная реализация очереди - временная сложность постановки и снятия с очереди

Question

Я сейчас читаю учебник по структурам данных / алгоритмам. Одним из упражнений является создание эффективной очереди с использованием структуры списка Python: временная сложность как очереди, так и очереди должна быть в среднем O (1). В книге говорится, что временная сложность должна составлять только O (n) для конкретного случая исключения, а в остальное время она должна быть O (1). Я реализовал это так, что задняя часть очереди является концом списка, а передняя часть очереди является началом списка; Когда я удаляю элемент из очереди, я не удаляю его из списка, а просто увеличиваю счетчик, чтобы метод узнал, какой элемент в списке представляет начало очереди. Вот мой код:

class FasterQueue:
    def __init__(self):
        self.items = []
        self.index = 0
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        index = self.index
        self.index += 1
        return self.items[index]
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)

Мой вопрос: в книге сказано, что в некоторых случаях для удаления из очереди необходимо принять O (1). Я понятия не имею, в каком случае это происходит, потому что кажется, что dequeue всегда будет просто получать значение по определенному индексу. Моя реализация очереди недействительна или я что-то упустил? Или учебник просто ищет другую более распространенную реализацию?

Большое спасибо за помощь.

Answer 1

O (n) является необходимым следствием управления длиной списка.

Вот решение.В общем, это работает как O (1), и время от времени это O (n) в результате дополнительного шага, который происходит внутри метода dequeue.

Шаг O (n) происходит, когда список становится слишком большим и запускает очистку.Обратите внимание, что в общем случае это должно быть сделано именно внутри метода dequeue.Выполнение этого снаружи будет иметь тенденцию быть более сложным и менее эффективным.

class FasterQueue:
    def __init__(self, maxwaste=100):
        self.items = []
        self.nout = 0
        self.maxwaste = maxwaste
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        if len(self.items):
            retv = self.items[self.nout]
            self.nout += 1
            if self.nout >= self.maxwaste:
                self.items = self.items[self.nout:]
                self.nout =0
            return retv
        else:
            print( 'empty' )
            raise ValueError
    def listQ(self):
        return ' '.join( self.items[self.nout:] )
    def isEmpty(self):
        return self.nout == len(self.items)
    def size(self):
        return len(self.items) - self.nout

q = FasterQueue(5)

for n in range(10):
    q.enqueue( str(n) )

print( 'queue size %d  nout %d items %s'%(q.size(),q.nout,q.listQ()) )
print( q.items )

while True:
    try:
        print( 'dequeue %s'%q.dequeue() )
        print( 'queue size %d  nout %d items %s'%(q.size(),q.nout,q.listQ()) )
        print( q.items )
    except:
        print( 'empty' )
        break

Запуск приведенного выше кода приводит к следующему выводу, обратите внимание на восстановление потраченной памяти при превышении maxwaste.Maxwaste установлен здесь небольшим с целью демонстрации операции.

queue size 10  nout 0 items 0 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 0
queue size 9  nout 1 items 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 1
queue size 8  nout 2 items 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 2
queue size 7  nout 3 items 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 3
queue size 6  nout 4 items 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 4
queue size 5  nout 0 items 5 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 5
queue size 4  nout 1 items 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 6
queue size 3  nout 2 items 7 8 9
['5', '6', '7', '8', '9']
dequeue 7
queue size 2  nout 3 items 8 9
['5', '6', '7', '8', '9']
dequeue 8
queue size 1  nout 4 items 9
['5', '6', '7', '8', '9']
dequeue 9
queue size 0  nout 0 items 
[]
empty
empty

Answer 2

Насколько я понимаю, enqueue должен вставляться в конце, а dequeue должен удаляться с самого начала.Таким образом, код должен быть

class FasterQueue:
def __init__(self):
    self.items = []

def enqueue(self, item):
    self.items.append(item)

def dequeue(self):
    if self.items:
        return self.items.pop(0)
    print("Underflow")

def isEmpty(self):
    return self.items == []

def size(self):
    return len(self.items)

Answer 3

Для полноты приведем ответ с использованием кольцевого буфера.

Этот пример работает как O (1) навсегда, но он делает это, ограничивая размер очереди. Если вы хотите, чтобы очередь росла или динамически увеличивалась, то у вас снова есть поведение O (n).

Другими словами, у вас есть O (1), только если вы каким-то образом не управляете размером списка. В этом суть вопроса.

Хорошо, вот реализация кольцевого буфера с фиксированной длиной очереди.

class FasterQueue:
    def __init__(self, nsize=100):
        self.items = [0]*nsize
        self.nin = 0
        self.nout = 0
        self.nsize = nsize
    def enqueue(self, item):
        next = (self.nin+1)%self.nsize
        if next != self.nout:
            self.items[self.nin] = item
            self.nin = next
            print self.nin, item
        else:
            raise ValueError
    def dequeue(self):
        if self.nout != self.nin:
            retv = self.items[self.nout]
            self.nout = (self.nout+1)%self.nsize
            return retv
        else:
            raise ValueError

    def printQ(self):
        if self.nout < self.nin:
            print( ' '.join(self.items[self.nout:self.nin]) )
        elif self.nout > self.nin:
            print( ' '.join(self.items[self.nout:]+self.items[:self.nin]) )

    def isEmpty(self):
        return self.nin == self.nout
    def size(self):
        return (self.nin - self.nout + self.nsize)%self.nsize

q = FasterQueue()

q.enqueue( 'a' )
q.enqueue( 'b' )
q.enqueue( 'c' )

print( 'queue items' )
q.printQ()
print( 'size %d'%q.size() )


while True:
    try:
        print( 'dequeue %s'%q.dequeue() )
        print( 'queue items' )
        q.printQ()
    except:
        print( 'empty' )
        break

Answer 4

делая это, используя еще некоторые функции Python-esque, я бы сделал что-то вроде:

class FasterQueue:
    def __init__(self):
        self.items = []
        self.index = 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        # do this first so IndexErrors don't cause us ignore items
        obj = self.items[self.index]
        # release the reference so we don't "leak" memory
        self.items[self.index] = None
        self.index += 1
        return obj

    def isEmpty(self):
        return self.index == len(self.items)

    def size(self):
        return len(self.items)

    def try_shrink(self):
        nactive = len(self.items) - self.index
        if nactive + 2 < self.index // 2:
            self.items = self.items[self.index:]
            self.index = 0

добавил метод try_shrink, который пытается освободить используемое пространство памяти, и может быть полезно вызвать его в конце dequeue() - в противном случае список будет расти произвольно долго и тратить большое количество памяти. константы там не удивительны, но должны предотвращать их слишком частое сокращение. эта операция будет O (n) и может быть то, что упоминалось