Sedikit latar belakang tentang Python
Python adalah bahasa yang bagus. Saya mencoba beberapa bahasa sebelumnya: Pascal di sekolah; C, C dengan kelas, C ++ di universitas. Dua (tiga) yang terakhir menanamkan keengganan yang kuat untuk pemrograman: alih-alih menyelesaikan masalah, Anda mengacaukan alokasi dan penghancur (kata-kata menakutkan dari masa lalu), Anda berpikir dalam hal primitif tingkat rendah. Pendapat saya adalah bahwa C tidak cocok untuk menyelesaikan masalah pendidikan dan ilmiah (dalam hal apa pun, di bidang matematika). Saya yakin mereka akan menolak saya, tetapi saya tidak mencoba memaksakan apa pun pada siapa pun, saya hanya mengekspresikan pendapat saya.
Python dulunya adalah wahyu. Untuk pertama kalinya dalam hidup saya, saya menulis beberapa tingkat abstraksi lebih tinggi daripada apa yang biasanya dilakukan dalam bahasa C. Jarak antara tugas dan kode telah dikurangi tidak seperti sebelumnya.
Saya mungkin akan melakukan ini sepanjang hidup saya di Python jika saya tidak harus tiba-tiba mengimplementasikan tes statistik NIST. Tampaknya tugasnya sangat sederhana: ada array dengan beberapa (> = 10) megabita panjangnya, ada serangkaian tes yang perlu diterapkan ke array ini.
Untuk apa numpy bagus?
Dalam python, ada paket numpy yang bagus untuk bekerja dengan array, yang pada dasarnya adalah antarmuka tingkat tinggi untuk perpustakaan cepat seperti LAPACK. Tampaknya set seluruh pria untuk komputasi ilmiah tersedia (Sympy, Numpy, Scipy, Matplotlib), apa lagi yang Anda inginkan?
Setiap orang yang berurusan dengan numpy tahu bahwa dia baik, tetapi tidak dalam segala hal. Kita masih perlu mencoba memastikan bahwa operasi di vektorisasi (seperti pada R), yaitu dalam arti, seragam untuk seluruh array. Jika tiba-tiba masalah Anda karena alasan tertentu tidak sesuai dengan paradigma ini, maka Anda memiliki masalah.
Apa tugas non-vektor yang saya bicarakan? Ya, setidaknya ambil NIST yang sama: hitung panjang register geser linier menggunakan algoritma Berlekamp-Messi; menghitung panjang unit terpanjang berturut-turut dan seterusnya. Saya tidak mengesampingkan kemungkinan bahwa ada beberapa jenis solusi cerdik yang akan mengurangi masalah menjadi solusi vektor.
Licik?Sebagai contoh dari NIST yang sama: perlu untuk menghitung jumlah urutan "switching", di mana dengan "beralih" maksud saya mengubah unit berturut-turut (... 1111 ...) menjadi nol berturut-turut (... 000 ... ), dan sebaliknya. Untuk melakukan ini, Anda dapat mengambil urutan asli tanpa elemen terakhir (x [: -1]) dan mengurangi darinya urutan digeser oleh 1 (x [2:]), dan kemudian menghitung jumlah elemen bukan nol di urutan baru yang dihasilkan. Semuanya akan terlihat seperti:
np.count_nonzero(x[:-1] - x[1:])
Ini mungkin terlihat seperti latihan menghibur untuk pikiran, tetapi pada dasarnya sesuatu yang tidak wajar terjadi di sini, sebuah trik yang tidak akan terlihat jelas bagi pembaca setelah beberapa saat. Belum lagi bahwa ini masih lambat - tidak ada yang membatalkan alokasi memori.
Operasi non-vektor di Python adalah waktu yang lama. Bagaimana menghadapi mereka jika numpy tidak cukup? Biasanya mereka menawarkan beberapa solusi:
- Numba JIT. Jika dia bekerja seperti yang dijelaskan pada halaman judul Numba, maka saya pikir itu akan bermanfaat untuk menyelesaikan cerita. Saya telah sedikit melupakan masa lalu bahwa apa yang salah dengannya; Intinya adalah bahwa akselerasi itu tidak mengesankan seperti yang saya harapkan, sayangnya.
- Cython. Oke, angkat tangan, mereka yang percaya bahwa cython adalah solusi yang sangat indah dan elegan yang tidak menghancurkan makna dan semangat Python? Saya kira tidak; jika Anda menggunakan Cython, Anda sudah bisa berhenti membodohi diri sendiri dan beralih ke sesuatu yang kurang canggih seperti C ++ dan C.
- Tulis ulang kemacetan dalam C dan tarik dari Python kesayangan Anda. OK, tapi bagaimana jika saya memiliki seluruh program - ini semua tentang perhitungan dan kemacetan? Xi tidak menawarkan! Saya tidak berbicara tentang fakta bahwa dalam solusi ini Anda perlu tahu bukan hanya satu, tetapi dua bahasa - Python dan C.
Inilah JULIA!
Setelah merenungkan solusi yang ada dan tidak menemukan (tidak dapat memprogram) sesuatu yang baik, saya memutuskan untuk menulis ulang dengan sesuatu yang "lebih cepat". Bahkan, jika Anda menulis "perontok angka" di abad ke-21 dengan dukungan normal untuk array, operasi vektor "di luar kotak", dll. dll, maka pilihan Anda tidak terlalu padat:
- Fortran . Dan jangan tertawa, siapa di antara kita yang tidak menarik BLAS / LAPACK dari bahasa favorit kita? Fortran adalah bahasa yang sangat baik (SI!) Untuk komputasi SCIENTIFIC. Saya tidak mengambilnya dengan alasan bahwa sejak zaman Fortran banyak hal telah ditemukan dan ditambahkan ke bahasa pemrograman; Saya berharap untuk sesuatu yang lebih modern.
- R menderita masalah yang sama dengan Python (vektorisasi).
- Matlab - mungkin ya, sayangnya saya tidak punya uang untuk memeriksa.
- Julia - kuda itu gelap, akan lepas landas, tidak akan lepas landas (dan itu wajar sampai versi stabil 1.0)
Beberapa keuntungan yang jelas dari Julia
- Itu terlihat seperti Python, setidaknya yang sama "tingkat tinggi", dengan kemampuan, jika perlu, turun ke bit dalam angka.
- Tidak repot dengan alokasi memori dan sejenisnya.
- Jenis sistem yang kuat. Jenis ditentukan secara opsional dan sangat tertutup. Suatu program dapat ditulis tanpa menentukan satu jenis - dan jika Anda melakukannya, mereka akan dapat melakukannya dengan cepat. Namun ada nuansa.
- Sangat mudah untuk menulis jenis khusus yang akan secepat jenis bawaan.
- Pengiriman ganda. Anda dapat membicarakan hal ini selama berjam-jam, tetapi menurut saya - ini adalah yang terbaik yang dimiliki Julia, ini adalah dasar dari desain semua program dan, secara umum, dasar dari filosofi bahasa.
Berkat pengiriman ganda, banyak hal ditulis dengan sangat seragam.
Beberapa contoh pengiriman rand() # 0 1 rand(10) # 10 0 1 rand(3,5) # 3 5 .... using Distributions d = Normal() # 0, 1 rand(d) # rand(d, 10) # 10 ...
Yaitu, argumen pertama dapat berupa distribusi (satu dimensi) dari Distribusi, tetapi pemanggilan fungsi akan tetap sama. Dan tidak hanya distribusi (dimungkinkan untuk mengirimkan RNG itu sendiri sebagai objek MersenneTwister dan banyak lagi). Contoh lain (menurut saya, ilustratif) adalah navigasi di DataFrames tanpa loc / iloc.
- 6. Array adalah asli, bawaan. Vektorisasi di luar kotak.
Kontra untuk tetap diam tentang yang akan menjadi kejahatan!
- Bahasa baru Di satu sisi, tentu saja, minus. Dalam sesuatu, mungkin tidak dewasa. Di sisi lain, ia memperhitungkan rake banyak bahasa masa lalu, berdiri "di bahu raksasa", telah menyerap banyak hal menarik dan baru.
- Program cepat tidak mungkin untuk menulis. Ada beberapa hal yang tidak jelas yang sangat mudah diatasi: Anda melangkah menyapu, meminta bantuan komunitas, melangkah lagi ... dll. Ini terutama tipe ketidakstabilan, ketidakstabilan tipe, dan variabel global. Secara umum, sejauh yang saya tahu sendiri, seorang programmer yang ingin cepat menulis dalam Julia melewati beberapa tahap: a) menulis dengan Python. Ini bagus, dan memang begitu, tetapi kadang-kadang akan ada masalah kinerja. b) menulis seperti di C: jenis resep maniak sedapat mungkin. c) secara bertahap memahami di mana perlu (sangat diukur) untuk menentukan jenis, dan di mana mereka mengganggu.
- Ekosistem Beberapa paket mentah, dalam arti bahwa suatu tempat terus-menerus ada sesuatu yang jatuh; beberapa sudah matang, tetapi tidak konsisten satu sama lain (konversi ke jenis lain diperlukan, misalnya). Di satu sisi, ini jelas buruk; di sisi lain, Julia memiliki banyak ide yang menarik dan berani, hanya karena "kita berdiri di atas pundak para raksasa" - kita telah memperoleh pengalaman luar biasa menginjak garu dan "bagaimana tidak melakukannya", dan ini diperhitungkan (sebagian) oleh pengembang paket.
- Array penomoran dari 1. Ha, bercanda, ini tentu saja plus! Tidak, yah, serius, ada apa, dengan indeks apa penomoran dimulai? Anda akan terbiasa dalam 5 menit. Tidak ada yang mengeluh bahwa bilangan bulat disebut bilangan bulat, bukan keseluruhan. Ini semua masalah selera. Dan ya, ambil setidaknya Cormen yang sama sesuai dengan algoritma - semuanya diberi nomor dari satu di sana, dan kadang-kadang tidak nyaman untuk mengulanginya dengan Python sebaliknya.
Nah, mengapa kecepatan?
Sudah waktunya untuk mengingat mengapa semuanya dimulai.
Catatan: Saya aman melupakan Python, jadi tuliskan perbaikan Anda di komentar, saya akan mencoba menjalankannya di laptop saya dan melihat runtime.
Jadi, dua contoh kecil dengan microbenchmark.
Sesuatu vektorMasalah: vektor X 0 dan 1 disuplai ke input fungsi. Anda perlu mengonversinya menjadi vektor 1 dan (-1) (1 -> 1, 0 -> -1) dan menghitung berapa banyak koefisien dari transformasi Fourier dari vektor ini. nilai absolut melebihi batas batas.
def process_fft(x, boundary): return np.count_nonzero(np.abs(np.fft.fft(2*x-1)) > boundary) %timeit process_fft(x, 2000) 84.1 ms ± 335 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
function process_fft(x, boundary) count(t -> t > boundary, abs.(fft(2*x.-1))) end @benchmark process_fft(x, 2000) BenchmarkTools.Trial: memory estimate: 106.81 MiB allocs estimate: 61 -------------- minimum time: 80.233 ms (4.75% GC) median time: 80.746 ms (4.70% GC) mean time: 85.000 ms (8.67% GC) maximum time: 205.831 ms (52.27% GC) -------------- samples: 59 evals/sample: 1
Kami tidak akan melihat sesuatu yang mengejutkan di sini - semua sama, mereka tidak menganggapnya sendiri, tetapi meneruskannya ke program fortran yang dioptimalkan dengan baik.
Sesuatu Non-VektorArray 0 dan 1. diumpankan ke input. Temukan panjang dari unit terpanjang berturut-turut.
def longest(x): maxLen = 0 currLen = 0
function longest(x) maxLen = 0 currLen = 0 # This will count the number of ones in the block for bit in x if bit == 1 currLen += 1 maxLen = max(maxLen, currLen) else maxLen = max(maxLen, currLen) currLen = 0 end end return max(maxLen, currLen) end @benchmark longest(x) BenchmarkTools.Trial: memory estimate: 0 bytes allocs estimate: 0 -------------- minimum time: 9.094 ms (0.00% GC) median time: 9.248 ms (0.00% GC) mean time: 9.319 ms (0.00% GC) maximum time: 12.177 ms (0.00% GC) -------------- samples: 536 evals/sample: 1
Perbedaannya jelas dengan mata telanjang. Tips untuk "menyelesaikan" dan / atau membuat vektor versi versi numpy dipersilakan. Saya juga ingin mencatat bahwa programnya hampir identik. Sebagai contoh, saya tidak mendaftarkan satu jenis pun di Julia (bandingkan dengan yang sebelumnya) - semua sama, semuanya bekerja dengan cepat.
Saya juga ingin mencatat bahwa versi yang disajikan tidak termasuk dalam program akhir, tetapi lebih dioptimalkan; di sini mereka diberikan sebagai contoh dan tanpa komplikasi yang tidak perlu (meneruskan memori tambahan di Julia untuk dilakukan di tempat, dll.).
Apa yang keluar pada akhirnya?
Saya tidak akan menampilkan kode final untuk Python dan untuk Julia: ini adalah rahasia (setidaknya untuk saat ini). Pada saat saya berhenti menyelesaikan versi python, itu berhasil semua tes NIST pada array 16 megabyte karakter biner dalam ~ 50 detik. Pada Julia saat ini, semua tes berjalan pada volume yang sama ~ 20 detik. Mungkin saya bodoh, dan ada ruang untuk optimisasi, dll. dll. Tetapi inilah saya, sebagaimana adanya saya, dengan segala kelebihan dan kekurangannya, dan menurut pendapat saya, itu harus dianggap bukan kecepatan program dalam ruang hampa dalam bahasa pemrograman, tetapi bagaimana saya secara pribadi dapat memprogram ini (tanpa benar-benar blunder).
Mengapa saya menulis semua ini?
Orang-orang di
sini menjadi tertarik; Saya memutuskan untuk menulis ketika saatnya tiba. Di masa depan saya berpikir untuk melewati Julia lebih teliti, dengan contoh menyelesaikan beberapa masalah khas. Mengapa Lebih banyak bahasa, baik dan berbeda, dan biarkan semua orang yang ingin menemukan sesuatu yang cocok untuknya secara pribadi.