Kadang-kadang saya mendengar orang mengatakan bahwa karena kecepatan prosesor dan jumlah memori yang tersedia, efisiensi algoritma dan runtime tidak, dalam praktiknya, menjadi perhatian utama.
Tapi saya membayangkan masih ada area di mana pertimbangan seperti itu tetap sangat penting. Dua yang muncul dalam pikiran adalah perdagangan algoritmik, di mana ribuan transaksi harus dilakukan dalam sepersekian detik, dan pemrograman sistem tertanam, di mana memori dan kekuasaan sering langka. Apakah saya benar tentang contoh-contoh ini? dan bidang apa yang juga menjadi contoh?
algorithms
cocojambles
sumber
sumber
O(n*log(n))algoritma akan selesai lebih cepat pada komputer lama 30 tahun daripadaO(n!)atauO(n*n)pada perangkat keras yang paling mahal saat ini jikancukup besar.O(c * f(n))Di mana konstantacdidasarkan pada inefisiensi perangkat keras. Anda dapat memiliki sistem 1000 kali lebih cepat,nhingga tak terbatas, itu akan menjadi semakin penting. Saya akan memilih yangO(10000 * log(n))bukanO(n)hari apa saja jika saya curiga itunbisa besar.Jawaban:
Kecepatan selalu diminati. Saya kira Anda benar. Berikut adalah beberapa contoh algoritma yang diminati:
Kriptografi
Mencari basis data besar
Menyortir dan menggabungkan
Pencarian teks (non-diindeks), termasuk wildcard
Masalah matematika dengan perhitungan intensif
Simulasi
Aplikasi Data Mining
Animasi
AI
Visi komputer
sumber
Ada beberapa kasus di mana algoritma run-time mungkin tidak menjadi masalah besar, karena kami telah sampai pada titik bahwa Anda dapat dengan mudah menembus algoritma yang berjalan lebih lama dengan perangkat keras yang lebih kuat. Tetapi pasti ada beberapa tempat di mana kecepatan sangat penting.
Secara umum, apa pun yang menggunakan kumpulan data besar akan menjadi masalah. Ketika Anda memiliki sesuatu yang berskala buruk dengan n, dan kemudian Anda membuat jumlah yang sangat besar, Anda memiliki masalah. Saya curiga jika Anda mengunjungi situs beta Computational Science dan mencari-cari sedikit, Anda bisa menemukan banyak masalah yang membutuhkan algoritma yang lebih baik dan lebih cepat. Beberapa area yang saya temui:
Secara umum, komputasi ilmiah umumnya tampaknya merupakan area di mana kompleksitas dari apa yang diprogram menghasilkan peluang untuk perlambatan serius jika algoritme Anda lamban (banyak dari mereka menderita n yang sangat besar). Dan, seperti yang Anda sebutkan, ada aplikasi keuangan. Ketika milidetik dapat menentukan apakah Anda menghasilkan atau kehilangan uang pada perdagangan, algoritma "cukup baik" tidak akan memotongnya jika ada sesuatu yang lebih baik yang dapat dilakukan.
sumber
Ambillah dengan sebutir garam. Lebih banyak daya komputasi pada dasarnya hanya berarti bahwa Anda dapat menjadi jauh lebih besar sebelum secara signifikan melambat. Untuk sebagian besar masalah sehari-hari, ini sekarang cukup besar sehingga Anda tidak perlu peduli. Namun, Anda harus tetap mengetahui kompleksitas algoritme Anda.
Dengan lebih banyak sumber daya yang tersedia, mungkin perlu mengolah lebih banyak data nanti. Hari ini Anda perlu menganalisis file log 10MB dengan 100.000 baris. Dalam setahun Anda mungkin memiliki file log 100GB dengan 1.000.000.000 baris. Jika jumlah data tumbuh lebih cepat dari kekuatan sumber daya, Anda mengalami masalah nanti.
Dengan lebih banyak sumber daya yang tersedia, lebih banyak lapisan ditumpuk satu sama lain. OS, kerangka kerja OS, kerangka kerja pihak ke-3, juru bahasa, dan akhirnya di atas alat Anda sendiri. Semua inefisiensi yang tidak perlu di semua lapisan yang berbeda berlipat ganda. Besok alat Anda dapat berjalan pada OS baru dengan lebih banyak bel dan peluit, yang dengan sendirinya memakan lebih banyak siklus dan lebih banyak memori, menyisakan lebih sedikit untuk Anda.
Jadi untuk menjawab pertanyaan Anda, Anda masih perlu peduli di mana semakin banyak data perlu diolah (cukup contoh yang diberikan dalam jawaban lain), dan di mana Anda tidak menyediakan alat terakhir, tetapi lapisan abstraksi lain untuk alat lain.
sumber
Beberapa tahun yang lalu saya harus menulis sebuah algoritma yang mengurutkan tabung reaksi yang disusun pada
nrak menjadi dua partisi yang berbeda: yaitu satu bagian dari tabung yang 'dipilih' dan sisanya adalah 'tidak dipilih' dan hasil akhirnya adalah bahwa tidak ada rak akan memiliki 'dipilih' dan 'tidak-dipilih' tabung di atasnya (ada beberapa persyaratan tambahan seperti kompresi). Setiap rak berisi maksimal 100 tabung.Algoritma itu akan digunakan untuk menggerakkan robot pemilah tabung di laboratorium farmasi.
Ketika spesifikasi asli diberikan kepada saya, saya dialokasikan di wilayah 1 menit waktu perhitungan untuk memilah sekitar 2.000 tabung karena kami berpikir bahwa kegunaan bijak itu tidak terlalu menyakitkan. Ada persyaratan bahwa jumlah gerakan harus minimal dari semua kombinasi yang mungkin karena robot itu sendiri lambat .
Asumsi implisit adalah bahwa kompleksitas akan eksponensial dengan jumlah tabung. Namun, ketika bekerja pada desain algoritma saya menemukan bahwa ada
O(n)algoritma cepat di mananjumlah rak yang melakukan partisi optimal dari tabung. Hasil dari itu adalah bahwa waktu pengurutan algoritma adalah instan sehingga tampilan pengurutan akan diperbarui secara real time ketika pengguna mengkonfigurasi operasi pengurutan mereka.Bagi saya perbedaan antara pengguna yang duduk selama satu menit setelah setiap perubahan dan memiliki GUI yang responsif langsung adalah perbedaan antara perangkat lunak yang memadai secara fungsional dan perangkat lunak yang menyenangkan untuk digunakan.
sumber
Area lain mencakup banyak jenis pemrosesan sinyal waktu nyata, sistem kontrol umpan balik, dekonvolusi eksplorasi minyak, kompresi video, penelusuran sinar dan rendering bingkai film, sistem realitas virtual, permainan di mana laju bingkai tinggi mungkin merupakan keunggulan kompetitif yang signifikan, dan smartphone serta lainnya aplikasi perangkat seluler, di mana sejumlah besar siklus CPU akan menghabiskan daya tahan baterai pengguna lebih cepat.
Saya cukup terkejut pertanyaan ini bahkan akan ditanyakan, karena untuk setiap superkomputer Top-500 yang pernah dibangun, ada kemungkinan daftar tunggu peneliti yang dapat memaksimalkannya dan berharap untuk besarnya menghitung lebih banyak daya komputasi atau algoritma yang lebih baik untuk memecahkan beberapa masalah (lipat beberapa protein untuk menguraikan kanker, dll.) sebelum mereka pensiun.
sumber
Saya pikir mesin pencari seperti Google dan Bing adalah salah satu area terbesar di mana algoritma kompleks digunakan dan mereka memainkan peran kunci dalam mempercepat hasil dengan relevansi (peringkat halaman) membawa lebih banyak utilitas bagi pengguna.
sumber
Efisiensi algoritma bukan masalah utama saat ini karena kami menggunakan algoritma yang efisien. Jika Anda menggunakan algoritma O (n!), Itu akan lambat pada semua jenis perangkat keras.
sumber
Kompleksitas algoritma menjadi semakin penting seiring dengan meningkatnya jumlah data. Untungnya, solusi umum yang efisien untuk masalah pemrograman umum (terutama mencari dan menyortir) termasuk dalam hampir semua perpustakaan standar bahasa pemrograman modern, jadi biasanya, seorang programmer tidak perlu terlalu khawatir tentang hal-hal ini. The downside adalah bahwa banyak programmer tidak tahu sama sekali apa yang terjadi di bawah tenda dan apa karakteristik algoritma yang mereka gunakan.
Ini menjadi sangat bermasalah karena banyak aplikasi yang tidak benar-benar teruji stres: Orang-orang menulis kode yang bekerja dengan baik untuk set data uji kecil, tetapi ketika dihadapkan dengan beberapa ribu kali lebih banyak data, kode tersebut terhenti. Sesuatu yang bekerja dengan baik untuk sepuluh catatan dengan cepat meledak ketika kumpulan data tumbuh. Contoh dunia nyata: sepotong kode yang seharusnya membersihkan item yang tidak ditautkan ke kategori apa pun lagi menggunakan loop bertingkat tiga, yaitu O (n ^ 3). Dengan hanya 10 catatan dalam database pengujian, ini berarti 1.000 pemeriksaan - dapat dilakukan dengan sempurna, dan tidak menyebabkan penundaan yang nyata. Namun, basis data produksi dengan cepat mengisi sekitar 1000 baris, dan tiba-tiba kode melakukan satu miliar cek setiap kali.
Jadi: Tidak, Anda tidak perlu mengetahui seluk beluk menerapkan segala macam algoritma yang rapi, dan Anda tidak perlu dapat membuat sendiri, tetapi Anda memang perlu pengetahuan dasar tentang algoritma umum, apa yang mereka poin kuat dan lemah adalah, kapan dan kapan tidak menggunakannya, dan Anda perlu menyadari kemungkinan dampak kompleksitas algoritmik, sehingga Anda dapat memutuskan tingkat kompleksitas mana yang dapat diterima.
sumber
Ini bukan pertanyaan tentang domain aplikasi apa yang sensitif terhadap runtime. Setiap program, di mana saja, memiliki kinerja minimum di bawahnya yang secara efektif tidak berharga. Inti dari kompleksitas algoritma adalah bagaimana ia bervariasi dengan bertambahnya ukuran input. Dengan kata lain, area di mana kecepatan sangat penting adalah area di mana Anda berharap harus melampaui tidak hanya ukuran masalah Anda saat ini, tetapi urutan besarnyadari ukuran masalah Anda saat ini. Jika Anda memproses aplikasi pajak warga negara bagian Perancis, tugasnya mungkin besar, tetapi kemungkinan besar ukuran populasi atau kompleksitas pemrosesan satu catatan tidak akan bertambah sepuluh atau seratus kali lipat, jadi apa pun yang berhasil untuk Anda sekarang, mungkin akan terus bekerja. Tetapi jika Anda mencoba untuk membuat sesuatu yang akan lepas landas pada volume internet, kompleksitas algoritma adalah kuncinya: apa pun yang tergantung lebih dari linear atau log-linear pada ukuran input akan menjadi jauh lebih mahal sangat cepat, dan akhirnya kecepatan prosesor tidak bisa bersaing dengan pertumbuhan.
sumber
Di bidang saya (VFX, yang mencakup hal-hal seperti pelacakan jalur, animasi komputer, simulasi partikel, dinamika fluida, pemrosesan gambar, dll.), Kompleksitas algoritme adalah hal yang mendasar. Tidak ada cara apa pun yang beroperasi lebih buruk daripada waktu linearithmic dapat berharap untuk menyelesaikan dalam waktu yang wajar pada input yang biasanya mencapai jutaan simpul, poligon, voxel, partikel, texels, terutama ketika banyak dari hal-hal ini perlu diselesaikan beberapa kali dalam sedetik untuk menyediakan umpan balik interaktif waktu nyata.
Dengan mengatakan bahwa, tidak ada yang kuat dari penekanan pada kompleksitas algoritmik dalam diskusi biasanya di antara rekan-rekan, mungkin karena agak diterima begitu saja dan agak "sederhana". Secara umum diasumsikan jika Anda menulis lacak jalur yang akan beroperasi dalam waktu logaritmik atau lebih baik, dan bahwa struktur data seperti hierarki volume yang terikat sudah dikenal dan relatif sepele untuk diterapkan bagi pembaca. Saya bahkan punya kolega yang terampil yang terus mengatakan bahwa multithreading dan SIMD lebih penting daripada algoritma, dan saya tidak berpikir dia bermaksud bahwa dalam arti bahwa Anda bisa berharap untuk mendapatkan jauh dari paralelisasi semacam gelembung. Saya pikir dia mengatakan itu karena dia menerima begitu saja bahwa kami akan menerapkan algoritma yang masuk akal,
Seringkali banyak fokus hari ini adalah mengambil banyak dari algoritma yang sudah dikenal ini dan menjadikannya lebih baik mengeksploitasi karakteristik perangkat keras seperti cache CPU, register dan instruksi SIMD, GPU, dan banyak core. Sebagai contoh, Intel datang dengan cara baru untuk mengambil BVH lama yang sudah dikenal dan datang dengan konsep "paket ray", pada dasarnya menguji beberapa sinar koheren pada satu waktu dengan semacam traversal pohon rekursif (yang mungkin terdengar seperti itu) akan hadir dengan bagian kompleksitas dan overhead, kecuali lebih dari dibuat oleh fakta bahwa sinar tersebut sekarang dapat diuji secara simultan untuk persimpangan ray / AABB dan ray / segitiga melalui instruksi dan register SIMD).
Hal serupa dengan subdivisi seperti catmull-clark, yang merupakan hal yang sangat mendasar dalam grafis komputer. Tetapi saat ini yang kompetitif dan panas dan sangat efisien adalah implementasi GPU yang mendekati subdivisi CC menggunakan Gregory Patches, seperti yang dipopulerkan oleh Charles Loop dan kemudian diadopsi oleh Pixar. Implementasi CPU yang lebih mudah sekarang agak usang, tidak harus karena digantikan dalam hal kompleksitas algoritmik, tetapi karena digantikan oleh sesuatu yang bermain baik dengan GPU.
Dan itu biasanya banyak tantangan hari ini tidak datang dengan algoritma terbaik dengan cara yang relatif independen dari karakteristik perangkat keras yang mendasarinya. Saya benar-benar berhasil di industri dengan membuat struktur percepatan baru yang secara signifikan mempercepat deteksi tabrakan untuk karakter animasi dan badan lunak lainnya di tahun 90-an menggunakan pendekatan segmentasi hierarkis yang bertentangan dengan indeks spasial, yang membuat saya banyak tawaran pekerjaan, tetapi hari ini tidak begitu mengesankan lagi karena saya menerbitkannya jauh sebelum kami memiliki cache CPU yang mengesankan dan beberapa core dan GPU yang dapat diprogram dan apa yang tidak, dan saat ini saya menggunakan pendekatan yang sama sekali berbeda sebagai akibat dari perubahan signifikan pada perangkat keras yang mendasarinya.
sumber
Saya pernah mengalami masalah di mana algoritma biasanya berjalan di O (n), tetapi dalam keadaan yang jarang dan sangat tidak mungkin akan membutuhkan waktu O (n ^ 3) - keadaan "jarang" adalah direktori yang berisi file dengan nama yang valid dalam satu sistem operasi tetapi tidak yang lain.
Tidak ada yang pernah mengalami masalah. Kemudian satu pelanggan menggunakan strategi untuk memberi nama file yang secara sistematis akan berjalan ke dalam kasus O (n ^ 3), dan dengan beberapa 100 file di sana sistem terhenti secara virtual. Hasilnya adalah bahwa algoritma harus diubah.
sumber
Tiga lagi yang belum disebutkan:
1) Banyak game strategi real time. Lihatlah mereka yang memiliki unit yang tidak dapat berbagi posisi. Perhatikan apa yang terjadi pada perintis jalan ketika sekelompok besar unit bergerak melalui medan terbatas. Saya belum menemukan permainan tanpa masalah besar karena ini tidak cukup daya CPU yang tersedia.
2) Banyak masalah optimasi. (Sunting: Karena saya menulis jawaban ini, saya telah mencapai satu. Tujuan saya adalah untuk memangkas jalur yang redundan sehingga semua node terhubung dengan bobot minimum dari jalur penghubung. Pendekatan asli saya bekerja dengan cukup baik sampai saya memindahkan lebih banyak pemangkasan). untuk rutin itu, maka saya menyadari itu 2 ^ n. Sekarang n ^ 2 meskipun itu kadang-kadang dapat menghasilkan hasil yang sedikit tidak optimal.)
3) Hal-hal yang harus beroperasi pada data dalam jumlah besar secara realtime. Pertimbangkan sebuah DVD: Anda biasanya mendapatkan 2 jam video dalam 4.7gb. Pertimbangkan file video tipikal pada resolusi yang sama: Video 2 jam itu biasanya akan berukuran di bawah 1gb. Alasan untuk ini adalah ketika spec DVD diletakkan Anda tidak bisa membuat DVD player dengan harga terjangkau yang bisa memecahkan kode format yang lebih modern dengan cukup cepat.
sumber
Ya, aplikasi apa pun yang biasanya dijalankan pada superkomputer ( daftar mesin terbesar ) memenuhi syarat. Ini beragam, tetapi subkelas besar dari mereka adalah simulasi fisika:
Ini hanya bagian atas topik kepala saya, tetapi baca saja daftar superkomputer yang berbeda dan sadari bahwa masing-masing dari ini dibangun untuk memungkinkan beberapa jenis komputasi yang tidak mungkin dilakukan tanpa mesin raksasa seperti itu.
Dan, setelah Anda melihat bahwa kita benar-benar membutuhkan mesin ini, sadari berapa banyak biaya yang bisa dihemat, hanya dengan mempercepat aplikasi ini hingga 10% . Setiap optimasi kode-kode ini secara langsung meningkatkan jumlah hasil yang bisa kami dapatkan dari mesin ini.
sumber