Mengapa menggunakan perbandingan alih-alih runtime untuk membandingkan dua algoritma?

19

Saya perhatikan bahwa dalam beberapa makalah penelitian CS, untuk membandingkan efisiensi dua algoritma, jumlah total perbandingan kunci dalam algoritma digunakan daripada waktu komputasi yang sebenarnya. Mengapa kita tidak bisa membandingkan mana yang lebih baik dengan menjalankan kedua program dan menghitung total waktu yang dibutuhkan untuk menjalankan algoritma?

telah
sumber
Selamat datang! Saya harap sebagian besar makalah seperti itu tidak menggunakan runtimes. Saya tahu ada yang melakukannya, terutama di komunitas yang lebih terapan dan ketika sistem yang dipertimbangkan sangat kompleks.
Raphael

Jawaban:

14

Ini sebenarnya adalah masalah mendalam yang memiliki beberapa jawaban metodis dan beberapa pragmatis. Saya berasumsi Anda ingin tahu sesuatu tentang algoritma yang ada. Jika Anda ingin tahu algoritma mana yang bekerja lebih baik pada mesin yang diberikan pada input yang diberikan, silakan dan mengukur runtimes. Jika Anda ingin membandingkan kualitas kompiler untuk algoritma yang diberikan, silakan dan mengukur runtimes. Untuk mempelajari sesuatu tentang algoritma, jangan lakukan itu.

Izinkan saya memberi beberapa alasan mengapa menggunakan runtimes bukan ide yang baik.

  1. Generality
    Runtimes diukur menggunakan satu bahasa dan satu kompiler pada satu mesin memiliki sedikit arti jika Anda mengubah komponen apa pun. Bahkan implementasi yang sedikit berbeda dari algoritma yang sama dapat bekerja secara berbeda karena Anda memicu beberapa pengompilasi di dalam kasus tetapi tidak di yang lain.
  2. Prediksi
    Jadi Anda memiliki beberapa runtime untuk beberapa input. Apa yang dikatakan tentang runtime dari beberapa input lain? Secara umum, tidak ada.
  3. Signifikansi
    Biasanya, Anda tidak akan membandingkan semua input (dengan ukuran tertentu), sehingga segera membatasi kemampuan Anda untuk membandingkan algoritme: mungkin set pengujian Anda memicu kasus terburuk dalam satu dan kasus terbaik dalam algoritme lain? Atau mungkin input Anda terlalu kecil untuk menunjukkan perilaku runtime .
  4. Pengukuran
    Mengukur runtime dengan baik tidak mudah. Apakah ada JIT? Apakah ada pertengkaran, yaitu apakah Anda menghitung waktu bahkan algoritma tidak berjalan? Bisakah Anda mereproduksi persis kondisi mesin yang sama untuk menjalankan lain (dari algoritma lain), khususnya proses dan cache bersamaan? Bagaimana latensi memori ditangani?

Saya harap ini meyakinkan Anda bahwa runtime adalah ukuran yang mengerikan untuk membandingkan algoritma, dan bahwa beberapa metode umum abstrak untuk menyelidiki runtime algoritma diperlukan.

Ke bagian kedua dari pertanyaan. Mengapa kita menggunakan perbandingan atau operasi dasar serupa?

  1. Keterlacakan analitik
    Dengan asumsi Anda ingin melakukan analisis formal, Anda harus dapat melakukannya. Menghitung pernyataan individual sangat teknis, terkadang bahkan sulit; beberapa orang tetap melakukannya (misalnya Knuth). Menghitung hanya beberapa pernyataan - yang mendominasi runtime - lebih mudah. Untuk alasan yang sama, kita sering "hanya" menyelidiki (batas atas) runtime terburuk.

  2. Dominasi
    Operasi yang dipilih mendominasi runtime. Itu tidak berarti bahwa ia berkontribusi paling runtime - perbandingan jelas tidak, misalnya di Quicksort ketika mengurutkan integer berukuran kata. Tetapi mereka dieksekusi paling sering , jadi dengan menghitungnya Anda menghitung seberapa sering bagian algoritma yang paling dieksekusi dijalankan. Akibatnya, runtime asimptotik Anda sebanding dengan jumlah operasi dasar yang dominan. Inilah sebabnya kami merasa nyaman menggunakan notasi Landau dan kata "runtime" walaupun kami hanya menghitung perbandingan.

Perhatikan bahwa dapat berguna untuk menghitung lebih dari satu operasi. Sebagai contoh, beberapa varian Quicksort mengambil lebih banyak perbandingan tetapi lebih sedikit pertukaran daripada yang lain (rata-rata).

Untuk apa nilainya, setelah Anda melakukan semua teori yang Anda mungkin ingin meninjau kembali runtimes untuk memverifikasi bahwa prediksi yang dibuat teori Anda masuk akal. Jika tidak, teori Anda tidak berguna (dalam praktiknya) dan harus diperpanjang. Hirarki memori adalah salah satu hal pertama yang Anda sadari penting tetapi tidak ada dalam analisis dasar.

Raphael
sumber
1
Perlu diingat bahwa analisis formal juga memiliki keterbatasan. Sebagai contoh, kasus rata-rata untuk distribusi input yang tidak seragam seringkali tidak dapat digunakan.
Raphael
10

Ini karena total waktu untuk menjalankan algoritma memiliki ketergantungan pada perangkat keras di mana ia dijalankan bersama dengan faktor-faktor lain. Tidak dapat diandalkan untuk membandingkan dua algoritma jika satu berjalan pada Pentium 4 dan lainnya berjalan pada, katakanlah, Core i7. Bukan hanya ini, tetapi katakanlah Anda menjalankan keduanya di komputer yang sama. Apa yang harus dikatakan bahwa mereka berdua memiliki jumlah waktu prosesor yang sama? Apa yang terjadi jika beberapa proses lain memiliki prioritas lebih tinggi daripada proses dari salah satu algoritma?

Untuk melewati ini, kami memisahkan diri dari keseluruhan waktu ini untuk menyelesaikan, dan bukannya membandingkan berdasarkan pada seberapa baik skala algoritma. Anda mungkin telah memperhatikan notasi seperti O (1) atau O (n ^ 2) di makalah penelitian. Ini mungkin memerlukan sedikit lebih banyak bacaan, jika Anda tertarik lihat notasi O Besar .

Chris Howell
sumber
1
Waktu tayang aktual tergantung pada ukuran dan isi input aktual yang digunakan untuk menjalankan algoritme!
Tsuyoshi Ito
7

Karena jawaban lain menjelaskan mengapa kami menganalisis runtime dalam hal jumlah operasi dasar, izinkan saya menawarkan beberapa alasan mengapa perbandingan adalah metrik yang tepat dari banyak (tidak semua) algoritma pengurutan:

  • untuk banyak algoritma pengurutan jumlah perbandingan mendominasi waktu berjalan, yaitu setidaknya sebanyak perbandingan dilakukan sebagai operasi dasar lainnya
  • perbandingan adalah operasi yang mahal ; berpikir tentang bagaimana rutin penyortiran diimplementasikan di perpustakaan: fungsi sort melewati array elemen dan pointer ke fungsi yang membandingkan dua elemen; dalam panggilan umum dan menunggu fungsi membandingkan untuk mengeksekusi lebih mahal daripada operasi "internal"; karena fungsi ini disediakan oleh pengguna, lebih sulit untuk mengoptimalkannya
  • (ini mungkin atau mungkin bukan alasan yang baik untuk beberapa) kita dapat mengatakan sesuatu yang menarik tentang jumlah perbandingan yang cukup dan perlu untuk mengurutkan urutan; kita tahu bagaimana melakukan ini dalam kasus terburuk dan rata-rata untuk berbagai distribusi, bahkan bagaimana merancang algoritma yang konvergen menjadi optimal ketika dijalankan pada item sampel iid dari distribusi yang tidak diketahui ( Algoritma Peningkatan Diri ); kami tahu bagaimana melakukan ini ketika beberapa perbandingan diberikan secara gratis ( Menyortir dengan Informasi Sebagian )
Sasho Nikolov
sumber
1) "setidaknya perbandingan dilakukan sebagai operasi elementer lainnya" - hanya sampai faktor konstan. 2) "perbandingan adalah operasi yang mahal" - yang mengasumsikan pengaturan generik. Untuk penyortiran bilangan bulat (yang biasanya dianalisis), swap biasanya lebih mahal.
Raphael
Tentu. op tampaknya bingung tentang analisis algoritma secara umum, tidak ingin membawa faktor konstan. Saya berharap fakta bahwa saya berbicara tentang pengaturan umum jelas dari deskripsi - rutin semacam di perpustakaan standar tidak menyortir bilangan bulat
Sasho Nikolov
ditambah karya-karya yang op saw jelas bukan tentang algoritma penyortiran bilangan bulat khusus, tidak ada yang menghitung jumlah perbandingan
Sasho Nikolov
@Raphael Menyortir bilangan bulat kecil bukanlah masalah umum dalam praktiknya. Saya akan bertaruh sebagian besar penyortiran yang terjadi di dunia adalah pada string (dengan panjang tertentu ). Bahkan untuk penyortiran bilangan bulat, saya tidak yakin apakah itu akurat bahwa swap lebih mahal - percabangan adalah operasi yang relatif mahal pada prosesor high-end modern, melihat bahwa prediksi cabang sebagian besar akan sia-sia ketika menyortir.
Gilles 'SANGAT berhenti menjadi jahat'
@Gilles Dalam dirinya sendiri, swap lebih mahal daripada perbandingan integer daripada platform apa pun yang saya tahu. Biaya "sekunder" seperti mispredictions cabang jelas merupakan faktor, yang dampaknya merupakan subjek penelitian yang sedang berlangsung. (Mengenai penggunaan dalam praktik, saya tidak bisa membuat pernyataan yang memenuhi syarat. Namun, saya mengamati bahwa pengelola perpustakaan standar terus meningkatkan algoritma penyortiran yang mereka gunakan untuk tipe data primitif jadi saya berasumsi bahwa mereka melihat banyak penggunaan (ab).)
Raphael