Apa yang Anda sebut ketika Anda mengubah waktu eksekusi fungsi Big O [tertutup]

Katakanlah saya memiliki fungsi yang mengurutkan basis data dalam O(n^2)waktu. Saya ingin melanjutkan refactoring sehingga berjalan dalam O(n log(n))waktu, dan dengan melakukan itu saya akan mengubah cara dasar operasi berjalan, sambil menjaga nilai pengembalian dan input setara.

Apa yang saya sebut kegiatan refactoring ini?

"Mempercepat pemasangan" sepertinya tidak tepat, karena Anda dapat membuat algoritme berjalan lebih cepat tanpa mengubah kecepatan O besar yang dijalankannya.

"Menyederhanakan" juga tampaknya tidak benar.

Apa yang saya sebut aktivitas ini?

Memperbarui

Jawaban terbaik yang bisa saya temukan adalah mengurangi kompleksitas waktu asimpotik.

Biasanya disebut "optimasi kinerja" , tetapi saya tidak akan menyebutnya "refactoring", karena istilah ini biasanya mengacu pada perubahan kode yang tidak mengubah perilaku yang terlihat . Dan perubahan Big-O jelas merupakan sesuatu yang saya sebut perubahan yang terlihat.

dengan melakukan itu saya akan mengubah cara dasar operasi berjalan

Dalam hal ini, pengoptimalan Anda adalah penulisan ulang fungsi tersebut. Tidak setiap pengoptimalan, meskipun perubahan "Besar-O", harus ditulis ulang, kadang-kadang hanya perubahan kecil yang diperlukan untuk mencapai peningkatan seperti itu, tetapi bahkan kemudian, saya enggan menggunakan istilah "refactoring" untuk ini, karena itu cenderung memberi kesan yang salah tentang sifat perubahan.

EDIT: Saya memeriksa daftar refactoring Fowler , dan di antara ini ~ 100 bernama refactorings, yang terakhir disebut "Substitute Algorithm" . Jadi jika kita menganggap ini sebagai referensi kanonik, ada area kecil berwarna abu-abu di mana optimalisasi bentuk yang dideskripsikan dapat disebut jenis khusus refactoring (tapi IMHO bukan tipikal). Perhatikan juga, tujuan Fowler dengan semua refactoring selalu untuk meningkatkan desain dengan fokus pada pemeliharaan dan evolvabilitas kode yang ada tanpa menulis ulang, dan jelas bukan optimasi kinerja.

Saya tidak berpikir ada istilah standar, yang umum digunakan adalah mengoptimalkan meskipun meningkatkan , atau mempercepat juga akan benar membuat klarifikasi bahwa Anda berbicara tentang perubahan kode dan bukan perubahan perangkat keras.

Seperti yang orang lain katakan, "mengoptimalkan" adalah istilah umum untuk meningkatkan kinerja suatu algoritma. Namun, mengoptimalkan sering kali berarti meningkatkan faktor konstan. Jika saya ingin secara ringkas tetapi jelas menyatakan bahwa saya telah mengurangi kompleksitas (waktu) asimptotik, saya akan mengatakan bahwa saya telah "meningkatkan kinerja asimptotik". Kadang-kadang orang akan menggambarkan ini sebagai "meningkatkan skala" tetapi ini sangat ambigu saat ini.

Peringatan : Mengurangi kompleksitas waktu asimptotik tidak harus sama dengan mengoptimalkan dalam konteks praktis . Seringkali algoritma asimtotik tidak optimal digunakan karena pada rentang input program sebenarnya terkena algoritma kurang optimal berkinerja lebih baik.

Ini akan tergantung pada konteks.

"Memperbaiki bug kinerja runtime kuadrat" biasanya apa yang saya lihat. Namun, apakah itu pantas diperbaiki (perubahan kode) tergantung konteks.

Ingatlah bahwa database menyediakan banyak alat untuk meningkatkan kompleksitas waktu. Misalnya, untuk mendapatkan hasil N teratas dari database, katakan saja. Saat mengubah kludge yang tidak efisien menjadi panggilan yang dioptimalkan yang terpasang di dalam, penjelasan tampaknya tidak perlu.

Alasan saya mempertimbangkan algoritma dengan runtime kuadrat untuk mendapatkan tinjauan kode (diskusi) tidak begitu banyak karena lambat (lambat relatif; kuadrat cepat jika dibandingkan dengan eksponensial), tetapi karena intuisi manusia (seperti pelanggan Anda, atau sesama programer) secara bawaan tidak nyaman dengan fungsi perangkat lunak yang menyimpang terlalu jauh dari runtime linear, karena pencampuran harapan dari kehidupan sehari-hari.

Banyak keluhan pelanggan tentang kinerja perangkat lunak termasuk dalam dua kategori ini:

• Seluruh sistem (perangkat lunak dan perangkat keras) ditentukan berdasarkan perkiraan penggunaan. Pekan lalu, semuanya berjalan dengan baik, fungsi tertentu membutuhkan waktu kurang dari 5 detik. Minggu ini, setelah menginstal pembaruan, fungsi yang sama membutuhkan waktu lebih dari 1 menit.

  • Ini adalah perbandingan dengan kinerja yang diperbandingkan sebelumnya. Pelanggan memegang kinerja masa depan untuk tolok ukur absolut dari skala waktu manusia (dari detik ke menit).

• Saya mengirimkan 100 pekerjaan ke sistem. Mengapa perlu 400x waktu untuk diproses, dibandingkan dengan waktu yang dibutuhkan untuk satu pekerjaan?

  • Pelanggan mengharapkan waktu pemrosesan menjadi linier. Bahkan, pelanggan tidak dapat memahami atau menerima bahwa ada tugas yang lebih lambat dari linier.

Untuk alasan ini, pelanggan akan menganggap waktu eksekusi sebagai bug jika keduanya benar:

• Lebih lambat dari linear
• Terlihat (yaitu termasuk dalam rentang waktu manusia (lebih dari detik atau menit) dengan ukuran tugas yang khas)

Argumen sah yang menjelaskan bahwa algoritma runtime kuadrat tidak menimbulkan masalah (yaitu tidak pantas menerima perubahan kode):

• Ukuran tugas yang biasanya ditangani oleh fungsi runtime kuadratik ini agak dibatasi
• Mengingat rentang ukuran yang khas, waktu eksekusi aktual (absolut) masih cukup kecil untuk diberhentikan
• Jika pengguna benar-benar mencoba untuk mengirimkan tugas yang cukup besar untuk dapat dilihat, pengguna akan menerima pesan peringatan tentang waktu yang berjalan lama
• Pengguna sistem semuanya ahli, oleh karena itu mereka tahu apa yang mereka lakukan. Misalnya, pengguna API harus membaca tulisan kecil pada dokumentasi API.

Banyak algoritma yang berguna untuk pengembangan aplikasi tipikal sebenarnya lebih lambat dari linear (kebanyakan O (N log N), seperti dalam penyortiran), oleh karena itu perangkat lunak skala besar sebenarnya akan mencoba untuk mengatasinya, dengan hanya menyortir bagian yang relevan dari data, atau gunakan teknik penyaringan histogram (statistik) yang mencapai efek yang sama.

Ini berlaku untuk pelanggan perangkat lunak, tetapi jika Anda menganggap pengguna perpustakaan perangkat lunak atau fungsi API juga sebagai "pelanggan", maka jawabannya tetap berlaku.

Jika algoritma asli diimplementasikan dengan benar (atau bug mana pun yang tidak relevan) maka "mengubah algoritma" atau "substitusi algoritma" , karena perubahan tersebut berarti Anda melakukan hal itu dengan tepat; mengganti suatu algoritma dengan kompleksitas waktu yang berbeda untuk yang sebelumnya digunakan.

Jika kompleksitas waktu sebelumnya disebabkan oleh bug dalam implementasi (mis. Katakan Anda tidak sengaja mengatur ulang titik awal loop batin pada urutan sehingga apa yang seharusnya O (n) menjadi O (n ² )) maka "memperbaiki bug biaya kuadratik " atau serupa.

Ada tumpang tindih, dalam hal demikian efek pada kode adalah sama jika Anda tahu dari awal bahwa pekerjaan dapat dilakukan dalam waktu O (n) dan waktu O (n ² ) adalah kesalahan, atau jika pertama-tama Anda secara sengaja mengimplementasikannya dalam waktu O (n ² ) dan kemudian menyadari bahwa itu masih akan berfungsi dengan benar tanpa mengatur ulang titik awal, dan dengan demikian menggantikan algoritma O (n) untuk O (n ² ).

Optimalisasi kecepatan dengan perintah / pesanan besar. Meskipun ini adalah bahasa yang secara matematis salah, ia paling baik menyampaikan gagasan tentang Ordo yang sedang diubah.

Meningkatkan skalabilitas. dengar juga.