Apakah ada standar untuk membandingkan runtime secara eksperimental?

10

Situasi saya

Saya menulis makalah yang menyajikan modul perangkat lunak yang saya kembangkan dan saya ingin membandingkan runtime-nya dengan modul lain untuk tugas yang sama. Saya mengetahui kelemahan dari eksperimen runtime , tetapi harap anggap telah diberikan bahwa tidak ada jalan lain dalam kasus saya. (Saya dapat dan memang menyimpulkan beberapa properti secara teoritis, tetapi tidak cukup untuk semuanya.)

Skenario spesifik yang ingin saya gunakan untuk pembandingan memiliki dua parameter: kompleksitas  dari masalah dan benih acak  yang menentukan masalah terperinci. Terutama saya ingin menunjukkan ketergantungan pada  . Pergi dengan investigasi awal dan teori, pengaruh pada runtime kecil atau dapat diabaikan. Satu tugas membutuhkan waktu paling lama sepuluh menit untuk diselesaikan.nn rrnr

Pertanyaan aktual

Saya mencari beberapa prosedur yang umum diterima atau dipublikasikan untuk melakukan eksperimen semacam itu atau setidaknya daftar perangkap umum (idealnya dipublikasikan).

Apa yang saya temukan sejauh ini

Tidak ada. Pencarian di internet memunculkan segala macam hasil yang tidak terkait, tetapi saya mungkin tidak menggunakan terminologi yang tepat. Termasuk minimum kata kunci , yang saya tahu merupakan standar yang baik (lihat di bawah), juga tidak membantu.

Bagaimana saya akan melakukannya

  • Jalankan semua percobaan pada mesin yang sama dengan perangkat lunak yang berpotensi mengganggu seperti GUI yang dinonaktifkan sejauh mungkin.

  • Subjek semua modul dengan pilihan skenario yang sama, yaitu dan  r yang sama .nr

  • Untuk setiap skenario, uji modul yang berbeda secara langsung setelah satu sama lain secara acak. Dengan kata lain, pengulangan modul yang berbeda adalah yang paling dalam. Ini harus menghindari bias pada modul yang berbeda karena fluktuasi kinerja mesin yang lambat (misalnya, karena perubahan suhu). Urutan acak harus menghindari bias melalui efek seperti caching atau satu modul selalu diuji setelah yang sama.

  • n

Wrzlprmft
sumber
Mungkin membantu menjelaskan alasan Anda mengapa Anda berpikir "tidak ada jalan lain dalam kasus saya". Tetapi tentu saja, mungkin sebagai pertanyaan terpisah dan tautan di sana karena pertanyaan ini cukup fokus sebagaimana adanya.
Apiwat Chantawibul
@ Billiska: Saya tidak yakin apa yang Anda ingin saya lakukan. Mengapa saya harus menjelaskan alasan saya untuk pendekatan eksperimental dalam pertanyaan terpisah? Saya tidak memiliki pertanyaan tentang ini.
Wrzlprmft
Saya harus tidak setuju dengan Anda yang menjalankan runtime minimum percobaan berulang. Anda tampaknya berpikir mungkin ada outliner saja. Mungkinkah memiliki outliner ke bawah? Lebih umum untuk memeriksa beberapa statistik pada saat yang bersamaan, misalnya rata-rata, median, maks. Siapa tahu mereka dapat menunjukkan sesuatu yang tidak Anda harapkan. Bagaimanapun, ini adalah eksperimen empiris.
Apiwat Chantawibul
2
Ini sangat luas; buku dapat ditulis tentang topik tersebut, misalnya "Panduan untuk Algoritma Eksperimental" karya McGeoch. Seseorang mungkin bahkan mengatakan Anda bertanya, "Apakah ada standar untuk melakukan sains?". Jadi saya tidak yakin ini cukup layak. Apakah Anda memiliki pertanyaan yang lebih spesifik?
Raphael

Jawaban:

2

CC McGeoch "A Guide to Experimental Algorithmics" adalah referensi yang bagus untuk

  • cara mengatur eksperimen pada algoritma,
  • cara menafsirkan dan menggunakan hasil, dan
  • bagaimana cara beralih ke hasil yang lebih bermakna jika perlu.
Raphael
sumber
2

Selain waktu yang berlalu untuk setiap proses, laporkan detik dari mode pengguna & sistem, dan total paket IP, dan total disk I / Os, jika hanya untuk memverifikasi bahwa beberapa angka secara konsisten "rendah" dan memiliki dampak yang dapat diabaikan pada waktu yang berlalu.

Di https://wiki.freebsd.org/BenchmarkAdvice PHK dan lainnya menawarkan saran yang bagus, termasuk

Gunakan ministat untuk melihat apakah angka Anda signifikan. Pertimbangkan untuk membeli "Panduan kartun untuk statistik"

J_H
sumber