Jaka jest idiomatyczna składnia dla poprzedzania krótkiej listy python?

542

list.append()jest oczywistym wyborem do dodania na końcu listy. Oto rozsądne wyjaśnienie zaginięcia list.prepend(). Zakładając, że moja lista jest krótka, a problemy z wydajnością są znikome

list.insert(0, x)

lub

list[0:0] = [x]

idiomatyczny?

hurrymaplelad
źródło

Odpowiedzi:

782

s.insert(0, x)Forma jest najbardziej powszechne.

Ilekroć to zobaczysz, może być czas, aby rozważyć użycie collections.deque zamiast listy.

Raymond Hettinger
źródło
9
„Ilekroć to zobaczysz, może być czas na zastanowienie się nad użyciem collections.deque zamiast listy.” Dlaczego to?
Matt M.
6
@MattM. Jeśli wstawisz na początku listy, python musi przesunąć wszystkie pozostałe elementy o jedno miejsce do przodu, listy nie mogą „zrobić miejsca na początku”. collections.deque (kolejka podwójnie zakończona) obsługuje „tworzenie miejsca z przodu” i w tym przypadku jest znacznie szybsza.
fejfo
265

Jeśli możesz przejść funkcjonalnie, poniższe informacje są dość jasne

new_list = [x] + your_list

Oczywiście, że nie dodaje xsię your_list, a po utworzeniu nowej listy z xpreprended do niego.

Nil Geisweiller
źródło
45
Jak zauważysz, nie jest to przejście do listy. Tworzy nową listę. Zatem w ogóle nie spełnia tego pytania.
Chris Morgan
112
Chociaż nie spełnia tego pytania, uzupełnia je i taki jest cel tej witryny. Doceń ten komentarz i masz rację, ale kiedy ludzie go szukają, dobrze jest to zobaczyć.
dave4jr
2
Ponadto, jeśli chcesz dodać listę do listy, wówczas użycie wstawiania nie będzie działać zgodnie z oczekiwaniami. ale ta metoda ma!
gota
89

Jaka jest idiomatyczna składnia dla poprzedzania krótkiej listy python?

Zwykle nie chcesz powtarzalnie dodawać do listy w Pythonie.

Jeśli jest krótki i nie robisz tego dużo ... to dobrze.

list.insert

list.insertMogą być wykorzystane w ten sposób.

list.insert(0, x)

Jest to jednak nieefektywne, ponieważ w Pythonie a listto tablica wskaźników, a Python musi teraz pobrać każdy wskaźnik z listy i przesunąć go o jeden w dół, aby wstawić wskaźnik do obiektu w pierwszym gnieździe, więc jest to naprawdę skuteczne dla raczej krótkich list, jak pytasz.

Oto fragment kodu źródłowego CPython, w którym jest on zaimplementowany - i jak widać, zaczynamy od końca tablicy i przesuwamy wszystko o jeden w dół dla każdego wstawienia:

for (i = n; --i >= where; )
    items[i+1] = items[i];

Jeśli potrzebujesz kontenera / listy, która jest wydajna w dodawaniu elementów, potrzebujesz listy połączonej. Python ma podwójnie połączoną listę, którą można szybko wstawiać na początku i na końcu - nazywa się to deque.

deque.appendleft

collections.dequeMa wiele sposobów na liście. list.sortjest wyjątkiem, który dequedefinitywnie nie zastępuje Liskova list.

>>> set(dir(list)) - set(dir(deque))
{'sort'}

Ma dequerównież appendleftmetodę (jak również popleft). dequeJest dwukrotnie zakończył kolejka i podwójnie związany list - bez względu na długość, to zawsze ma taką samą ilość czasu, aby preprend coś. W dużej notacji O, O (1) a czas O (n) dla list. Oto użycie:

>>> import collections
>>> d = collections.deque('1234')
>>> d
deque(['1', '2', '3', '4'])
>>> d.appendleft('0')
>>> d
deque(['0', '1', '2', '3', '4'])

deque.extendleft

Istotna jest również extendleftmetoda deque , która iteracyjnie przygotowuje:

>>> from collections import deque
>>> d2 = deque('def')
>>> d2.extendleft('cba')
>>> d2
deque(['a', 'b', 'c', 'd', 'e', 'f'])

Pamiętaj, że każdy element będzie dodawany jeden po drugim, co skutecznie odwróci ich kolejność.

Wydajność listkontradeque

Najpierw konfigurujemy iteracyjne poprzedzanie:

import timeit
from collections import deque

def list_insert_0():
    l = []
    for i in range(20):
        l.insert(0, i)

def list_slice_insert():
    l = []
    for i in range(20):
        l[:0] = [i]      # semantically same as list.insert(0, i)

def list_add():
    l = []
    for i in range(20):
        l = [i] + l      # caveat: new list each time

def deque_appendleft():
    d = deque()
    for i in range(20):
        d.appendleft(i)  # semantically same as list.insert(0, i)

def deque_extendleft():
    d = deque()
    d.extendleft(range(20)) # semantically same as deque_appendleft above

i wydajność:

>>> min(timeit.repeat(list_insert_0))
2.8267281929729506
>>> min(timeit.repeat(list_slice_insert))
2.5210217320127413
>>> min(timeit.repeat(list_add))
2.0641671380144544
>>> min(timeit.repeat(deque_appendleft))
1.5863927800091915
>>> min(timeit.repeat(deque_extendleft))
0.5352169770048931

Deque jest znacznie szybszy. Gdy listy będą coraz dłuższe, oczekiwałbym, że deque będzie działał jeszcze lepiej. Jeśli możesz użyć deque's extendleft, prawdopodobnie uzyskasz w ten sposób najlepszą wydajność.

Aaron Hall
źródło
57

Jeśli ktoś znajdzie to pytanie tak jak ja, oto moje testy wydajności proponowanych metod:

Python 2.7.8

In [1]: %timeit ([1]*1000000).insert(0, 0)
100 loops, best of 3: 4.62 ms per loop

In [2]: %timeit ([1]*1000000)[0:0] = [0]
100 loops, best of 3: 4.55 ms per loop

In [3]: %timeit [0] + [1]*1000000
100 loops, best of 3: 8.04 ms per loop

Jak widać, insertprzypisywanie plasterków jest prawie dwa razy szybsze niż jawne dodawanie i są bardzo zbliżone w wynikach. Jak zauważył Raymond Hettinger , insertjest bardziej powszechną opcją i ja osobiście wolę ten sposób, aby przejść do listy.

Aleksiej Milogradow
źródło
11
Jedyną rzeczą, której brakuje w tym teście, jest złożoność. Podczas gdy dwie pierwsze opcje mają stałą złożoność (nie zwalnia, gdy jest więcej elementów na liście), trzecia ma liniową złożoność (staje się wolniejsza, w zależności od liczby elementów na liście), ponieważ zawsze musi skopiować całą listę. Przy większej liczbie elementów na liście wynik może być znacznie gorszy.
Dakkaron
6
@Dakkaron Myślę, że się mylisz. Sporo źródeł podaje liniową złożoność list.insert, np. Tę ładną tabelę , i sugeruje rozsądne wyjaśnienie, z którym łączył się pytający. Podejrzewam, że CPython ponownie przydziela każdy element w pamięci na liście w pierwszych dwóch przypadkach, więc wszystkie trzy prawdopodobnie mają złożoność liniową. Jednak sam nie sprawdziłem kodu i nie przetestowałem go, więc przepraszam, jeśli te źródła są błędne. Collections.deque.appendleft ma liniową złożoność, o której mówisz.
TC Proctor,
@Dakkaron nieprawda, wszystkie mają równoważną złożoność. Chociaż .inserti [0:0] = [0]działają w miejscu , wciąż muszą ponownie przydzielić cały bufor.
juanpa.arrivillaga
Te testy porównawcze są złe. Początkowa lista powinna zostać utworzona w oddzielnym kroku konfiguracji, a nie w ramach samego taktowania. Ostatni tworzy nową listę o długości 1000001, więc w porównaniu z pozostałymi dwoma mutującymi wersjami lokalnymi są jabłka i pomarańcze.
wim