W jaki sposób implementowane są deques w Pythonie i kiedy są gorsze niż listy?

85

Niedawno zacząłem badać, w jaki sposób różne struktury danych są implementowane w Pythonie, aby mój kod był bardziej wydajny. Badając, jak działają listy i deki, odkryłem, że mogę uzyskać korzyści, gdy chcę zmienić i cofnąć przesunięcie, skracając czas z O (n) na listach do O (1) w deques (listy są implementowane jako tablice o stałej długości, które mają do całkowitego skopiowania za każdym razem, gdy coś zostanie włożone z przodu, itp ...). To, czego nie potrafię znaleźć, to specyfika implementacji deque i specyfika jego wad w porównaniu z listami. Czy ktoś może mnie oświecić w tych dwóch pytaniach?

Eli
źródło

Odpowiedzi:

74

https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c

A dequeobjectskłada się z podwójnie połączonej listy blockwęzłów.

Więc tak, dequejest to lista (podwójnie) połączona, jak sugeruje inna odpowiedź.

Opracowanie: Oznacza to, że listy Pythona są znacznie lepsze w przypadku operacji o swobodnym dostępie i operacjach o stałej długości, w tym wycinania, podczas gdy deques są znacznie bardziej przydatne do wypychania i zdejmowania rzeczy z końców, z indeksowaniem (ale nie cięciem, co ciekawe) możliwe, ale wolniej niż w przypadku list.

UKŁUCIE
źródło
3
Zwróć uwagę, że jeśli potrzebujesz tylko dołączyć i wyskoczyć na jednym końcu (stosie), listy powinny działać lepiej jako .append()i .pop()są amortyzowane O (1) (ponowna alokacja i kopiowanie ma miejsce, ale bardzo rzadko i tylko do momentu osiągnięcia maksymalnego rozmiaru stosu kiedykolwiek mieć).
@delnan: Ale jeśli chcesz mieć kolejkę, coś takiego dequejest zdecydowanie właściwą drogą.
JAB
@delnan: Jak myślisz? .append () i .pop () są amortyzowane O (1) na listach, ale czy nie są faktycznymi O (1) na deques i kopie nigdy nie są potrzebne.
Eli
1
@Eli: Listy nie zajmują się bezpieczeństwem wątków (no cóż, nie jest to połączone z ich wewnętrznymi elementami) i przez długi czas były dostrajane przez wielu mądrych ludzi.
3
@delnan: Właściwie deques w CPythonie również nie obsługuje bezpieczeństwa wątków; oni po prostu korzystać z GIL podejmowaniu operacji atomowej (w rzeczywistości, appenda popod końca listma takie same zabezpieczenia). W praktyce, jeśli używasz tylko stosu, oba listi dequemają skutecznie identyczną wydajność w CPythonie; alokacje bloków są częstsze w przypadku deque(ale nie na zwykłych połączonych listach często; w efekcie przydzielanie / zwalnianie kończy się za każdym razem, gdy przekroczysz granicę 64 elementów w implementacji CPythona), ale kompensuje to brak ogromnych przerywanych kopii.
ShadowRanger
51

Sprawdź collections.deque. Z dokumentów:

Deques obsługują bezpieczne wątkowo, wydajne pamięciowo dołączanie i wyskakuje z obu stron deque z mniej więcej taką samą wydajnością O (1) w obu kierunkach.

Chociaż obiekty listy obsługują podobne operacje, są one zoptymalizowane pod kątem szybkich operacji o stałej długości i powodują O (n) koszty przesunięcia pamięci dla operacji pop (0) i insert (0, v), które zmieniają zarówno rozmiar, jak i położenie podstawowej reprezentacji danych .

Tak jak jest napisane, użycie pop (0) lub insert (0, v) pociąga za sobą duże kary w przypadku obiektów list. Nie możesz używać operacji plasterka / indeksu na a deque, ale możesz użyć popleft/ appendleft, które są operacjami dequezoptymalizowanymi dla. Oto prosty test porównawczy, który to pokazuje:

import time
from collections import deque

num = 100000

def append(c):
    for i in range(num):
        c.append(i)

def appendleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.appendleft(i)
    else:
        for i in range(num):
            c.insert(0, i)
def pop(c):
    for i in range(num):
        c.pop()

def popleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.popleft()
    else:
        for i in range(num):
            c.pop(0)

for container in [deque, list]:
    for operation in [append, appendleft, pop, popleft]:
        c = container(range(num))
        start = time.time()
        operation(c)
        elapsed = time.time() - start
        print "Completed %s/%s in %.2f seconds: %.1f ops/sec" % (container.__name__, operation.__name__, elapsed, num / elapsed)

Wyniki na moim komputerze:

Completed deque/append in 0.02 seconds: 5582877.2 ops/sec
Completed deque/appendleft in 0.02 seconds: 6406549.7 ops/sec
Completed deque/pop in 0.01 seconds: 7146417.7 ops/sec
Completed deque/popleft in 0.01 seconds: 7271174.0 ops/sec
Completed list/append in 0.01 seconds: 6761407.6 ops/sec
Completed list/appendleft in 16.55 seconds: 6042.7 ops/sec
Completed list/pop in 0.02 seconds: 4394057.9 ops/sec
Completed list/popleft in 3.23 seconds: 30983.3 ops/sec
zeekay
źródło
3
Huh, właśnie zauważyłem, że nie możesz wykonać cięcia za pomocą deques, mimo że możesz wykonać indeksowanie. Ciekawy.
JAB
1
+1 za czasy - ciekawe, że listdołączanie jest nieco szybsze niż dequedołączanie.
nadawca
1
@zeekay: To dość dziwne, biorąc pod uwagę, że wyszukiwanie indeksu określonego elementu i tak normalnie wymagałoby iteracji po elementach kolekcji, a indeksowanie można przeprowadzić dequetak samo, jak w przypadku list.
JAB,
1
@senderle: Oczywiście list pops były wolniejsze niż deque's (prawdopodobnie ze względu na listwyższy koszt sporadycznej zmiany rozmiaru, gdy się kurczy, gdzie dequejest po prostu zwalnianie bloków z powrotem do wolnej listy lub małej puli obiektów), więc wybierając strukturę danych dla stosu (aka kolejka LIFO), wydajność od pustego do pełnego do pustego wygląda nieco lepiej deque(średnio 6365 000 operacji na sekundę dla append/ pop, w porównaniu listz 5578 000 operacji na sekundę). Podejrzewam, dequeże w prawdziwym świecie poradziłby sobie nieco lepiej, ponieważ dequewolna lista oznacza, że ​​uprawa po raz pierwszy jest droższa niż uprawa po zmniejszeniu się.
ShadowRanger,
1
Aby wyjaśnić moją listę darmowych list: CPython dequenie będzie w rzeczywistości zawierał freedo 16 bloków (na szerokość modułu, nie na deque), zamiast tego umieszcza je w taniej tablicy dostępnych bloków do ponownego wykorzystania. Więc kiedy rośnie dequepo raz pierwszy, zawsze musi wyciągać nowe bloki z malloc(czyniąc appenddroższymi), ale jeśli stale się rozwija przez pewien czas, a następnie kurczy się trochę i tam iz powrotem, zwykle nie będzie obejmował malloc/ freew wszystko, o ile długość mieści się w przybliżeniu w zakresie 1024 elementów (16 bloków na liście wolnej, 64 szczeliny na blok).
ShadowRanger,
17

Podejrzewam, że wpis w dokumentacji dotyczącej dequeobiektów zawiera większość informacji, które musisz wiedzieć. Wybitne cytaty:

Deques obsługują bezpieczne wątkowo, wydajne pamięciowo dołączanie i wyskakuje z obu stron deque z mniej więcej taką samą wydajnością O (1) w obu kierunkach.

Ale...

Indeksowany dostęp to O (1) na obu końcach, ale spowalnia do O (n) w środku. Aby uzyskać szybki losowy dostęp, użyj zamiast tego list.

Musiałbym spojrzeć na źródło, aby stwierdzić, czy implementacja jest listą połączoną, czy czymś innym, ale wydaje mi się, że dequema z grubsza takie same cechy, jak lista podwójnie połączona.

nadawca
źródło
11

Oprócz wszystkich innych pomocnych odpowiedzi, tutaj jest więcej informacji porównujących złożoność czasową (Big-Oh) różnych operacji na listach Pythona, deques, zbiory i słowniki. Powinno to pomóc w wyborze właściwej struktury danych dla konkretnego problemu.

PythonJin
źródło
-3

Chociaż nie jestem do końca pewien, w jaki sposób Python to zaimplementował, tutaj napisałem implementację kolejek wykorzystującą tylko tablice. Ma taką samą złożoność jak kolejki Pythona.

class ArrayQueue:
""" Implements a queue data structure """

def __init__(self, capacity):
    """ Initialize the queue """

    self.data = [None] * capacity
    self.size = 0
    self.front = 0

def __len__(self):
    """ return the length of the queue """

    return self.size

def isEmpty(self):
    """ return True if the queue is Empty """

    return self.data == 0

def printQueue(self):
    """ Prints the queue """

    print self.data 

def first(self):
    """ Return the first element of the queue """

    if self.isEmpty():
        raise Empty("Queue is empty")
    else:
        return self.data[0]

def enqueue(self, e):
    """ Enqueues the element e in the queue """

    if self.size == len(self.data):
        self.resize(2 * len(self.data))
    avail = (self.front + self.size) % len(self.data) 
    self.data[avail] = e
    self.size += 1

def resize(self, num):
    """ Resize the queue """

    old = self.data
    self.data = [None] * num
    walk = self.front
    for k in range(self.size):
        self.data[k] = old[walk]
        walk = (1+walk)%len(old)
    self.front = 0

def dequeue(self):
    """ Removes and returns an element from the queue """

    if self.isEmpty():
        raise Empty("Queue is empty")
    answer = self.data[self.front]
    self.data[self.front] = None 
    self.front = (self.front + 1) % len(self.data)
    self.size -= 1
    return answer

class Empty(Exception):
""" Implements a new exception to be used when stacks are empty """

pass

Tutaj możesz to przetestować za pomocą jakiegoś kodu:

def main():
""" Tests the queue """ 

Q = ArrayQueue(5)
for i in range(10):
    Q.enqueue(i)
Q.printQueue()    
for i in range(10):
    Q.dequeue()
Q.printQueue()    


if __name__ == '__main__':
    main()

Nie będzie działać tak szybko, jak implementacja w C, ale używa tej samej logiki.

TheRevanchist
źródło
1
Nie wymyślaj.koła!
Abhijit Sarkar
Pytanie dotyczyło sposobu implementacji deque Pythona. Nie było prośbą o alternatywną implementację.
Gino Mempin