Perbandingan metode iterasi: jumlah iterasi vs waktu cpu

14

Saya membandingkan dua metode berulang untuk membalikkan matriks kuadrat acak. Karena matriksnya acak, setiap test case mengambil jumlah iterasi dan waktu yang berbeda yang berbeda. Pertanyaan saya adalah, di atas rata-rata waktu CPU, adalah nilai rata-rata dari iterasi yang diambil oleh kedua metode informasi yang berguna untuk membandingkan metode.

performance benchmarking srijan
sumber
4
Saya menulis ulang pertanyaan Anda agar mudah-mudahan menjadi lebih jelas. Harap pastikan bahwa saya tidak mengubah makna Anda dengan cara apa pun.
Godric Seer
3
@GodricSeer Hasil edit Anda telah meningkatkan pertanyaan saya. Terima kasih
srijan

Jawaban:

12

Secara umum, kedua metode perbandingan kinerja memiliki tempatnya masing-masing.

  • Membandingkan waktu cpu adalah metrik yang paling menarik, karena pada akhirnya Anda benar-benar tertarik dengan metode mana yang lebih cepat. (Tetapi pastikan bahwa kriteria terminasi sebanding; misalnya, bahwa kedua metode menghasilkan perkiraan dengan akurasi yang sama). Kekurangannya adalah ini hanya memberi tahu Anda metode mana (dan yang lebih penting, implementasi mana ) yang lebih cepat pada mesin tempat Anda melakukan tes. Tidak ada jaminan bahwa mesin yang berbeda dengan arsitektur atau perangkat lunak yang berbeda akan memilih pemenang yang sama.

  • Membandingkan angka iterasi , di sisi lain, adalah mesin independen, tetapi berpotensi menyesatkan jika kedua metode memiliki iterasi yang sangat berbeda - dalam hal ini metode dengan iterasi yang lebih sedikit tetapi lebih mahal mungkin tidak disukai (misalnya, metode Newton vs gradien untuk optimasi jika Anda hanya membutuhkan akurasi yang sangat rendah).

Jadi, ya, masuk akal untuk memberikan kedua angka [1], dan saya sering melihatnya dilakukan di publikasi. Ada juga opsi ketiga:

  • Membandingkan jumlah operasi dasar . Jika kedua iterasi terdiri dari jenis operasi yang sama mahal, tetapi memerlukan nomor yang berbeda (mungkin bahkan tidak nomor yang sama di setiap iterasi), masuk akal untuk menghitung jumlah total operasi ini. Dalam kasus Anda, kandidat yang mungkin adalah perkalian matriks-vektor atau matriks-matriks.

[1] Statistik pasti hadir lebih dari beberapa kali; jika Anda menunjukkan cara, jangan lupa untuk memasukkan standar deviasi juga.

Christian Clason
sumber
5
Jangan hanya mengambil cara! Jika Anda memiliki cukup titik uji dengan input acak, plot sebuah distribusi.
Bill Barth
1
@ BillBarth - poin bagus, meskipun itu mungkin tidak selalu layak; tetapi memberikan standar deviasi bersama dengan mean harus selalu dimungkinkan. Faktanya, statistik mana yang disajikan untuk melaporkan kinerja terdengar seperti pertanyaan tindak lanjut yang sangat baik.
Christian Clason
@ BillBarth Anda membuat poin yang bagus. Tapi, saya menggunakan beberapa matriks tes dalam urutan yang meningkat. Untuk kasus seperti itu tidak layak untuk merencanakan distribusi sejak saat itu saya harus merencanakan distribusi untuk semua matriks pengujian lainnya. Itu sebabnya saya ingin mentabulasi mereka. Terima kasih atas komentar anda
srijan
1
@srijan: Anda akan memiliki datanya, Anda harus merencanakan histogram untuk diri sendiri di mana pun Anda bisa. Anda tidak harus menerbitkan semuanya, tetapi saya berjanji kepada Anda bahwa grafik distribusi akan memberi tahu Anda lebih dari sekadar lautan angka atau hanya rata-rata yang pernah ada.
Bill Barth
Saya akan memasukkan waktu eksekusi per iterasi. Karena setiap matriks berbeda, Anda dapat memiliki jumlah iterasi yang berbeda dengan waktu eksekusi yang berbeda. Bersama dengan apa yang dikatakan @Cristian, waktu eksekusi per iterasi akan berguna.
jbcolmenares
4

Saya menemukan jumlah iterasi menjadi metrik yang menyesatkan karena ini menunjukkan "kecepatan" ketika tidak. Untuk contoh sederhana membandingkan beberapa prekondisi berbeda yang menunjukkan perbedaan ini, lihat di sini: http://www.dealii.org/developer/doxygen/deal.II/step_6.html#Possibilityforextensions

Wolfgang Bangerth
sumber
Terima kasih atas jawabannya. Saya tidak dapat memahami 'jumlah iterasi baris ini menjadi metrik yang menyesatkan karena ini menunjukkan "kecepatan" ketika bukan'. Contoh yang Anda sarankan agak sulit untuk saya pahami.
srijan
Apa yang saya katakan adalah bahwa kita sering menyajikan "jumlah iterasi" setara dengan "waktu CPU yang digunakan", yang menyiratkan bahwa metode yang membutuhkan lebih sedikit iterasi juga lebih cepat. Tapi itu tidak benar, seperti yang ditunjukkan oleh angka yang saya tautkan.
Wolfgang Bangerth
Sekarang, saya sepenuhnya mengerti maksud Anda. Sama saya telah mengamati dengan metode newton untuk mendekati kebalikan dari matriks persegi. A s urutan metode meningkat, awalnya waktu cpu serta jumlah iterasi keduanya menurun tetapi seiring meningkatnya pesanan waktu cpu mulai meningkat meskipun jumlah iterasi menurun. Terimakasih banyak atas jawaban Anda.
srijan
2

Seandainya tidak jelas dalam jawaban lain, jumlah iterasi yang baik untuk argumen big-O.

Ini tidak baik untuk kecepatan absolut, karena itu tergantung pada rata-rata waktu per iterasi, yang mungkin berbeda antara metode dengan faktor besar.

Sebagai contoh, ada kecenderungan untuk mengabaikan biaya penghitungan indeks array, dan itu mungkin merupakan sebagian besar dari waktu CPU.

TAMBAH: Juga, seperti yang telah saya tunjukkan di tempat lain, untuk setiap doa metode biasanya ada biaya setup. Kemudian jika matriks biasanya tidak terlalu besar, biaya setup itu sendiri dapat menyebabkan sebagian besar waktu CPU (sehingga menghapusnya akan membuat perbedaan besar dalam kecepatan).

Mike Dunlavey
sumber