Mengapa loop lambat di R?

Saya tahu bahwa loop lambat Rdan saya harus mencoba melakukan berbagai hal dengan cara vektorisasi.

Tapi kenapa? Mengapa loop lambat dan applycepat? applymemanggil beberapa sub-fungsi - itu sepertinya tidak cepat.

Pembaruan: Maaf, pertanyaan itu tidak tepat. Saya bingung dengan vektorisasi apply. Pertanyaan saya seharusnya,

"Mengapa vektorisasi lebih cepat?"

Pengulangan di R lambat karena alasan yang sama dengan bahasa apa pun yang ditafsirkan lambat: setiap operasi membawa banyak bagasi ekstra.

Lihat R_execClosuredieval.c (ini adalah fungsi yang dipanggil untuk memanggil fungsi yang ditentukan pengguna). Panjangnya hampir 100 baris dan melakukan semua jenis operasi - menciptakan lingkungan untuk eksekusi, menetapkan argumen ke lingkungan, dll.

Pikirkan berapa banyak yang terjadi ketika Anda memanggil fungsi di C (dorong args ke stack, jump, pop args).

Jadi itulah mengapa Anda mendapatkan pengaturan waktu seperti ini (seperti yang ditunjukkan joran dalam komentar, sebenarnya bukan applyitu yang cepat; itu adalah loop C internal mean yang menjadi cepat. applyHanya kode R lama biasa):

A = matrix(as.numeric(1:100000))

Menggunakan loop: 0,342 detik:

system.time({
    Sum = 0
    for (i in seq_along(A)) {
        Sum = Sum + A[[i]]
    }
    Sum
})

Menggunakan jumlah: sangat kecil:

sum(A)

Ini sedikit membingungkan karena, secara asimtotik, loop sama baiknya dengan sum; tidak ada alasan praktis mengapa harus lambat; itu hanya melakukan lebih banyak pekerjaan ekstra setiap iterasi.

Jadi pertimbangkan:

# 0.370 seconds
system.time({
    I = 0
    while (I < 100000) {
        10
        I = I + 1
    }
})

# 0.743 seconds -- double the time just adding parentheses
system.time({
    I = 0
    while (I < 100000) {
        ((((((((((10))))))))))
        I = I + 1
    }
})

(Contoh itu ditemukan oleh Radford Neal )

Karena (di R adalah operator, dan sebenarnya membutuhkan pencarian nama setiap kali Anda menggunakannya:

> `(` = function(x) 2
> (3)
[1] 2

Atau, secara umum, operasi yang ditafsirkan (dalam bahasa apa pun) memiliki lebih banyak langkah. Tentu saja, langkah-langkah memberikan manfaat juga: Anda tidak bisa melakukan itu (trik di C.

Tidak selalu terjadi loop lambat dan applycepat. Ada diskusi bagus tentang ini di R News edisi Mei 2008 :

Uwe Ligges dan John Fox. R Help Desk: Bagaimana cara menghindari putaran ini atau membuatnya lebih cepat? R News, 8 (1): 46-50, Mei 2008.

Di bagian "Loops!" (mulai dari hal 48), mereka berkata:

Banyak komentar tentang R menyatakan bahwa penggunaan loop adalah ide yang sangat buruk. Ini belum tentu benar. Dalam kasus tertentu, sulit untuk menulis kode vektor, atau kode vektor mungkin menghabiskan banyak memori.

Mereka lebih lanjut menyarankan:

• Inisialisasi objek baru hingga panjang penuh sebelum loop, daripada meningkatkan ukurannya dalam loop.
• Jangan melakukan hal-hal dalam satu lingkaran yang bisa dilakukan di luar lingkaran.
• Jangan hindari loop hanya untuk menghindari loop.

Mereka memiliki contoh sederhana di mana sebuah forloop membutuhkan waktu 1,3 detik tetapi applykehabisan memori.

Satu-satunya Jawaban atas Pertanyaan yang diajukan adalah; loop tidak lambat jika yang perlu Anda lakukan adalah melakukan iterasi atas sekumpulan data yang menjalankan beberapa fungsi dan fungsi itu atau operasi tidak vektor. Secara for()umum, loop akan berlangsung secepat apply(), tetapi mungkin sedikit lebih lambat daripada lapply()panggilan. Poin terakhir dibahas dengan baik pada SO, misalnya dalam Answer ini , dan berlaku jika kode yang terlibat dalam menyiapkan dan mengoperasikan loop adalah bagian penting dari keseluruhan beban komputasi loop .

Mengapa banyak orang berpikir for()loop lambat adalah karena mereka, pengguna, menulis kode yang buruk. Secara umum (meskipun ada beberapa pengecualian), jika Anda perlu memperluas / menumbuhkan objek, itu juga akan melibatkan penyalinan sehingga Anda memiliki overhead menyalin dan mengembangkan objek. Ini tidak hanya terbatas pada loop, tetapi jika Anda menyalin / menumbuhkan pada setiap iterasi loop, tentu saja, loop akan menjadi lambat karena Anda melakukan banyak operasi salin / tumbuhkan.

Idiom umum untuk menggunakan for()loop di R adalah Anda mengalokasikan penyimpanan yang Anda perlukan sebelum loop dimulai, lalu mengisi objek yang dialokasikan dengan demikian. Jika Anda mengikuti idiom itu, loop tidak akan lambat. Inilah yang apply()mengatur untuk Anda, tetapi itu hanya tersembunyi dari pandangan.

Tentu saja, jika fungsi vektorisasi ada untuk operasi yang Anda implementasikan dengan for()loop, jangan lakukan itu . Demikian juga, jangan gunakan apply()dll jika fungsi vektorisasi ada (misalnya apply(foo, 2, mean)lebih baik dilakukan melalui colMeans(foo)).

Hanya sebagai perbandingan (jangan terlalu banyak membaca!): Saya menjalankan loop (sangat) sederhana di R dan di JavaScript di Chrome dan IE 8. Perhatikan bahwa Chrome melakukan kompilasi ke kode asli, dan R dengan kompiler paket dikompilasi ke bytecode.

# In R 2.13.1, this took 500 ms
f <- function() { sum<-0.5; for(i in 1:1000000) sum<-sum+i; sum }
system.time( f() )

# And the compiled version took 130 ms
library(compiler)
g <- cmpfun(f)
system.time( g() )

@ Gavin Simpson: Btw, butuh 1162 ms di S-Plus ...

Dan kode "sama" dengan JavaScript:

// In IE8, this took 282 ms
// In Chrome 14.0, this took 4 ms
function f() {
    var sum = 0.5;
    for(i=1; i<=1000000; ++i) sum = sum + i;
    return sum;
}

var start = new Date().getTime();
f();
time = new Date().getTime() - start;