Dlaczego l.insert (0, i) jest wolniejsza niż l.append (i) w pythonie?

Question

Przetestowałem dwa sposoby odwrócenia listy w python.

import timeit 

value = [i for i in range(100)] 
def rev1(): 
    v = [] 
    for i in value: 
     v.append(i) 
    v.reverse() 

def rev2(): 
    v = [] 
    for i in value: 
     v.insert(0, i) 

print timeit.timeit(rev1) 
print timeit.timeit(rev2) 

Co ciekawe, druga metoda wstawiająca wartość do pierwszego elementu jest znacznie wolniejsza niż pierwsza.

20.4851300716 
73.5116429329 

Dlaczego tak jest? Pod względem działania wkładanie elementu do głowy nie wydaje się tak drogie. Jest to operacja

Answer 1

, ponieważ wymaga ona przesunięcia wszystkich elementów w lub po położeniu wstawki o jeden. append, z drugiej strony, ogólnie jest O(1) (i O(n) w najgorszym przypadku, gdy trzeba przydzielić więcej miejsca). To wyjaśnia znaczną różnicę czasu.

Złożoność czasowa tych metod jest dokładnie udokumentowana here.

I przytoczyć:

Wewnętrznie jest reprezentowany w tablicy; największe koszty pochodzą z powiększania się o bieżący rozmiar alokacji (ponieważ wszystko musi się przenieść) lub od wstawienia lub usunięcia gdzieś w pobliżu początku (ponieważ wszystko po tym musi się przesunąć).

Teraz, wracając do swojego kodu, możemy zobaczyć, że rev1() jest implementacją O(n) natomiast rev2() jest w rzeczywistości O(n2), więc ma to sens, że rev2() będzie znacznie wolniejsze.

Answer 2

W języku Python listy są zaimplementowane jako tablice. Jeśli dodasz jeden element do tablicy, zarezerwowane miejsce dla tablicy zostanie po prostu rozwinięte. Jeśli dodasz element, wszystkie elementy są przesuwane o 1 i jest to bardzo kosztowne.

Answer 3

możesz to potwierdzić, czytając o listach Pythona online. Python implementuje listę jako tablicę, w której rozmiar tablicy jest zwykle większy niż rozmiar bieżącej listy. Nieużywane elementy znajdują się na końcu tablicy i reprezentują nowe elementy, które można dodać do KONIEC listy, a nie początek. Python stosuje klasyczne, zamortyzowane podejście kosztowe, więc średnio dołączanie do końca listy zajmuje czas O (1), jeśli robisz kilka załączników, chociaż czasami pojedynczy dodatek powoduje, że tablica staje się pełna, więc nowa, szersza tablica należy utworzyć, a wszystkie dane skopiować do nowej tablicy. Z drugiej strony, jeśli zawsze wstawiasz na początku listy, wówczas w podstawowej tablicy wszystkie elementy muszą zostać przesunięte nad jednym indeksem, aby zrobić miejsce dla nowego elementu na początku tablicy. Podsumowując, jeśli utworzysz listę, wykonując N wstawień, całkowity czas działania będzie wynosił O (N), jeśli zawsze dodajesz nowe elementy na końcu listy i będzie to O (N^2), jeśli zawsze dołączasz do początku listy.