Ini adalah tindak lanjut dari Seberapa lambat sebenarnya Python? (Atau seberapa cepat bahasa Anda?) .
Ternyata agak terlalu mudah untuk mendapatkan speedup x100 untuk pertanyaan terakhir saya. Bagi mereka yang telah menikmati tantangan tetapi menginginkan sesuatu yang lebih keras di mana mereka benar-benar dapat menggunakan keterampilan tingkat rendah mereka, inilah bagian II. Tantangannya adalah untuk mendapatkan speedup x100 untuk kode python berikut seperti yang diuji di komputer saya.
Untuk membuatnya lebih sulit, saya menggunakan pypy kali ini. Waktu saat ini bagi saya adalah 1 menit dan 7 detik menggunakan pypy 2.2.1.
Aturan
- Orang pertama yang mengirimkan kode yang dapat saya jalankan, sudah benar dan x100 kali lebih cepat di komputer saya akan diberikan hadiah 50 poin.
- Saya akan memberikan penghargaan kepada kode tercepat setelah seminggu.
import itertools
import operator
import random
n = 8
m = 8
iters = 1000
# creates an array of 0s with length m
# [0, 0, 0, 0, 0, 0, 0, 0]
leadingzerocounts = [0]*m
# itertools.product creates an array of all possible combinations of the
# args passed to it.
#
# Ex:
# itertools.product("ABCD", "xy") --> Ax Ay Bx By Cx Cy Dx Dy
# itertools.product("AB", repeat=5) --> [
# ('A', 'A', 'A', 'A', 'A'),
# ('A', 'A', 'A', 'A', 'B'),
# ('A', 'A', 'A', 'B', 'A'),
# ('A', 'A', 'A', 'B', 'B'),
# etc.
# ]
for S in itertools.product([-1,1], repeat = n+m-1):
for i in xrange(iters):
F = [random.choice([-1,0,0,1]) for j in xrange(n)]
# if the array is made up of only zeros keep recreating it until
# there is at least one nonzero value.
while not any(F):
F = [random.choice([-1,0,0,1]) for j in xrange(n)]
j = 0
while (j < m and sum(map(operator.mul, F, S[j:j+n])) == 0):
leadingzerocounts[j] +=1
j += 1
print leadingzerocounts
Outputnya harus sama dengan
[6335185, 2526840, 1041967, 439735, 193391, 87083, 40635, 19694]
Anda harus menggunakan seed acak dalam kode Anda dan generator nomor acak apa pun yang cukup baik untuk memberikan jawaban yang dekat dengan yang di atas akan diterima.
Mesin Saya Pengaturan waktu akan dijalankan pada mesin saya. Ini adalah instalasi ubuntu standar pada Prosesor Delapan Core AMD FX-8350. Ini juga berarti saya harus dapat menjalankan kode Anda.
Penjelasan kode
Kode ini berulang pada semua larik S dengan panjang n + m-1 yang dibuat untuk -1s dan 1s. Untuk setiap larik S, sampel 1000 larik acak non-nol F dengan panjang n terdiri dari -1,0 atau 1 dengan probabilitas 1/4, 1/2, / 14 untuk mengambil masing-masing nilai. Ini kemudian menghitung produk dalam antara F dan setiap jendela dengan panjang S sampai menemukan produk dalam yang tidak nol. Ia menambahkan 1 leadingzerocounts
pada setiap posisi itu menemukan nol produk dalam.
Status
Perl . 2,7 kali perlambatan oleh @tobyink. (Dibandingkan dengan pypy, bukan cpython.)
J . 39 kali percepatan oleh @Eelvex.
- C . 59 kali dipercepat oleh @ace.
- Julia . 197 kali lebih cepat tidak termasuk waktu mulai dengan @ satu menit lagi. 8,5 kali mempercepat termasuk waktu start up (lebih cepat menggunakan 4 prosesor dalam hal ini dari 8).
- Fortran . 438 kali dipercepat oleh @ semi-ekstrinsik.
- Rpython . 258 kali dipercepat oleh @primo.
- C ++ . 508 kali dipercepat oleh @ilmale.
(Saya berhenti menghitung waktu perbaikan baru karena mereka terlalu cepat dan iters terlalu kecil.)
Itu menunjukkan bahwa waktu di bawah satu detik tidak dapat diandalkan dan juga beberapa bahasa memiliki biaya awal. Argumennya adalah bahwa jika Anda ingin menyertakan Anda juga harus memasukkan waktu kompilasi C / C ++ dll. Berikut adalah timing untuk kode tercepat dengan jumlah iterasi meningkat menjadi 100.000.
- Julia . 42 detik dengan @ satu menit lagi.
- C ++ . 14 detik oleh @GuySirton.
- Fortran . 14s oleh @ semi-ekstrinsik.
- C ++ . 12s oleh @ilmale.
- Rpython . 18-an oleh @primo.
- C ++ . 5d oleh @Stefan.
Pemenangnya adalah .. Stefan!
Tantangan tindak lanjut diposting. Seberapa tinggi Anda bisa pergi? (Tantangan coding + algoritma) . Yang ini lebih sulit.
sumber
Jawaban:
C ++ bit magic
~ 16ms multithreaded, 56ms singlethreaded. ~ 4000 speedup.
(speedup didasarkan pada kode multithreaded pada i7-2820QM saya dan 1 menit 9 detik yang disebutkan dalam pertanyaan. Karena sistem OP memiliki kinerja single threaded yang lebih buruk daripada CPU saya, tetapi kinerja multi-threaded yang lebih baik saya berharap angka ini akurat)
Bagian multithreaded cukup tidak efisien karena pemijahan benang. Saya mungkin bisa melakukan yang lebih baik dengan memanfaatkan pustaka pekerjaan kustom saya tetapi yang satu memiliki bug di bawah sistem unix .. Untuk penjelasan dan kode yang hampir sama tanpa memasukkan threading ke https://codegolf.stackexchange.com/a/26485/20965 .
sunting
Saya memberi masing-masing utas itu sendiri RNG dan mengurangi panjang bit menjadi 32 yang mengurangi runtime oleh beberapa ms.
Output sampel:
sumber
C ++
x150x450x530Alih-alih array saya menggunakan bit (dan dark magic).
Terima kasih @ace untuk fungsi acak yang lebih cepat.
Bagaimana cara kerjanya: bit ke-15 pertama dari integer
s
mewakili arrayS[15]
; nol mewakili -1, yang mewakili +1. ArrayF
dibuat dengan cara yang sama. Tetapi dengan dua bit untuk setiap simbol.Menyebabkan
S
danF
memiliki representasi yang berbeda saya harus interleaveS
dengan dirinya sendiri agar dapat dibandingkanF
.F
)F
)Sekarang kita cukup menggunakan Carnot untuk menghitung produk dalam. Ingat bahwa satu variabel hanya dapat mengasumsikan nilai 00 atau 11
0. 00 = 11 (-1 * -1 = +1)
0. 01 = 10 (-1 * 0 = 0)
0. 10 = 01 (-1 * 0 = 0)
0. 11 = 00 (-1 * +1 = -1)
1. 00 = 00 (+1 * -1 = -1)
1. 10 = 10 (+1 * 0 = 0)
1. 01 = 01 (+1 * 0 = 0)
1. 11 = 11 (+1 * +1 = +1)
Sepertinya bukan untukku. :)
Jumlah yang ada hanyalah permainan shift dan mask, tidak ada yang benar-benar rumit.
Di sini keluaran sampel:
Program ini telah dikompilasi dengan:
pada Fedora 20 dengan gcc 4.8.2 Cpu adalah i7 8core.
Mungkin saya bisa mendapatkan beberapa parameter kompiler tweaker ms.
Sementara ini adalah waktu solusi OP pada mesin saya:
Sunting:
Hanya menambahkan openmp dan mengubah urutan untuk saya mendapatkan x3, yang mengarah ke peningkatan kinerja x450 terhadap kode OP. : D Dalam hal ini
leadingZero
array harus berupa atom. Global acak ... acak, mereka akan lebih acak.perlu menambahkan
-fopenmp
ke flag kompilerSunting: 2 Sebagai suggester oleh user71404 Saya mengubah fungsi sumOnes dan sumArray dan sekarang sangat cepat.
Dengan openmp lebih lambat, menyebabkan atom menambah terlalu banyak overhead.
Tanpa atom bahkan lebih cepat, tetapi saya mendapatkan hasil yang salah.
2137992 1147218 619297 321243 155815 70946 32919 15579
Untuk memahami sumArray pertimbangkan bahwa mewakili 16 bit dan array 8 angka.
00 tidak memiliki 1 dan mewakili -1
01 dan 10 memiliki satu 1 dan mewakili 0
11 memiliki dua 1 dan mewakili 1
Sehingga built-in menghitung jumlah bit yang ditetapkan ke 1 [ http://en.wikipedia.org/wiki/ Hamming_weight] dan untuk setiap grup kami menghapus 1. Cool.
sumOnes hanyalah ilmu hitam.
Di sini kompilasi flag dan kode terbaru.
gcc -std = c ++ 11 -mfpmath = sse -O3 -flto -march = asli -funroll-loop -Wall -lstdc ++
sumber
inline int32_t sumOnes(int32_t v) { /* 0xAAAA == 0b1010 1010 1010 1010 */ return !! (0xAAAA & (v ^ ~(v << 1))); } inline int32_t sumArray(int32_t v) { return __builtin_popcount(v) - 8; }
ini disarankan oleh @ user71404Julia: 0,7 detik, 120x lebih cepat
Seperti yang ditunjukkan oleh user20768, port langsung dari kode ke Julia sekitar dua kali lebih cepat dari PyPy. Tetapi kita dapat melakukan jauh lebih baik dari itu.
Anda dapat menjalankan ini menggunakan
julia -p 8 -e 'require("golf.jl");main()'
(8 adalah jumlah proses, Anda mungkin ingin bermain dengannya). Pada pra-rilis terbaru Julia ini membutuhkan 0,7 vs 1m22 untuk PyPy.Jika Anda memiliki cukup inti di komputer Anda, dan mungkin memutar beberapa instance AWS, Anda harus dapat mencukur lagi :)
sumber
C, 1.210-an
Dengan kode OP menjalankan 1m45.729 di mesin saya.
Kompilasi:
Terima kasih khusus: @dyp untuk flag kompilasi dan ide-ide untuk optimisasi.
Output sampel:
sumber
-march=native -fwhole-program -fstrict-aliasing -ftree-vectorize
Btw. Saya turun ke <4 s dengan menggunakan beberapa C ++ 11 termasuk MT19937 plus auniform_int_distribution
.F
.n
sama dengan8
, Anda mungkin dapat menggunakan AVX (atau 2 * SSE) untuk menghitung dotproduct denganS
penyimpanan yang tepat .smmintrin.h
)Perl
Ini tidak mendekati secepat solusi C, tetapi saya kira cukup cepat untuk bahasa yang ditafsirkan tingkat tinggi. Ini mencukur sekitar 40% dari waktu berjalan implementasi Python.
Algoritma :: Combinatorics tersedia di Ubuntu (
sudo apt-get install libalgorithm-combinatorics-perl
). Modul lain yang digunakan adalah modul inti Perl, jadi harus sudah diinstal sebagai bagian dari instalasi dasar Ubuntu.sumber
0..N-1
berkisar pada yang terakhirmap
, bukan? Apakah kamu lupause warnings
? :-) Meskipun logika dalam OP membingungkan, jendela geser tidak pernah sampai ke elemen terakhirS
.warnings
memungkinkan elemen yang hilang diperlakukan sebagai nol.N-1
meningkatkan ini. Dan itu benar-benar meningkatkan kecepatan sangat sedikit - sekarang sekitar 40% lebih cepat daripada implementasi Python.any
atau dapat ditemukan di List :: MoreUtils, yang walaupun bukan modul inti adalah salah satu modul CPAN yang paling umum digunakan.Julia: 4.66x lebih lambat!
Saya benar-benar mulai meragukan statistik di situs web mereka ...
Perhatikan bahwa kode Julia berikut ini secara efektif merupakan transkripsi langsung dari kode Python OP tanpa optimisasi apa pun. Saya menggunakan
time()
fungsi ini untuk mengecualikan waktu startup Julia yang lambat ...Julia: 5 m 32,912 dtk
Kode OP dalam PyPy: 1 m 11,506 dtk
Output Julia:
sumber
RPython 0.187s (258x lebih cepat)
Sumber Asli dengan PyPy2.2.1: 1m 6.718s
Sekarang dengan threading, dukungan kembali untuk standar Python telah dibatalkan. Jumlah utas pekerja dapat ditentukan sebagai parameter baris perintah, standarnya adalah dua.
RPython adalah subset terbatas dari Python, yang dapat diterjemahkan ke C dan kemudian dikompilasi menggunakan RPython Toolchain . Tujuannya adalah untuk membantu dalam menciptakan penerjemah bahasa, tetapi juga dapat digunakan untuk menyusun program-program sederhana seperti yang di atas. Sebagian besar fitur 'pelamun' dari Python, seperti
itertools
atau bahkanmap
tidak tersedia.Untuk mengkompilasi, buat klon lokal repositori pypy saat ini , dan jalankan yang berikut:
Eksekusi yang dihasilkan akan diberi nama
convolution-c
atau serupa di direktori kerja saat ini.Saya telah parameterkan variabel input, sehingga program harus dijalankan sebagai:
untuk mencocokkan kode sampel.
Catatan Implementasi
S in itertools.product([-1,1], repeat = n+m-1)
menjadiS in xrange(1<<n+m-1)
, menafsirkanS
sebagai bit map: [0
,1
] → [-1
,1
]Demikian juga,
F
juga peta bit, dengan masing-masing dua bit mewakili nilai tunggal:[
00
,01
,10
,11
] → [-1
,0
,0
,1
]Tabel kebenaran digunakan untuk mencari produk, daripada melakukan mulitplikasi.
Karena bilangan bulat bertanda 32-bit digunakan,
n
mungkin tidak lebih besar dari 15, dann+m
tidak lebih besar dari 31. Dukungan bilangan bulat sewenang-wenang dapat dicapai denganrpython.rlib.rbigint
modul, jika perlu.Iterasi pertama dari loop titik-produk tidak terbuka, dan dikombinasikan dengan uji nolitas
F
.PRNG homebrew digunakan, sumber terdaftar. Penulis makalah ini menunjukkan periode 2 32 -1, dan mengklaim bahwa ia lulus semua tes Diehard kecuali satu, walaupun saya belum secara pribadi mengkonfirmasi hal ini.
Benih acak berubah setiap milidetik, yang memungkinkan menggunakan stempel waktu. Selain itu, setiap pekerja memasang
xor
id proses mereka dengan nilai ini, untuk memastikan bahwa mereka masing-masing memiliki seed yang berbeda.Contoh waktu
2 utas pekerja:
4 utas pekerja:
8 thread pekerja:
Sumber asli OP:
Waktu untuk 100000 iterasi:
sumber
Julia: 1 menit 21,4 detik (lebih cepat 2,2x) (modifikasi kode Arman)
Kode op dalam PyPy: 3 mnt 1.4 dtk
Keduanya dilakukan dalam REPL, tidak termasuk waktu untuk memuat paket.
Ada beberapa masalah dengan kode Arman membuatnya sangat lambat: Menggunakan banyak fungsi anonim dan fungsi urutan yang lebih tinggi tidak perlu. Untuk menguji apakah semua vektor F adalah nol, mengapa tidak hanya menulis semua (F == 0) alih-alih semua (x-> x == 0, F)? Ini lebih pendek, dan seribu kali lebih cepat.
Itu juga menggunakan jumlah (peta (*, x, y)) sebagai produk titik bukan hanya titik (x, y). Versi pertama 650 kali lebih lambat untuk vektor 10k ganda. Dan fungsi titik produk diimplementasikan sebagai untuk loop di Julia murni.
Juga, pemahaman array lambat. Lebih baik menulis [0,1,0, -1] [rand (1: 4, n)] daripada [[-1 0 0 1] [rand (1: 4)] untuk j = 1: n] .
Akhirnya, variabel global adalah juju buruk di Julia. Julia hanya cepat jika Anda menulis kode sedemikian rupa yang memungkinkan JIT dan ketik inferensi untuk bekerja. Sebagian besar dari ini adalah stabilitas tipe: Compiler harus dapat memastikan bahwa tipe variabel tidak akan berubah saat berada di dalam loop, misalnya.
sumber
Nimrod
Contoh output:
Nimrod mengkompilasi ke C, oleh karena itu pilihan kompiler C untuk hal-hal backend juga.
Menggunakan dentang, kompilasi dengan:
Menggunakan gcc, kompilasi dengan:
Hapus
--passc:-flto
jika Anda memiliki kompiler C lama yang tidak mendukung KPP. Hapus--cc=...
opsi jika Anda baik-baik saja dengan pilihan default untuk kompiler C. Kode membutuhkan Nimrod 0.9.4 atau 0.9.5 .Pada quadcore iMac saya (2,66 GHz core i5), kode ini berjalan sekitar 0,15 detik dengan gcc 4,9, 0,16 detik dengan dentang, dibandingkan dengan 88 detik untuk PyPy 2.2.1 (yaitu percepatan 500 kali). Sayangnya, saya tidak memiliki akses ke mesin dengan lebih dari empat core yang juga telah menginstal PyPy atau di mana saya dapat dengan mudah menginstal PyPy, meskipun saya mendapatkan sekitar 0,1 detik (dengan banyak suara pengukuran) pada AMD 64-core Opteron 6376 1.4 GHz (menurut / proc / cpuinfo) dengan gcc 4.4.6.
Implementasi mencoba untuk setia pada kode asli daripada mengoptimalkan kode dengan biaya keterbacaan, sementara tidak meninggalkan optimasi yang jelas. Yang cukup menarik, rekursi ekor
initVecRand()
sedikit lebih cepat daripada loop dengan instruksi istirahat dengan gcc dan dentang. Membuka gulungan secara manual satu iterasi dariconvolve
loop tes di dalam loop utama juga menghasilkan percepatan, mungkin karena prediksi cabang yang lebih baik.sumber
Jawa
Saya menerjemahkan solusi C ++ di atas ke Java:
Di mesin saya, saya mendapatkan output berikut untuk program java:
Program OPs berjalan sekitar 53 detik di mesin saya:
Program c ++ dijalankan hanya sekitar 0,15 detik:
Itu sekitar 2,5x lebih cepat dari solusi java yang sesuai (saya tidak mengecualikan VM startup). Solusi java ini sekitar 142x lebih cepat dari program yang dijalankan dengan PyPy.
Karena saya tertarik secara pribadi, saya menetapkan
iters
ke 100_000 untuk Java dan C ++ tetapi faktor 2.5 tidak berkurang untuk Java jika ada yang lebih besar.EDIT: Saya menjalankan program pada PC Linux 64bit Arch.
EDIT2: Saya ingin menambahkan bahwa saya mulai dengan terjemahan kasar dari kode python:
Program ini berjalan sekitar 3,6 detik:
Yaitu sekitar 14 kali lebih cepat dari solusi PyPy. (Memilih fungsi acak standar daripada fungsi fastRandom mengarah ke waktu eksekusi 5 detik)
sumber
Python 3,5 + numpy 1,10.1, 3,76 detik
Tes dijalankan di Macbook Pro saya. Kode OP memakan waktu ~ 6 menit pada mesin yang sama.
Alasan saya menjawab pertanyaan ini sebenarnya adalah karena saya tidak memiliki 10 reputasi dan tidak dapat menjawab Bagian I :-p
Selama beberapa hari terakhir, saya telah mencoba mencari tahu bagaimana melakukan konvolusi besar secara efisien dengan numpy (tanpa mengandalkan paket pihak ketiga, bahkan scipy). Ketika saya menemukan serangkaian tantangan selama penelitian saya, saya memutuskan untuk mencobanya. Saya mungkin terlambat datang ke game ini, tetapi ini adalah usaha saya menggunakan Python 3.5 dan numpy 1.10.1.
Saya pra-komputasi array S dan F, dan meratakan array S sambil melakukan konvolusi, yang (berdasarkan percobaan saya) dapat mengambil keuntungan dari kecepatan np.convolve. Dengan kata lain, karena saya tidak menemukan rutin konvolusi vectorized, saya memalsukan vektorisasi kode dengan meratakan seluruh array dan berharap np.convolved akan melakukan vektorisasi di bawah tenda untuk saya, yang sepertinya berfungsi. Catatan saya menggunakan mode = 'sama' dan memangkas elemen memimpin dan mengekor yang tidak berguna.
Di Macbook Pro saya, hasil tes memberikan 3,76 detik . Ketika saya menjalankan kode OP (dimodifikasi ke Python 3.5), saya mendapat sekitar 6 menit . Percepatan sekitar 100 kali.
Salah satu kelemahannya adalah karena array S dan F disimpan, kebutuhan memori dapat menjadi masalah jika ukurannya terlalu besar.
Saya menggunakan metode yang sama untuk Bagian I dan saya mendapat speedup ~ 60-100x di laptop saya.
Ketika saya melakukan semua yang ada di Macbook Pro saya, jika seseorang dapat menguji kode saya dan memberi tahu saya cara kerjanya di komputer Anda, saya akan sangat menghargainya!
sumber
J,
130x~ 50x speedup?Waktu pada debian acak:
Saya pikir ada ruang untuk perbaikan.
sumber
pypy
, bukanpython
, itulah sebabnya skrip Anda tampaknya memberikan kecepatan 130x.C ++: x200 (4-core i7, harus diubah ke x400 pada 8-core)
Mencoba untuk solusi C ++ 11 yang lebih mudah (Diuji dengan VS 2012, gcc dan dentang) dengan paralelisasi.
Untuk mendapatkan ini untuk dikompilasi dan dijalankan di Linux dengan gcc 4.8.1:
Di Linux kita juga perlu
std::launch::async
memaksa banyak utas. Saya melewatkan itu di versi sebelumnya.Di Visual Studio (2012+) ini seharusnya hanya berfungsi tetapi buat rilis untuk waktu ...
Pada dual core i3 lama saya ini berjalan dalam ~ 0,9 detik. Pada quad core i7 saya ini adalah 0,319 vs pypy 66 detik.
Pada 8-core i7 ini harus dalam kisaran speedup x400. Beralih ke array gaya C akan mempercepatnya tetapi saya tertarik untuk tetap menggunakan wadah C ++. Bagi saya itu menarik untuk melihat speedup yang bisa Anda dapatkan sambil tetap relatif dekat dengan domain masalah dan pada tingkat yang relatif tinggi, sesuatu yang saya pikir C ++ sangat bagus. Yang juga perlu diperhatikan adalah relatif mudahnya paralleization menggunakan konstruksi C ++ 11.
Solusi bit @ ilmale sangat keren dan bekerja untuk -1/1/0. Satu juga bisa melempar SSE ini dan mungkin mendapatkan speedup yang signifikan.
Di luar paralelisasi ada "trik" lain di sana yang mengurangi jumlah penjumlahan. Contoh hasil: 6332947 2525357 1041957 438353 193024 87331 40902 19649
sumber
Fortran: 316x
Oke, Fortran: Saya sudah mempercepatnya hingga
106x155x160x316x saat menggunakan Xorshift RNG dan OpenMP pada CPU 4 core i7. Selain itu, tidak ada trik besar. Untuk iterator untuk membangun S, saya hanya menggunakan representasi biner dari integer 16-bit i. Anda akan perhatikan bahwa selain dari inline RNG dan "iterator" / pemetaan dari i ke S, kodenya sama tingginya dengan kode Python.Sunting: menghapus "jika" di Xorshift, sekarang menggunakan "r = abs (w / ...)" alih-alih "r = w / ...". Mulai dari 106x hingga 155x.
Sunting2: Ini menghasilkan 15x angka acak sebanyak solusi C ++. Jika seseorang memiliki solusi nol-overhead untuk mengubah int acak menjadi array 0s dan 1s di Fortran, saya dengar. Maka kita bisa mengalahkan C ++ :)
Sunting3: Suntingan pertama memperkenalkan bug, seperti yang ditunjukkan Lembik. Ini sudah diperbaiki sekarang, dengan sedikit peningkatan pada speedup. Saya akan mencoba menggunakan saran oleh Eelvex untuk mendapatkan lebih banyak speedup.
Sunting4: Pembuatan profil menunjukkan bahwa mengonversi ke nyata dan kembali ke integer dengan nint () lambat. Saya mengganti ini dengan satu divisi integer melakukan penskalaan dan pembulatan, pergi dari 160x ke 316x speedup.
Kompilasi dengan:
Contoh output:
Kode OP:
sumber