Mengapa [] lebih cepat daripada daftar ()?

Saya baru-baru ini membandingkan kecepatan pemrosesan []dan list()dan terkejut menemukan bahwa []berjalan lebih dari tiga kali lebih cepat daripada list(). Saya menjalankan tes yang sama dengan {}dan dict()dan hasilnya praktis identik: []dan {}keduanya mengambil sekitar 0,128 detik / juta siklus, sementara list()dan dict()mengambil sekitar 0,428 detik / juta siklus masing-masing.

Kenapa ini? Apakah []dan {}(dan mungkin ()dan '', juga) segera lulus kembali salinan dari beberapa literal saham kosong sementara rekan-rekan mereka secara eksplisit bernama ( list(), dict(), tuple(), str()) sepenuhnya pergi tentang menciptakan sebuah objek, apakah mereka benar-benar memiliki unsur-unsur?

Saya tidak tahu bagaimana kedua metode ini berbeda tetapi saya ingin mengetahuinya. Saya tidak dapat menemukan jawaban di dokumen atau di SO, dan mencari kurung kosong ternyata lebih bermasalah dari yang saya duga.

Saya mendapatkan hasil pengaturan waktu saya dengan menelepon timeit.timeit("[]")dan timeit.timeit("list()"), timeit.timeit("{}")dan timeit.timeit("dict()"), dan, masing-masing untuk membandingkan daftar dan kamus. Saya menjalankan Python 2.7.9.

Baru-baru ini saya menemukan " Mengapa jika Benar lebih lambat daripada jika 1? " Yang membandingkan kinerja if Trueto if 1dan tampaknya menyentuh skenario literal-versus-global yang serupa; mungkin perlu dipertimbangkan juga.

Karena []dan {}merupakan sintaksis literal . Python dapat membuat bytecode hanya untuk membuat daftar atau objek kamus:

>>> import dis
>>> dis.dis(compile('[]', '', 'eval'))
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
>>> dis.dis(compile('{}', '', 'eval'))
  1           0 BUILD_MAP                0
              3 RETURN_VALUE        

list()dan dict()merupakan objek yang terpisah. Nama-nama mereka perlu diatasi, tumpukan harus dilibatkan untuk mendorong argumen, frame harus disimpan untuk mengambil nanti, dan panggilan harus dibuat. Itu semua membutuhkan lebih banyak waktu.

Untuk kasing kosong, itu berarti Anda memiliki paling tidak a LOAD_NAME(yang harus mencari melalui namespace global dan __builtin__modul ) diikuti oleh a CALL_FUNCTION, yang harus mempertahankan bingkai saat ini:

>>> dis.dis(compile('list()', '', 'eval'))
  1           0 LOAD_NAME                0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
>>> dis.dis(compile('dict()', '', 'eval'))
  1           0 LOAD_NAME                0 (dict)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        

Anda dapat mengatur waktu pencarian nama secara terpisah dengan timeit:

>>> import timeit
>>> timeit.timeit('list', number=10**7)
0.30749011039733887
>>> timeit.timeit('dict', number=10**7)
0.4215109348297119

Perbedaan waktu mungkin ada tabrakan hash kamus. Kurangi waktu itu dari waktu untuk memanggil objek-objek itu, dan bandingkan hasilnya dengan waktu untuk menggunakan literal:

>>> timeit.timeit('[]', number=10**7)
0.30478692054748535
>>> timeit.timeit('{}', number=10**7)
0.31482696533203125
>>> timeit.timeit('list()', number=10**7)
0.9991960525512695
>>> timeit.timeit('dict()', number=10**7)
1.0200958251953125

Jadi harus memanggil objek membutuhkan tambahan 1.00 - 0.31 - 0.30 == 0.39detik per 10 juta panggilan.

Anda dapat menghindari biaya pencarian global dengan menamai nama global sebagai penduduk lokal (menggunakan timeitpengaturan, semua yang Anda ikat ke nama adalah lokal):

>>> timeit.timeit('_list', '_list = list', number=10**7)
0.1866450309753418
>>> timeit.timeit('_dict', '_dict = dict', number=10**7)
0.19016098976135254
>>> timeit.timeit('_list()', '_list = list', number=10**7)
0.841480016708374
>>> timeit.timeit('_dict()', '_dict = dict', number=10**7)
0.7233691215515137

tetapi Anda tidak pernah bisa mengatasi CALL_FUNCTIONbiaya itu.

list()membutuhkan pencarian global dan panggilan fungsi tetapi []mengkompilasi ke satu instruksi. Lihat:

Python 2.7.3
>>> import dis
>>> print dis.dis(lambda: list())
  1           0 LOAD_GLOBAL              0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
None
>>> print dis.dis(lambda: [])
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
None

Karena listadalah fungsi untuk mengkonversi katakanlah string ke objek daftar, sementara []digunakan untuk membuat daftar dari kelelawar. Coba ini (mungkin lebih masuk akal bagi Anda):

x = "wham bam"
a = list(x)
>>> a
["w", "h", "a", "m", ...]

Sementara

y = ["wham bam"]
>>> y
["wham bam"]

Memberi Anda daftar aktual yang berisi apa pun yang Anda masukkan ke dalamnya.

Jawaban di sini bagus, to the point dan sepenuhnya mencakup pertanyaan ini. Saya akan turun lebih jauh dari byte-code untuk mereka yang tertarik. Saya menggunakan repo CPython terbaru; versi yang lebih lama berperilaku serupa dalam hal ini tetapi sedikit perubahan mungkin terjadi.

Berikut adalah rincian eksekusi untuk masing-masing, BUILD_LISTuntuk []dan CALL_FUNCTIONuntuk list().

The BUILD_LISTinstruksi:

Anda hanya harus melihat kengeriannya:

PyObject *list =  PyList_New(oparg);
if (list == NULL)
    goto error;
while (--oparg >= 0) {
    PyObject *item = POP();
    PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();

Saya tahu, sangat berbelit-belit. Ini adalah betapa sederhananya:

• Buat daftar baru dengan PyList_New(ini terutama mengalokasikan memori untuk objek daftar baru), opargmenandakan jumlah argumen pada stack. Langsung ke intinya.
• Pastikan tidak ada yang salah dengan if (list==NULL).
• Tambahkan argumen apa pun (dalam kasus kami ini tidak dijalankan) yang terletak di tumpukan dengan PyList_SET_ITEM(makro).

Tidak heran itu cepat! Dibuat khusus untuk membuat daftar baru, tidak ada yang lain :-)

The CALL_FUNCTIONinstruksi:

Inilah hal pertama yang Anda lihat ketika Anda mengintip penanganan kode CALL_FUNCTION:

PyObject **sp, *res;
sp = stack_pointer;
res = call_function(&sp, oparg, NULL);
stack_pointer = sp;
PUSH(res);
if (res == NULL) {
    goto error;
}
DISPATCH();

Terlihat tidak berbahaya, kan? Yah, tidak, sayangnya tidak, call_functionbukan orang yang langsung akan memanggil fungsi segera, itu tidak bisa. Sebagai gantinya, ia mengambil objek dari stack, meraih semua argumen stack dan kemudian beralih berdasarkan pada jenis objek; apakah itu:

• PyCFunction_Type? Tidak, itu adalah list, listtidak dari jenisPyCFunction
• PyMethodType? Tidak, lihat sebelumnya.
• PyFunctionType? Tidak, lihat sebelumnya.

Kami memanggil listtipe, argumen yang diteruskan call_functionadalah PyList_Type. CPython sekarang harus memanggil fungsi generik untuk menangani objek yang bisa dipanggil bernama _PyObject_FastCallKeywords, yay lebih banyak panggilan fungsi.

Fungsi ini lagi membuat beberapa pemeriksaan untuk jenis fungsi tertentu (yang saya tidak mengerti mengapa) dan kemudian, setelah membuat dikt untuk kwargs jika diperlukan , melanjutkan panggilan _PyObject_FastCallDict.

_PyObject_FastCallDictakhirnya membawa kita ke suatu tempat! Setelah melakukan bahkan lebih cek itu meraih tp_callslot yang daritype dari typekita sudah berlalu dalam, yaitu, meraih type.tp_call. Itu kemudian mulai membuat tuple dari argumen yang diteruskan _PyStack_AsTupledan, akhirnya, panggilan akhirnya dapat dibuat !

tp_call, yang cocok type.__call__mengambil alih dan akhirnya membuat objek daftar. Itu panggilan daftar __new__yang sesuai dengan PyType_GenericNewdan mengalokasikan memori untuk itu dengan PyType_GenericAlloc: Ini sebenarnya bagian di mana ia mengejar ketinggalan PyList_New, akhirnya . Semua yang sebelumnya diperlukan untuk menangani objek secara umum.

Pada akhirnya, type_callpanggilan list.__init__dan inisialisasi daftar dengan argumen yang tersedia, kemudian kami kembali seperti kami datang. :-)

Akhirnya, ingat LOAD_NAME, itu cowok lain yang berkontribusi di sini.

Sangat mudah untuk melihat bahwa, ketika berhadapan dengan input kami, Python umumnya harus melompat melalui lingkaran untuk benar-benar mengetahui Cfungsi yang tepat untuk melakukan pekerjaan itu. Itu tidak memiliki ketepatan untuk segera menyebutnya karena itu dinamis, seseorang mungkin menutupi list( dan anak laki-laki lakukan banyak orang ) dan jalan lain harus diambil.

Di sinilah list()kehilangan banyak: Python mengeksplorasi perlu lakukan untuk mencari tahu apa yang harus dilakukan.

Sintaks literal, di sisi lain, berarti tepat satu hal; itu tidak dapat diubah dan selalu berperilaku dengan cara yang ditentukan sebelumnya.

^{Catatan Kaki: Semua nama fungsi dapat berubah dari satu rilis ke rilis lainnya. Intinya masih berdiri dan kemungkinan besar akan berdiri di versi masa depan, itu adalah pencarian dinamis yang memperlambat segalanya.}

Kenapa []lebih cepat dari itu list()?

Alasan terbesarnya adalah bahwa Python memperlakukan list()seperti fungsi yang ditentukan pengguna, yang berarti Anda dapat mencegatnya dengan mengalihkan sesuatu yang lain ke listdan melakukan sesuatu yang berbeda (seperti menggunakan daftar subklas Anda sendiri atau mungkin deque).

Segera membuat contoh baru dari daftar builtin dengan [].

Penjelasan saya berusaha memberi Anda intuisi untuk ini.

Penjelasan

[] umumnya dikenal sebagai sintaksis literal.

Dalam tata bahasa, ini disebut sebagai "tampilan daftar". Dari dokumen :

Tampilan daftar adalah serangkaian ekspresi yang mungkin kosong yang terlampir dalam tanda kurung:

list_display ::=  "[" [starred_list | comprehension] "]"

Tampilan daftar menghasilkan objek daftar baru, konten yang ditentukan oleh daftar ekspresi atau pemahaman. Ketika daftar ekspresi yang dipisahkan koma disediakan, elemen-elemennya dievaluasi dari kiri ke kanan dan ditempatkan ke objek daftar dalam urutan itu. Ketika pemahaman diberikan, daftar dibangun dari elemen-elemen yang dihasilkan dari pemahaman.

Singkatnya, ini berarti bahwa objek tipe builtin listdibuat.

Tidak ada yang bisa mengelak dari ini - yang berarti Python dapat melakukannya secepat mungkin.

Di sisi lain, list()dapat dicegat dari membuat builtin listmenggunakan konstruktor daftar builtin.

Misalnya, kami ingin daftar kami dibuat dengan berisik:

class List(list):
    def __init__(self, iterable=None):
        if iterable is None:
            super().__init__()
        else:
            super().__init__(iterable)
        print('List initialized.')

Kami kemudian dapat mencegat nama listpada lingkup global level modul, dan kemudian ketika kami membuat list, kami benar-benar membuat daftar subtipe kami:

>>> list = List
>>> a_list = list()
List initialized.
>>> type(a_list)
<class '__main__.List'>

Demikian pula kita dapat menghapusnya dari namespace global

del list

dan letakkan di namespace builtin:

import builtins
builtins.list = List

Dan sekarang:

>>> list_0 = list()
List initialized.
>>> type(list_0)
<class '__main__.List'>

Dan perhatikan bahwa tampilan daftar membuat daftar tanpa syarat:

>>> list_1 = []
>>> type(list_1)
<class 'list'>

Kami mungkin hanya melakukan ini sementara, jadi mari kita batalkan perubahan kami - pertama-tama hapus Listobjek baru dari bawaan:

>>> del builtins.list
>>> builtins.list
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: module 'builtins' has no attribute 'list'
>>> list()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'list' is not defined

Oh, tidak, kami kehilangan jejak aslinya.

Tidak perlu khawatir, kita masih bisa mendapatkan list- itu adalah jenis daftar literal:

>>> builtins.list = type([])
>>> list()
[]

Begitu...

Kenapa []lebih cepat dari itu list()?

Seperti yang telah kita lihat - kita dapat menimpa list- tetapi kita tidak dapat mencegat penciptaan tipe literal. Ketika kita menggunakan listkita harus melakukan pencarian untuk melihat apakah ada sesuatu di sana.

Maka kita harus memanggil panggilan apa pun yang kita cari. Dari tata bahasa:

Panggilan memanggil objek yang dapat dipanggil (misalnya, fungsi) dengan serangkaian argumen yang mungkin kosong:

call                 ::=  primary "(" [argument_list [","] | comprehension] ")"

Kita dapat melihat bahwa ia melakukan hal yang sama untuk nama apa pun, tidak hanya daftar:

>>> import dis
>>> dis.dis('list()')
  1           0 LOAD_NAME                0 (list)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE
>>> dis.dis('doesnotexist()')
  1           0 LOAD_NAME                0 (doesnotexist)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE

Karena []tidak ada panggilan fungsi di tingkat bytecode Python:

>>> dis.dis('[]')
  1           0 BUILD_LIST               0
              2 RETURN_VALUE

Itu hanya langsung membangun daftar tanpa pencarian atau panggilan di tingkat bytecode.

Kesimpulan

Kami telah menunjukkan bahwa listdapat dicegat dengan kode pengguna menggunakan aturan pelingkupan, dan yang list()mencari callable dan kemudian menyebutnya.

Sedangkan []tampilan daftar, atau literal, dan dengan demikian menghindari pencarian nama dan panggilan fungsi.