Bagaimana Daftar Python Diimplementasikan?

Apakah ini daftar tertaut, sebuah array? Saya mencari-cari dan hanya menemukan orang menebak. Pengetahuan C saya tidak cukup baik untuk melihat kode sumber.

Ini adalah array dinamis . Bukti praktis: Pengindeksan (tentu saja dengan perbedaan yang sangat kecil (0,0013 µsec!)) Waktu yang sama terlepas dari indeks:

...>python -m timeit --setup="x = [None]*1000" "x[500]"
10000000 loops, best of 3: 0.0579 usec per loop

...>python -m timeit --setup="x = [None]*1000" "x[0]"
10000000 loops, best of 3: 0.0566 usec per loop

Saya akan terkejut jika IronPython atau Jython menggunakan daftar tertaut - mereka akan merusak kinerja banyak banyak perpustakaan yang digunakan secara luas dibangun dengan asumsi bahwa daftar adalah array dinamis.

Kode C sebenarnya cukup sederhana. Memperluas satu makro dan memangkas beberapa komentar yang tidak relevan, struktur dasarnya ada di listobject.h, yang mendefinisikan daftar sebagai:

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size;

    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     */
    Py_ssize_t allocated;
} PyListObject;

PyObject_HEADberisi jumlah referensi dan pengenal tipe. Jadi, ini adalah vektor / array yang secara keseluruhan ditempatkan. Kode untuk mengubah ukuran array seperti itu ketika sudah penuh listobject.c. Sebenarnya tidak menggandakan array, tetapi tumbuh dengan mengalokasikan

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;

untuk kapasitas setiap kali, di mana newsizeukuran yang diminta (tidak harus allocated + 1karena Anda dapat extenddengan jumlah elemen yang sewenang-wenang alih-alih appendmengumpulkannya satu per satu).

Lihat juga FAQ Python .

Dalam CPython, daftar adalah array dari pointer. Implementasi lain dari Python dapat memilih untuk menyimpannya dengan cara yang berbeda.

Ini tergantung pada implementasi, tetapi IIRC:

• CPython menggunakan array pointer
• Jython menggunakan ArrayList
• IronPython rupanya juga menggunakan array. Anda dapat menelusuri kode sumber untuk mencari tahu.

Dengan demikian mereka semua memiliki O (1) akses acak.

Saya akan menyarankan artikel Laurent Luce "implementasi daftar Python" . Sangat berguna bagi saya karena penulis menjelaskan bagaimana daftar diimplementasikan dalam CPython dan menggunakan diagram yang sangat baik untuk tujuan ini.

Daftar struktur objek C

Objek daftar di CPython diwakili oleh struktur C berikut. ob_itemadalah daftar pointer ke elemen daftar. dialokasikan adalah jumlah slot yang dialokasikan dalam memori.

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

Penting untuk memperhatikan perbedaan antara slot yang dialokasikan dan ukuran daftar. Ukuran daftar sama dengan len(l). Jumlah slot yang dialokasikan adalah apa yang telah dialokasikan dalam memori. Seringkali, Anda akan melihat bahwa alokasi dapat lebih besar dari ukuran. Ini untuk menghindari keharusan memanggil reallocsetiap kali elemen baru ditambahkan ke daftar.

...

Menambahkan

Kami menambahkan integer ke dalam daftar: l.append(1). Apa yang terjadi?

Kami terus dengan menambahkan satu elemen lagi: l.append(2). list_resizedipanggil dengan n + 1 = 2 tetapi karena ukuran yang dialokasikan adalah 4, tidak perlu mengalokasikan lebih banyak memori. Hal yang sama terjadi ketika kita menambahkan 2 bilangan bulat lainnya: l.append(3), l.append(4). Diagram berikut menunjukkan apa yang kita miliki sejauh ini.

...

Memasukkan

Mari kita masukkan integer baru (5) di posisi 1: l.insert(1,5)dan lihat apa yang terjadi secara internal.

...

Pop

Ketika Anda pop elemen terakhir: l.pop(), listpop()disebut. list_resizedisebut di dalam listpop()dan jika ukuran baru kurang dari setengah dari ukuran yang dialokasikan maka daftar menyusut.

Anda dapat mengamati bahwa slot 4 masih menunjuk ke integer tetapi yang penting adalah ukuran daftar yang sekarang 4. Mari kita pop satu elemen lagi. Dalam list_resize(), ukuran - 1 = 4 - 1 = 3 kurang dari setengah slot yang dialokasikan sehingga daftar menyusut menjadi 6 slot dan ukuran baru daftar sekarang 3.

Anda dapat mengamati bahwa slot 3 dan 4 masih menunjuk ke beberapa bilangan bulat tetapi yang penting adalah ukuran daftar yang sekarang 3.

...

Hapus Python daftar objek memiliki metode untuk menghapus elemen tertentu: l.remove(5).

Menurut dokumentasi ,

Daftar Python adalah array yang benar-benar panjang variabel, bukan daftar tertaut gaya Lisp.

Seperti yang telah dinyatakan oleh orang lain di atas, daftar (ketika cukup besar) dilaksanakan dengan mengalokasikan jumlah ruang yang tetap, dan, jika ruang itu harus diisi, mengalokasikan jumlah ruang yang lebih besar dan menyalin elemen-elemen tersebut.

Untuk memahami mengapa metode ini diamortisasi O (1), tanpa kehilangan sifat umum, asumsikan kita telah memasukkan elemen = 2 ^ n, dan sekarang kita harus menggandakan tabel kita menjadi ukuran 2 ^ (n +1). Itu berarti kami sedang melakukan 2 ^ (n +1) operasi. Salinan terakhir, kami melakukan 2 ^ operasi. Sebelum itu kami melakukan 2 ^ (n-1) ... hingga 8,4,2,1. Sekarang, jika kita tambahkan ini, kita mendapatkan 1 + 2 + 4 + 8 + ... + 2 ^ (n + 1) = 2 ^ (n + 2) - 1 <4 * 2 ^ n = O (2 ^ n) = O (a) total penyisipan (yaitu O (1) waktu diamortisasi). Juga, harus dicatat bahwa jika tabel memungkinkan penghapusan, penyusutan tabel harus dilakukan pada faktor yang berbeda (misalnya 3x)

Daftar dalam Python adalah sesuatu seperti array, tempat Anda bisa menyimpan banyak nilai. Daftar bisa berubah yang berarti Anda dapat mengubahnya. Hal yang lebih penting yang harus Anda ketahui, ketika kita membuat daftar, Python secara otomatis membuat reference_id untuk variabel daftar itu. Jika Anda mengubahnya dengan menetapkan variabel lain, daftar utama akan berubah. Mari kita coba dengan sebuah contoh:

list_one = [1,2,3,4]

my_list = list_one

#my_list: [1,2,3,4]

my_list.append("new")

#my_list: [1,2,3,4,'new']
#list_one: [1,2,3,4,'new']

Kami menambahkan my_listtetapi daftar utama kami telah berubah. Daftar mean itu tidak menetapkan sebagai daftar salinan ditugaskan sebagai referensi.

Dalam daftar CPython diimplementasikan sebagai array dinamis, dan karena itu ketika kita menambahkan pada saat itu tidak hanya satu makro ditambahkan tetapi lebih banyak ruang dialokasikan sehingga setiap kali ruang baru tidak boleh ditambahkan.