Algoritma mana yang paling sering digunakan dalam praktik?

19

Algoritma mana yang paling sering digunakan?

Harap tulis satu algoritme per jawaban, usahakan agar jawaban Anda singkat (satu atau dua baris).

ds.algorithms big-list Kaveh
sumber
Kaveh, mungkin Anda harus menunggu tanggapan sebelum memasok begitu banyak? :)
Suresh Venkat
1
@ Suresh: Maaf. :)
Kaveh
3
Paling sering dalam arti apa? (Jumlah program komputer yang berbeda yang mengimplementasikan algoritma? Jumlah perangkat lunak yang diinstal yang menggunakan algoritma? Jumlah eksekusi algoritma? Jumlah data yang diproses dengan menggunakan algoritma? CPU detik digunakan oleh algoritma?) Di mana? (Akademisi, industri, PC rumahan?) Apakah mungkin untuk memperkirakan sesuatu seperti ini; Bisakah kita punya data untuk mendukung jawaban?
Jukka Suomela
1
Pertanyaan itu terlalu kabur seperti yang ditunjukkan Jukka Suomela. Tanpa klarifikasi lebih lanjut, jawabannya tidak akan lebih baik daripada daftar isi buku teks tentang algoritma.
Tsuyoshi Ito
1
Ada sebuah buku baru-baru ini: "Sembilan Algoritma yang Mengubah Masa Depan: Ide Cerdas yang Menggerakkan Komputer Saat Ini" oleh John MacCormick. Lihat press.princeton.edu/titles/9528.html
Alessandro Jacopson

Jawaban:

18

Apakah Fast Fourier Transform masalah algoritmik yang paling sering diselesaikan per hari oleh sistem komputer nyata? Itu harus dekat. Jadi saya akan mencalonkan algoritma FFT Cooley-Tukey .

Aaron Sterling
sumber
Aku seperti ini, FFT diabaikan dalam pendidikan ilmu komputer dasar, tapi itu adalah tentu sebuah algoritma dengan dampak yang luar biasa dalam masyarakat modern kita, dan banyak hal yang modern di sekitar kita berderak FFT sepanjang waktu.
Jukka Suomela
14

Perkalian.

Mungkin salah satu algoritma tertua yang tidak sepenuhnya sepele, dan masalah yang lebih sering diselesaikan daripada FFT.

Jukka Suomela
sumber
Perkalian bukan suatu algoritma, ini adalah masalah dengan banyak masalah yang diselesaikan dengan algoritma yang berbeda: integer ukuran tetap dan floating-point, dilakukan oleh perangkat keras atau perangkat lunak; bignum ukuran variabel (modulo atau tidak), matriks, ...
Gilles 'SO- stop being evil'
Saya merujuk pada rangkaian perkalian perangkat keras dalam CPU modern (untuk bilangan bulat dan angka floating-point; keduanya pada akhirnya tidak berbeda). Pemahaman saya adalah bahwa mereka cenderung "hanya" versi yang sangat cerdik dari pendekatan dasar yang sama - algoritma "perkalian panjang", yang sudah dikenal pada Abad Pertengahan.
Jukka Suomela
Saya pikir pengurangan (perbandingan) digunakan lebih sering daripada perkalian, dan saya tidak bisa melihat alasan mengapa perkalian dihitung sebagai suatu algoritma dan penambahan / pengurangan tidak. Namun, saya tidak tahu apakah ini memenuhi syarat sebagai jawaban.
Tsuyoshi Ito
Ya, penambahan dan pengurangan digunakan bahkan lebih sering daripada multiplikasi - memang, algoritma multiplikasi panjang pada dasarnya mengurangi multiplikasi menjadi tambahan. Namun, saya tidak tahu apakah ada algoritma penambahan / pengurangan tunggal yang bisa kami nominasikan di sini?
Jukka Suomela
@JukkaSuomela: Tambahan dan pengurangan komplemen dua akan menjadi kandidat yang baik.
John Gietzen
13

Algoritma jalur terpendek Dijkstra dan Bellman-Ford . Ada setidaknya 35.000 Sistem Otonomi (AS) aktif di Internet pada tahun 2010. Setiap AS berjalan baik link-state protokol routing (Dijkstra) atau jarak-vector routing yang protokol (Bellman-Ford). Router dalam satu AS biasanya memperbarui tabel mereka secara berkala setiap beberapa menit, misalnya 10.

Dengan demikian, jumlah eksekusi Dijkstra & Bellman-Ford per hari mencapai setidaknya 5 juta. Dan itu hanya dari router.

Kami belum menghitung perhitungan jalur terpendek dari Google Maps dan sejenisnya yang seharusnya dengan mudah diperhitungkan 10 kali lipat. Setengah miliar eksekusi sehari tidak dibuat-buat.

Hung Q. Ngo
sumber
Setengah miliar eksekusi sehari mungkin terdengar sangat banyak, tetapi mari kita ingat bahwa kita memiliki, misalnya, miliaran ponsel di planet ini. Apa yang dilakukan semua hal itu sepanjang waktu? Atau apa yang mereka lakukan selama setiap panggilan telepon? Saya tidak tahu, tetapi dugaan saya adalah mereka paling tidak melakukan lebih banyak FFT daripada jalur terpendek.
Jukka Suomela
8

Quicksort

Kaveh
sumber
14
Omong-omong, apakah benar bahwa quicksort adalah algoritma penyortiran yang paling umum digunakan di dunia nyata? Saya melihat sekilas penerapan fungsi "semacam" tujuan umum dalam beberapa bahasa pemrograman yang umum digunakan. Perl: tampaknya baru-baru ini beralih dari quicksort ke mergesort. Python: menggunakan Timsort (mergesort / sisipan jenis hibrida). Java: dulu mergesort, sekarang Timsort. Database cenderung menggunakan penyortiran eksternal. Apakah quicksort sudah menjadi spesies yang terancam punah?
Jukka Suomela
Saya pikir itu adalah poin yang sangat bagus. Akan lebih bagus jika seseorang dapat mengedit jawabannya.
Juan Bermejo Vega
@ Wang, meskipun poin yang Jukka sebutkan benar, aku tidak melihat alasan untuk mengedit jawabannya.
Kaveh
7

Saya pikir algoritma yang paling banyak digunakan adalah Parity Check (atau mungkin CRC atau semacam kode koreksi kesalahan), karena mereka muncul di setiap akses RAM.

Diego de Estrada
sumber
Juga digunakan setidaknya satu kali untuk setiap paket yang dikirim melalui jaringan berbasis IP apa pun
Claus Broch
5

Algoritma Simplex - bukankah ini masih bersaing dengan metode titik interior terbaik? Jika demikian itu harus banyak digunakan.

Mugizi Rwebangira
sumber
4

k

Secara umum, Anda harus melihat pemenang hadiah Kanellakis untuk ide-ide yang memiliki bobot teoritis dan praktis.

Suresh Venkat
sumber
terima kasih atas tautannya, itu terlihat sangat menarik. Motivasi parsial untuk pertanyaan itu adalah menemukan nama algoritme yang menarik untuk situs tersebut. :)
Kaveh
4

Pencocokan ekspresi reguler dengan konversi ke automata terbatas - Saya percaya fungsi grep di sepanjang baris ini.

Neeldhara
sumber
3

Sulit memikirkan algoritma yang lebih banyak digunakan daripada yang ada dalam implementasi modern TCP : yaitu penghindaran kemacetan , transmisi ulang yang cepat . Meskipun itu tergantung pada bagaimana seseorang menentukan apa yang memenuhi kriteria untuk suatu algoritma ...

Lev Reyzin
sumber
Tetapi bisakah Anda benar-benar menggunakan algoritma TCP lebih sering daripada FFT (yang sudah ada dalam daftar ini)? Jika komputer saya mengirim satu paket IP (TCP atau tidak), bukankah itu biasanya memicu sejumlah besar perhitungan FFT? Biasanya paket-paket ditransmisikan di beberapa titik dengan menggunakan teknologi seperti WLAN, ADSL, dan GSM, dan saya pikir sebagian besar dari mereka menggunakan modulasi yang sangat bergantung pada FFT.
Jukka Suomela
Saya pikir kamu benar.
Lev Reyzin
3

Eliminasi Gaussian Ini masih digunakan dalam praktek kan? Jika tidak diganti dengan apa pun yang paling sering digunakan untuk menyelesaikan sistem linier ...

Mugizi Rwebangira
sumber
2

SHA-1 (dan fungsi hash secara umum). Mungkin mengalahkan sebagian besar algoritma lain dalam hal jumlah eksekusi.

Hung Q. Ngo
sumber
2

Algoritma terkait B + tree digunakan dalam untuk hal-hal basis data

Prabu
sumber
2

Algoritma penjadwalan. Mereka digunakan oleh setiap perangkat pengguna dan server di seluruh dunia. Sejumlah variasi sedang digunakan, saya menemukan banyak referensi untuk "antrean umpan balik bertingkat"

chazisop
sumber
1

Respons ini menafsirkan "paling sering" dalam hal siklus CPU aktual.

Ketika saya belajar komputasi di tahun 70-an, saya ingat pernah membaca bahwa sebagian besar siklus komputer (baca: mainframe) dikhususkan untuk menyortir. Aplikasi bisnis membutuhkan penyortiran yang luas untuk analisis dan pelaporan. Saya tidak membayangkan itu telah banyak berubah, tetapi tentu saja munculnya aplikasi lain - e-mail, pengolah kata, dll .-- harus mengubah campuran. Jenis-jenis itu biasanya jenis yang stabil (bukan Quicksort) karena kebutuhan untuk mengurutkan pada suksesi bidang untuk membuat subsort.

Sebenarnya, algoritma yang paling sering digunakan adalah, tanpa keraguan, apa pun yang dijalankan oleh sistem Windows menunggu proses ketika tidak ada hal lain yang terjadi ;-).

whuber
sumber
1

Sprase Matrix Vector Multiply

... adalah pekerja keras komputasi di balik solusi dari hampir semua sistem linier. Akibatnya dijalankan setiap kali

  • Ilmuwan / insinyur memecahkan persamaan diferensial
  • Ahli statistik menemukan korelasi baru (PCA)
  • Google menjalankan pagerank
  • Ponsel Anda memprediksi lokasi Anda dari GPS, akselerometer, lokasi menara sel
  • Mobil Anda menyesuaikan suspensi Anda dalam gerakan
  • dll ....

Sebagian besar FLOP pada superkomputer atau cluster dihabiskan di dalam vv tikar jarang.

MRocklin
sumber
1

Metode Newton. Ini digunakan untuk menghitung akar kuadrat, untuk divisi komputasi. Dapat digunakan untuk melakukan pemrograman linier. Lebih umum itu adalah kerja keras optimasi (cembung). Ini dapat digunakan untuk menyelesaikan persamaan diferensial dalam Fisika dengan meminimalkan aksi / energi.

Jules
sumber
1

Hashing dan pohon merah-hitam.

Mereka sudah diimplementasikan dalam STL (hash_map, map), dan setiap programmer tahu bahwa wadah seperti itu sangat nyaman setiap kali Anda ingin menyimpan beberapa informasi yang diindeks oleh tipe data yang arbitrer.

zotachidil
sumber
0

Pemrograman Dinamis .

Saya pikir DP digunakan "lebih sering" daripada algoritma lain yang dikutip dalam survei sejauh ini. Saya menyimpulkan "lebih sering" dalam arti seberapa sering konsep algoritma non-sepele diimplementasikan oleh programmer dalam kehidupan nyata, daripada berapa kali implementasi algoritma tertentu dalam dipanggil.

DP serba guna, dan memiliki banyak wajah. Terkadang saya menggunakannya secara tidak sadar dan kemudian menyadari kemudian saya melakukan DP.

Tentu saja, ada hal-hal yang bahkan lebih umum daripada Program Dinamis, tetapi kebanyakan adalah struktur data (array, daftar tertaut, hash).

Hardy Leung
sumber
7
Ini sedikit berbeda dari saran lain karena ini adalah paradigma desain algoritma (mirip dengan serakah atau primal-dual) dan bukan hanya algoritma tunggal.
Jukka Suomela
0

Pencocokan String, digunakan sepanjang waktu dalam perangkat lunak aplikasi dan pada tingkat basis data.

Dalam kasus yang tepat, ada beberapa algoritma yang cukup terlibat (KMP, Boyer-Moore) dengan beberapa yang mencapai runtime yang diharapkan sublinear. Mereka juga menarik untuk dipelajari dari sudut pandang CS.

Pencocokan string perkiraan, yaitu penyelarasan, mungkin bahkan lebih menarik. Anda tahu fitur "koreksi otomatis"? Juga, pencarian dalam data string berisik (mis. DNA) dilakukan dengan menggunakan keberpihakan.

Raphael
sumber