Apa sintaksis idiomatik untuk mengawali ke daftar python pendek?

list.append()adalah pilihan yang jelas untuk ditambahkan ke akhir daftar. Berikut penjelasan yang masuk akal untuk yang hilanglist.prepend() . Menganggap daftar saya pendek dan masalah kinerja dapat diabaikan, adalah

list.insert(0, x)

atau

list[0:0] = [x]

idiomatis?

The s.insert(0, x)Bentuk yang paling umum.

Namun, kapan pun Anda melihatnya, mungkin sudah saatnya untuk mempertimbangkan untuk menggunakan collections.deque alih-alih daftar.

Jika Anda bisa menggunakan cara fungsional, berikut ini cukup jelas

new_list = [x] + your_list

Tentu saja Anda belum memasukkan x ke dalamnya your_list, melainkan Anda telah membuat daftar baru dengan xpreprended ke dalamnya.

Apa sintaksis idiomatik untuk mengawali ke daftar python pendek?

Anda biasanya tidak ingin berulang-ulang menambahkan daftar ke dalam Python.

Jika pendek , dan Anda tidak sering melakukannya ... maka baiklah.

list.insert

The list.insertdapat digunakan dengan cara ini.

list.insert(0, x)

Tapi ini tidak efisien, karena dalam Python, a listadalah array dari pointer, dan Python sekarang harus mengambil setiap pointer dalam daftar dan memindahkannya ke bawah dengan satu untuk memasukkan pointer ke objek Anda di slot pertama, jadi ini benar-benar hanya efisien untuk daftar yang agak pendek, seperti yang Anda minta.

Berikut cuplikan dari sumber CPython tempat ini diterapkan - dan seperti yang Anda lihat, kita mulai dari akhir array dan memindahkan semuanya ke bawah satu per setiap penyisipan:

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

Jika Anda menginginkan sebuah wadah / daftar yang efisien dalam elemen-elemen yang saling bergantung, Anda menginginkan daftar yang ditautkan. Python memiliki daftar tertaut ganda, yang dapat menyisipkan di awal dan akhir dengan cepat - ini disebut a deque.

deque.appendleft

A collections.dequememiliki banyak metode daftar. list.sortadalah pengecualian, membuat dequeLiskov pasti tidak sepenuhnya dapat diganti list.

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

Ini dequejuga memiliki appendleftmetode (dan juga popleft). Ini dequeadalah antrian dengan ujung ganda dan daftar yang terhubung ganda - tidak peduli panjangnya, selalu dibutuhkan jumlah waktu yang sama untuk menyiapkan sesuatu. Dalam notasi O besar, O (1) versus O (n) waktu untuk daftar. Inilah penggunaannya:

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

deque.extendleft

Juga relevan adalah metode deque extendleft, yang secara iteratif menambahkan:

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

Perhatikan bahwa setiap elemen akan ditambahkan satu per satu, sehingga secara efektif membalik urutannya.

Penampilan dari list versusdeque

Pertama kita atur dengan beberapa iterative prepending:

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

dan kinerja:

>>> 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 jauh lebih cepat. Seiring bertambahnya daftar, saya berharap deque akan tampil lebih baik. Jika Anda dapat menggunakan deque, extendleftAnda mungkin akan mendapatkan kinerja terbaik dengan cara itu.

Jika seseorang menemukan pertanyaan ini seperti saya, berikut ini adalah tes kinerja saya terhadap metode yang diusulkan:

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

Seperti yang Anda lihat, insertdan penugasan slice hampir dua kali lebih cepat daripada penambahan eksplisit dan hasilnya sangat dekat. Seperti yang dicatat oleh Raymond Hettingerinsert adalah opsi yang lebih umum dan saya, secara pribadi lebih suka cara ini untuk masuk daftar.