Bagaimana cara mengoptimalkan skrip python?

Versi ini melakukan rangkaian operasi string yang persis sama seperti yang pertama, tetapi menghilangkan overhead for loop demi loop yang lebih cepat dan tersirat dari fungsi reduce()

Tentu, jawab saya, tetapi itu dilakukan dengan mengorbankan panggilan fungsi (fungsi lambda) per item daftar. Saya yakin itu lebih lambat, karena overhead pemanggilan fungsi di Python lebih besar daripada overhead for loop

(Oke, jadi saya sudah melakukan perbandingan. f2() membutuhkan waktu 60% lebih lama daripada f1(). Jadi disana. -)

Hmm, kata teman saya. Saya membutuhkan ini untuk menjadi lebih cepat. Oke, kataku, bagaimana dengan versi ini

    def f3(list):
        string = ""
        for character in map(chr, list):
            string = string + character
        return string

Yang mengejutkan kami, f3() mencatat waktu dua kali lebih cepat dari f1(). Alasan mengapa hal ini mengejutkan kami ada dua. pertama, ini menggunakan lebih banyak penyimpanan (hasil dari map(chr, list) adalah daftar lain dengan panjang yang sama);

Tentu saja, ruang versus waktu adalah trade-off yang terkenal, jadi yang pertama seharusnya tidak mengejutkan kita. Namun, kenapa dua loop lebih cepat dari satu?

Pertama, di f1(), fungsi bawaan chr() dicari di setiap iterasi, sedangkan di f3() hanya dicari sekali (sebagai argumen untuk memetakan()). Pencarian ini relatif mahal, saya memberi tahu teman saya, karena aturan lingkup dinamis Python berarti bahwa ini pertama kali dicari (tidak berhasil) di kamus global modul saat ini, dan kemudian di kamus fungsi bawaan (di mana ditemukan . Lebih buruk lagi, pencarian kamus yang tidak berhasil (rata-rata) sedikit lebih lambat daripada yang berhasil, karena cara kerja rantai hash

Alasan kedua mengapa f3() lebih cepat daripada f1() adalah bahwa panggilan ke chr(item), seperti yang dieksekusi oleh juru bahasa bytecode, mungkin sedikit lebih lambat daripada saat dijalankan oleh fungsi map() - juru bahasa bytecode harus mengeksekusi

Hal ini membuat kami mempertimbangkan kompromi, yang tidak akan menyia-nyiakan ruang ekstra, tetapi akan mempercepat pencarian fungsi chr()

    def f4(list):
        string = ""
        lchr = chr
        for item in list:
            string = string + lchr(item)
        return string

Seperti yang diharapkan, f4() lebih lambat dari f3(), tetapi hanya sebesar 25%; . Ini karena pencarian variabel lokal jauh lebih cepat daripada pencarian variabel global atau built-in. "kompiler" Python mengoptimalkan sebagian besar badan fungsi sehingga untuk variabel lokal, tidak diperlukan pencarian kamus, tetapi operasi pengindeksan array sederhana sudah cukup. Kecepatan relatif f4() dibandingkan dengan f1() dan f3() menunjukkan bahwa kedua alasan mengapa f3() berkontribusi lebih cepat, tetapi alasan pertama (lebih sedikit pencarian) sedikit lebih penting. (Untuk mendapatkan data yang lebih akurat tentang ini, kami harus melengkapi juru bahasa. )

Tetap saja, versi terbaik kami, f3(), hanya dua kali lebih cepat dari versi yang paling sederhana, f1(). Bisakah kita berbuat lebih baik?

Saya khawatir perilaku kuadrat dari algoritme membunuh kami. Sejauh ini, kami telah menggunakan daftar 256 bilangan bulat sebagai data uji, karena itulah fungsi yang dibutuhkan teman saya. Tapi bagaimana jika diterapkan pada daftar dua ribu karakter? . Sangat mudah untuk melihat bahwa, selain overhead, untuk membuat daftar panjang N dengan cara ini, ada 1 + 2 + 3 +. + (N-1) karakter yang akan disalin seluruhnya, atau N*(N-1)/2, atau 0. 5*N**2 - 0. 5*N. Selain itu, terdapat operasi alokasi string N, tetapi untuk N yang cukup besar, term yang berisi N**2 akan mengambil alih. Memang, untuk daftar yang 8 kali lebih panjang (2048 item), semua fungsi ini memerlukan waktu lebih dari 8 kali lebih lama; . Saya tidak berani mencoba daftar 64 kali lebih lama

Ada teknik umum untuk menghindari perilaku kuadrat dalam algoritme seperti ini. Saya mengkodekannya sebagai berikut untuk string tepat 256 item

    def f5(list):
        string = ""
        for i in range(0, 256, 16): # 0, 16, 32, 48, 64, ...
            s = ""
            for character in map(chr, list[i:i+16]):
                s = s + character
            string = string + s
        return string

Sayangnya, untuk daftar 256 item, versi ini berjalan sedikit lebih lambat (meskipun dalam 20%) dari f3(). Karena menulis versi umum hanya akan memperlambatnya, kami tidak repot-repot melanjutkan jalur ini lebih jauh (kecuali bahwa kami juga membandingkannya dengan varian yang tidak menggunakan map(), yang tentu saja lebih lambat lagi)

Akhirnya, saya mencoba pendekatan yang sangat berbeda. gunakan hanya loop tersirat. Perhatikan bahwa seluruh operasi dapat dijelaskan sebagai berikut. terapkan chr() ke setiap item daftar; . Kami sudah menggunakan loop tersirat untuk bagian pertama. peta(). Untungnya, ada beberapa fungsi penggabungan string dalam modul string yang diimplementasikan dalam C. Secara khusus, string. joinfields(list_of_strings, delimiter) menggabungkan daftar string, menempatkan pembatas pilihan antara masing-masing dua string. Tidak ada yang menghentikan kita untuk menggabungkan daftar karakter (yang hanya berupa string dengan panjang satu di Python), menggunakan string kosong sebagai pembatas. Lihatlah

    import string
    def f6(list):
        return string.joinfields(map(chr, list), "")

Fungsi ini berjalan empat hingga lima kali lebih cepat dari pesaing tercepat kami, f3(). Selain itu, ia tidak memiliki perilaku kuadrat dari versi lainnya

Dan pemenangnya adalah

Keesokan harinya, saya ingat sudut aneh Python. modul larik. Ini kebetulan memiliki operasi untuk membuat larik bilangan bulat selebar 1 byte dari daftar bilangan bulat Python, dan setiap larik dapat ditulis ke file atau diubah menjadi string sebagai struktur data biner. Inilah fungsi kami yang diimplementasikan menggunakan operasi ini

    import array
    def f7(list):
        return array.array('B', list).tostring()

Ini sekitar tiga kali lebih cepat dari f6(), atau 12 hingga 15 kali lebih cepat dari f3(). ia juga menggunakan penyimpanan perantara yang lebih sedikit - hanya mengalokasikan 2 objek N byte (ditambah overhead tetap), sementara f6() dimulai dengan mengalokasikan daftar item N, yang biasanya berharga 4N byte (8N byte pada mesin 64-bit) -

Berhenti, kata teman saya, sebelum Anda masuk ke masa negatif - ini cukup cepat untuk program saya. Saya setuju, meskipun saya ingin mencoba satu pendekatan lagi. tulis seluruh fungsi dalam C. Ini dapat memiliki persyaratan penyimpanan minimal (itu akan segera mengalokasikan string dengan panjang N) dan menyimpan beberapa instruksi dalam kode C yang saya tahu ada di modul array, karena sifatnya yang generik (mendukung lebar bilangan bulat 1, 2 . Namun, itu tidak akan dapat menghindari keharusan mengekstrak item dari daftar satu per satu, dan mengekstrak bilangan bulat C darinya, keduanya merupakan operasi yang cukup mahal di API Python-C, jadi saya perkirakan di . Mengingat upaya menulis dan menguji ekstensi (dibandingkan dengan menyiapkan satu kalimat Python), serta ketergantungan pada ekstensi Python non-standar, saya memutuskan untuk tidak mengejar opsi ini

Kesimpulan

Jika Anda merasa perlu kecepatan, gunakan fungsi bawaan - Anda tidak dapat mengalahkan loop yang ditulis dalam C. Periksa manual perpustakaan untuk fungsi bawaan yang melakukan apa yang Anda inginkan. Jika tidak ada, berikut beberapa panduan untuk pengoptimalan loop

• Aturan nomor satu. hanya optimalkan bila ada hambatan kecepatan yang terbukti. Hanya optimalkan loop terdalam. (Aturan ini tidak bergantung pada Python, tetapi tidak ada salahnya mengulanginya, karena dapat menghemat banyak pekerjaan. . -)
• Kecil itu indah. Mengingat biaya Python yang besar dan kuat untuk instruksi bytecode dan pencarian variabel, jarang ada gunanya menambahkan tes tambahan untuk menghemat sedikit pekerjaan
• Gunakan operasi intrinsik. Loop tersirat di map() lebih cepat daripada loop for eksplisit;
• Hindari memanggil fungsi yang ditulis dengan Python di lingkaran dalam Anda. Ini termasuk lambda. Melapisi loop dalam dapat menghemat banyak waktu
• Variabel lokal lebih cepat daripada variabel global; . Dan di Python, nama fungsi (global atau bawaan) juga merupakan konstanta global
• Cobalah untuk menggunakan map(), filter() atau reduce() untuk menggantikan for loop eksplisit, tetapi hanya jika Anda dapat menggunakan fungsi bawaan. map dengan fungsi bawaan mengalahkan for loop, tetapi for loop dengan kode sebaris mengalahkan map dengan fungsi lambda
• Periksa algoritme Anda untuk perilaku kuadrat. Tetapi perhatikan bahwa algoritme yang lebih kompleks hanya terbayar untuk N besar - untuk N kecil, kerumitannya tidak terbayar. Dalam kasus kami, 256 ternyata cukup kecil sehingga versi yang lebih sederhana masih sedikit lebih cepat. Jarak tempuh Anda mungkin berbeda - ini perlu diselidiki
• Dan yang tak kalah pentingnya. mengumpulkan data. Modul profil Python yang luar biasa dapat dengan cepat menunjukkan hambatan dalam kode Anda. jika Anda sedang mempertimbangkan berbagai versi algoritme, ujilah dalam putaran ketat menggunakan waktu. jam() fungsi

Omong-omong, inilah fungsi pengaturan waktu yang saya gunakan. itu memanggil fungsi f n*10 kali dengan argumen a, dan mencetak nama fungsi diikuti dengan waktu yang dibutuhkan, dibulatkan menjadi milidetik. 10 panggilan berulang dilakukan untuk meminimalkan overhead loop dari fungsi pengaturan waktu itu sendiri. Anda bisa melangkah lebih jauh dan melakukan 100 panggilan. Perhatikan juga bahwa rentang ekspresi (n) dihitung di luar tanda kurung waktu - trik lain untuk meminimalkan overhead yang disebabkan oleh fungsi waktu. Jika Anda khawatir tentang overhead ini, Anda dapat mengalibrasikannya dengan memanggil fungsi pengaturan waktu dengan fungsi tidak melakukan apa-apa

    import time
    def timing(f, n, a):
        print f.__name__,
        r = range(n)
        t1 = time.clock()
        for i in r:
            f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a)
        t2 = time.clock()
        print round(t2-t1, 3)

Epilog

Beberapa hari kemudian, teman saya kembali dengan pertanyaan itu. bagaimana Anda melakukan operasi sebaliknya? . e. buat daftar nilai ASCII bilangan bulat dari sebuah string. Oh tidak, ini dia lagi, terlintas di benak saya

Tapi kali ini, itu relatif tidak menyakitkan. Ada dua kandidat, yang jelas

    def g1(string):
        return map(ord, string)

dan agak kurang jelas

    import array
    def g2(string):
        return array.array('b', string).tolist()

Pengaturan waktu ini menunjukkan bahwa g2() kira-kira lima kali lebih cepat dari g1(). Namun ada tangkapan. g2() mengembalikan bilangan bulat dalam rentang -128. 127, sedangkan g1() mengembalikan bilangan bulat dalam kisaran 0. 255. Jika Anda memerlukan bilangan bulat positif, g1() akan menjadi lebih cepat daripada pemrosesan pasca apa pun yang dapat Anda lakukan pada hasil dari g2(). (Catatan. sejak esai ini ditulis, kode jenis 'B' telah ditambahkan ke modul array, yang menyimpan byte yang tidak ditandatangani, jadi tidak ada alasan untuk memilih g1() lagi. )

Bagaimana cara membuat kode lebih optimal?

Bagaimana Anda mengoptimalkan runtime dengan Python?

Bagaimana Anda mengoptimalkan for loop dengan Python?