Apakah algoritma (dan efisiensi secara umum) menjadi kurang penting?

29

Karena membeli daya komputasi jauh lebih terjangkau daripada di masa lalu, apakah pengetahuan tentang algoritma dan menjadi efisien menjadi kurang penting? Sudah jelas bahwa Anda ingin menghindari perulangan tanpa batas, jadi, tidak semuanya berjalan. Tetapi jika Anda memiliki perangkat keras yang lebih baik, dapatkah Anda memiliki perangkat lunak yang lebih buruk?

efficiency Feora Quora
sumber

2

"Ya dan Tidak"!

vzn

4

Sekarang sudah ada pesawat, dan pengiriman trans-Atlantik tidak harus menggunakan kapal lagi, apakah kecepatan pengiriman kurang penting? Pelanggan FedEx dan DHL tidak berpikir demikian.

Peter Shor

2

Jika ukuran input cukup besar, perbedaan urutan-besarnya antara algoritma adalah penting tidak peduli seberapa cepat mesin. Tapi saya kadang-kadang tertipu untuk membuat perubahan untuk "mengoptimalkan pergi" perbedaan faktor konstan hanya untuk menyadari bahwa menggunakan ekspresi yang dibangun ke dalam gula sintaksis dari bahasa pemrograman <cough> Python </cough> secara signifikan lebih cepat daripada "optimasi" saya.

kojiro

lihat juga moores law

vzn

satu studi kasus yang menarik di sini adalah misalnya Windows, yang dalam beberapa / banyak hal berjalan kurang efisien bahkan pada perangkat keras yang sangat optimal daripada sebelumnya ... seperti halnya hukum moores meningkatkan perangkat keras, tampaknya ada hukum inflasi yang sesuai dalam perangkat lunak di mana peranti lunak modern semakin lama semakin banyak, dengan lapisan baru ditambahkan dan dikalikan ... agak analog dengan cara gas mengisi semua volume yang tersedia ... atau di mana anggaran tidak peduli seberapa besar atau meningkat selalu digunakan atau agak dikuasai ... lihat juga ras evolusi

vzn

31

Saya sangat suka contoh dari buku Pengantar Algoritma , yang menggambarkan pentingnya efisiensi algoritma:

Mari kita bandingkan dua algoritma pengurutan: jenis penyisipan dan jenis gabungan . Kompleksitasnya adalah dan . Biasanya gabungan jenis memiliki faktor konstan yang lebih besar, jadi mari kita asumsikan . $O(n^2) = c_1n^2$ $O(n\log n) = c_2n \lg n$ $c_1 < c_2$

Untuk menjawab pertanyaan Anda, kami mengevaluasi waktu eksekusi komputer yang lebih cepat (A) yang menjalankan algoritme penyisipan jenis terhadap komputer yang lebih lambat (B) yang menjalankan algoritme penggabungan.

Kami berasumsi:

ukuran masalah input adalah 10 juta angka: ; $n=10^7$
komputer A menjalankan instruksi per detik (~ 10GHz); $10^{10}$
komputer B hanya menjalankan instruksi per detik (~ 10MHz); $10^7$
faktor adalah (apa yang sedikit berlebihan) dan (pada kenyataannya lebih kecil). $c_1=2$ $c_2=50$

Jadi dengan asumsi ini dibutuhkan

\frac{2 \cdot (10^{7})^{2} instructions}{10^{10} instructions / second} = 2 \cdot 10^{4} seconds

$\frac{2 \cdot (10^7)^2 \text{ instructions}} {10^{10} \text{ instructions}/\text{second}} = 2 \cdot 10^4 \text{ seconds}$ untuk komputer A untuk mengurutkan angka dan

10^{7}

$10^7$

\frac{50 \cdot 10^{7} \lg 10^{7} instructions}{10^{7} instructions / second} \approx 1163 seconds

$\frac{50 \cdot 10^7 \lg 10^7 \text{ instructions}} {10^{7} \text{ instructions}/\text{second}} \approx 1163 \text{ seconds}$

untuk komputer B.

Jadi komputer, yang 1000 kali lebih lambat, dapat memecahkan masalah 17 kali lebih cepat. Pada kenyataannya, keuntungan dari jenis gabungan akan lebih signifikan dan meningkat dengan ukuran masalah. Saya harap contoh ini membantu menjawab pertanyaan Anda.

Namun, ini tidak semua tentang kompleksitas algoritma. Saat ini hampir tidak mungkin untuk mendapatkan peningkatan yang signifikan hanya dengan menggunakan mesin dengan frekuensi CPU yang lebih tinggi. Orang-orang perlu merancang algoritma untuk sistem multi-inti yang skala dengan baik. Ini juga tugas yang sulit, karena dengan peningkatan core, overhead (untuk mengelola akses memori, misalnya) meningkat juga. Jadi hampir tidak mungkin untuk mendapatkan speedup linier.

Jadi singkatnya, desain algoritma yang efisien hari ini sama pentingnya dengan sebelumnya, karena baik peningkatan frekuensi maupun core tambahan tidak akan memberi Anda kecepatan dibandingkan dengan yang dibawa oleh algoritma efisien.

Pavel Zaichenkov
sumber

4

Perlu disebutkan bahwa ketidakmungkinan percepatan linear berasal dari hukum Amdhal .

Bartosz Przybylski

Hukum Amdhal tidak selalu berlaku. Ada banyak masalah dalam ilmu komputasi di mana sebagian kecil dari pekerjaan yang tidak dapat diperbandingkan turun menjadi nol ketika ukuran masalah meningkat. Katakanlah komputasi membutuhkan berfungsi dan Anda perlu menghitung untuk berbeda . Secara serial biaya waktu adalah , sedangkan secara paralel dengan prosesor, pekerjaannya adalah .

f (x)

$f(x)$

n^{2}

$n^2$

\sum_{i = 1}^{n} f (x_{i})

$\sum_{i=1}^n f(x_i)$

n

$n$

x_{i}^{'} s

$x_i's$

O (n \cdot n^{2} + n) = O (n^{3})

$O(n\cdot n^2 + n) = O(n^3)$

n

$n$

O (n^{2} + n) = O (n^{2})

$O(n^2 + n) = O(n^2)$

Nick Alger

"Jadi komputer, yang 1000 kali lebih lambat, dapat menyelesaikan masalah 17 kali lebih cepat." Ini adalah pernyataan yang salah karena Anda menggabungkan kecepatan perangkat keras dan algoritma yang berbeda pada saat yang bersamaan. Alih-alih membandingkan komputer A vs Komputer B untuk setiap jenis penyortiran secara terpisah. (Mengapa saya tidak bisa menggunakan jenis gabungan di Komputer A, atau jenis sisipan di Komputer B?)

AquaAlex

3

@AquaAlex, tujuan dari contoh ini adalah untuk menunjukkan bahwa komputer yang lambat dapat mengungguli yang cepat hanya dengan menggunakan algoritma yang dipilih. Kami dapat membandingkan waktu eksekusi untuk setiap jenis penyortiran secara terpisah atau menjalankan penggabungan penyortiran pada A dan penyisipan menyortir pada B. Namun menunjukkan bahwa komputer yang lebih cepat biasanya berkinerja lebih baik daripada yang lambat hanya tidak masuk akal.

Pavel Zaichenkov

OK jadi idenya adalah untuk menunjukkan bahwa algoritma yang lebih efisien masih membawa bobot bahkan dalam sehari pada cpu yang lebih cepat dan memori yang lebih besar.

AquaAlex

36

Di sisi lain. Pada saat bersamaan perangkat keras semakin murah, beberapa perkembangan lainnya terjadi.

Pertama, jumlah data yang akan diproses bertambah secara eksponensial. Ini telah menyebabkan studi tentang algoritma waktu quasilinear , dan area big data . Pikirkan misalnya tentang mesin pencari - mereka harus menangani permintaan dalam jumlah besar, memproses data dalam jumlah besar, dan melakukannya dengan cepat. Algoritma lebih penting dari sebelumnya.

Kedua, bidang pembelajaran mesin tumbuh kuat, dan penuh dengan algoritma (meskipun berbeda dari apa yang Anda pelajari di BA Anda). Area ini berkembang pesat, dan seringkali algoritma yang benar-benar baru ditemukan, dan meningkatkan kinerja secara signifikan.

Ketiga, algoritma terdistribusi menjadi lebih penting, karena kami menekan hambatan dalam meningkatkan kecepatan pemrosesan CPU . Saat ini daya komputasi sedang ditingkatkan dengan memparalelkan , dan itu melibatkan algoritma khusus.

Keempat, untuk mengimbangi peningkatan kekuatan CPU, paradigma pemrograman modern menggunakan metode mesin virtual untuk memerangi celah keamanan. Itu memperlambat program-program ini karena faktor yang cukup besar. Menambah teka-teki, sistem operasi Anda menginvestasikan lebih banyak waktu CPU pada bel dan peluit, meninggalkan lebih sedikit waktu CPU untuk program Anda yang sebenarnya, yang dapat mencakup algoritma intensif CPU seperti kompresi video dan dekompresi. Jadi, sementara perangkat keras lebih cepat, itu tidak digunakan secara efisien.

Ringkasnya, algoritma yang efisien diperlukan untuk menangani sejumlah besar data; jenis algoritma baru bermunculan di bidang kecerdasan buatan ; algoritma terdistribusi menjadi fokus; dan daya CPU dimanfaatkan kurang efisien karena berbagai alasan (tetapi terutama, karena komputer semakin kuat). Algoritma belum mati.

Yuval Filmus
sumber

"Algoritma belum mati" ... sebaliknya, kita mungkin hidup melalui "zaman keemasan algoritma" ....

vzn

12

Pengetahuan tentang algoritma jauh lebih dari bagaimana menulis algoritma yang cepat.

Ini juga memberi Anda metode penyelesaian masalah (mis. Membagi dan menaklukkan, pemrograman dinamis, serakah, reduksi, pemrograman linier, dll) yang kemudian dapat Anda terapkan saat mendekati masalah baru dan menantang. Memiliki pendekatan yang cocok biasanya mengarah pada kode yang lebih sederhana dan lebih cepat untuk ditulis. Jadi saya harus tidak setuju dengan jawaban Kevin karena kode yang tidak hati-hati disatukan sering tidak hanya lambat tetapi juga rumit. Saya suka kutipan ini oleh David Parnas:

Saya sering mendengar pengembang digambarkan sebagai "seseorang yang tahu cara membangun sistem besar dengan cepat." Tidak ada trik dalam membangun sistem besar dengan cepat; semakin cepat Anda membangunnya, semakin besar hasilnya!

(Tentu saja, kita juga perlu menggabungkan algoritma dengan metode desain perangkat lunak untuk menulis kode yang baik.)

Pengetahuan tentang algoritma juga memberi tahu kami cara mengatur data Anda sehingga Anda dapat memprosesnya dengan lebih mudah dan efisien melalui penggunaan struktur data.

Selain itu, ini memberi kami cara untuk memperkirakan efisiensi pendekatan Anda, dan untuk memahami pertukaran antara beberapa pendekatan yang berbeda dalam hal kompleksitas waktu, kompleksitas ruang, dan kompleksitas kode. Mengetahui pertukaran ini adalah kunci untuk membuat keputusan yang tepat dalam keterbatasan sumber daya Anda.

Mengenai pentingnya efisiensi perangkat lunak, saya akan mengutip Hukum Wirth:

Perangkat lunak semakin lambat lebih cepat daripada perangkat keras menjadi lebih cepat.

Larry Page baru-baru ini menyatakan kembali bahwa perangkat lunak menjadi dua kali lebih lambat setiap 18 bulan, dan dengan demikian melampaui hukum Moore.

Dai
sumber

7

Ya , mereka 'relatif' kurang penting dalam industri luas. Editor teks mungkin 'cukup cepat' dan mungkin tidak perlu banyak perbaikan. Sebagian besar upaya TI dilakukan untuk memastikan komponen A yang ditulis di Jawa bekerja dengan komponen B yang ditulis dengan C berkomunikasi dengan benar melalui antrian pesan yang ditulis dalam Cobol (atau sesuatu), atau untuk membawa produk ke pasar, dll.

Terlebih lagi arsitekturnya menjadi rumit. Ketika Anda memiliki prosesor sederhana sederhana tua di mana Anda memiliki 1 instruksi per siklus dan Anda menulis dalam perakitan optimasi itu 'mudah' (Anda hanya perlu menghitung jumlah instruksi). Saat ini Anda tidak memiliki prosesor sederhana tetapi prosesor yang sepenuhnya disalurkan melalui pipa, superscalar, rusak dengan penggantian nama register dan cache beberapa tingkat. Dan Anda tidak menulis dalam perakitan tetapi di C / Java / etc. di mana kode dikompilasi / JITed (biasanya untuk kode yang lebih baik maka Anda atau saya akan menulis dalam perakitan), atau dengan Python / Ruby / ... di mana kode ditafsirkan dan Anda dipisahkan oleh beberapa tingkat abstraksi dari mesin. Optimalisasi mikro itu sulit dan kebanyakan programmer akan mencapai efek sebaliknya.

Tidak , mereka sama pentingnya dalam penelitian dan dalam istilah 'absolut' . Ada area di mana kecepatan penting karena mereka beroperasi pada sejumlah besar data. Pada skala ini kerumitan penting seperti ditunjukkan oleh contoh Pavel.

Namun ada beberapa kasus lebih lanjut - turun 'dari algoritma masih merupakan pilihan yang dipilih ketika masalah kecepatan (HPC, perangkat tertanam dll). Anda akan menemukan banyak grup universitas yang berspesialisasi dalam kompiler dan / atau optimasi perangkat lunak. Sebagai contoh, pertukaran urutan loop yang sederhana dapat memperoleh speedup seribu kali hanya karena menggunakan cache secara efisien - sementara itu mungkin merupakan contoh batas, celah CPU-Memory tumbuh 1000 kali selama 30 tahun terakhir. Arsitektur Komputer juga merupakan bagian dari CS. Oleh karena itu banyak perbaikan dalam kecepatan perhitungan sebenarnya merupakan bagian dari bidang CS umum.

Di sisi industri - ketika Anda memiliki masalah kecepatan klaster HPC karena satu program dapat berjalan selama berhari-hari, berbulan-bulan atau bertahun-tahun. Anda tidak hanya perlu membayar tagihan listrik tetapi menunggu juga dapat menghabiskan biaya. Anda dapat membuang dua kali lebih banyak perangkat keras tetapi $ 700 juta hampir tidak dapat dianggap sebagai perubahan saku untuk semua kecuali perusahaan besar - dalam kasus seperti itu para programmer adalah pilihan yang lebih murah dan jika menulis ulang program ke dalam bahasa baru berarti hanya percepatan 'kecil' - mereka mungkin pikirkan itu.

Juga kecepatan mungkin berarti UX yang lebih baik. Banyak tinjauan OS ponsel menyatakan mana yang 'snappier' dan sementara itu dapat dilakukan dengan 'trik' itu tentu merupakan bidang studi. Anda juga ingin mengakses data Anda lebih cepat dan cepat melakukan apa yang Anda butuhkan. Terkadang itu berarti Anda dapat melakukan lebih banyak - dalam permainan Anda memiliki 0,017 untuk melakukan segalanya dan semakin cepat Anda semakin banyak permen yang bisa Anda masukkan.

Maciej Piechotka
sumber

2

Ini adalah diskusi yang menarik. Dan kami memiliki beberapa hal untuk dilihat di sini.

Ilmu komputer teoretis - Ini adalah ilmu yang berkembang yang berarti seiring berjalannya waktu kita akan menemukan cara-cara baru dan lebih baik untuk menyelesaikan masalah, yang berarti peningkatan algoritma untuk mencari dan menyortir misalnya.
Komunitas yang lebih besar / perpustakaan yang lebih besar - Karena banyak pekerjaan telah dilakukan oleh orang lain, kita dapat membangun karya mereka dan menggunakan algoritme yang telah mereka buat dan bahkan diberi kode. Dan perpustakaan ini akan diperbarui dengan waktu yang memungkinkan kita akses otomatis ke program / algoritma yang lebih efisien.
Pengembangan - Sekarang di sini kita punya masalah saya pikir. Banyak programmer bukan ilmuwan komputer sehingga mereka menulis kode untuk memecahkan masalah bisnis bukan masalah teknis / teoritis dan akan senang menggunakan semacam gelembung sebagai semacam cepat misalnya. Dan di sini kecepatan perangkat keras memungkinkan programmer buruk untuk pergi dengan menggunakan algoritma yang buruk dan praktik pengkodean yang buruk. Memori, kecepatan CPU, ruang penyimpanan hal-hal ini tidak lagi menjadi perhatian utama dan setiap beberapa bulan hal-hal semakin besar, lebih cepat dan lebih murah. Maksud saya lihat Ponsel baru. Mereka sekarang lebih maju daripada komputer / server mainframe dari tahun 1970-an / 80-an. Lebih banyak penyimpanan, lebih banyak daya pemrosesan, memori lebih cepat.
UI & DATA - Antarmuka Pengguna / Pengalaman Pengguna dan DATA sekarang dianggap lebih penting daripada kode super efisien di sebagian besar area pengembangan. Jadi kecepatan hanya menjadi dan masalah ketika pengguna harus menunggu lama. Jika kami memberikan tampilan dan perasaan yang bagus kepada pengguna dan ia mendapat respons yang baik dari aplikasi, ia senang. Dan jika bisnis tahu semua data disimpan dengan aman dan aman dan mereka dapat mengambilnya dan memanipulasinya kapan saja mereka tidak peduli berapa banyak ruang yang dibutuhkan.

Jadi saya harus mengatakan itu bukan bahwa programmer yang efisien tidak lagi penting atau dibutuhkan, hanya saja sangat sedikit perusahaan / pengguna yang memberi penghargaan kepada orang-orang karena menjadi programmer yang sangat efisien, dan karena perangkat keras yang lebih baik kita lolos dengan menjadi kurang efisien. Tetapi setidaknya masih ada orang di luar sana yang berfokus pada efisiensi dan karena semangat komunitas, setiap orang pada waktunya mendapatkan manfaat dari ini.

AquaAlex
sumber

1

Beberapa sudut lain pada pertanyaan yang menarik dan mendalam ini menekankan aspek interdisipliner dan lintas sektor dari fenomena ini. Dai mengutip hukum Wirth dalam jawabannya:

Perangkat lunak semakin lambat lebih cepat daripada perangkat keras menjadi lebih cepat.

Ada paralel yang menarik dari ide ini dengan fenomena yang diamati dalam ekonomi. Perhatikan bahwa ekonomi memiliki banyak koneksi yang mendalam dengan ilmu komputer misalnya dalam penjadwalan katakanlah di mana sumber daya yang langka (mis. Utas dll) dialokasikan berdasarkan permintaan, dengan algoritma "load-balancing". Contoh lain adalah apa yang disebut antrian produsen-konsumen. Juga, lelang.

Juga misalnya, Daftar hukum eponim, Wikipedia :

Hukum Parkinson - "Pekerjaan mengembang untuk mengisi waktu yang tersedia untuk penyelesaiannya." Diciptakan oleh C. Northcote Parkinson (1909-1993), yang juga menciptakan akibat wajarnya, "Pengeluaran meningkat untuk memenuhi pendapatan." Di komputer: Program diperluas untuk mengisi semua memori yang tersedia.

Ada beberapa kesamaan kuat juga dengan paradoks Jevon yang diamati dalam peningkatan penggunaan energi setelah mesin uap Watt lebih efisien mulai menggantikan desain Newcomen, tetapi penggunaan atau proliferasi mesin meningkat:

Dalam ilmu ekonomi, paradoks Jevons (/ ˈdʒɛvənz /; kadang-kadang efek Jevons) adalah proposisi bahwa kemajuan teknologi yang meningkatkan efisiensi dengan penggunaan sumber daya cenderung meningkatkan (daripada mengurangi) tingkat konsumsi sumber daya tersebut.

Analoginya adalah bahwa perangkat keras adalah sumber daya dan perangkat lunak seperti konsumsi sumber daya (alias, penawaran vs permintaan). Jadi, perangkat lunak dan perangkat keras (dan masing-masing kemajuan) ada dalam lingkaran umpan balik simbiosis yang saling terkait erat, dalam arti tertentu, saling berkoevensiasi . Ada banyak faktor kompleks dan saling terkait yang mempengaruhi interaksi ini, misalnya:

ay
sumber

Mengapa downvote? Saya menemukan penyebutan hukum Parkinson dan paradoks Jevons sangat terbuka.

Yuval Filmus

@YuvalFilmus Dugaan saya: masalah dengan tata bahasa. Saya tidak merasa terganggu dengan kemampuan saya untuk membaca jawabannya terlalu banyak kali ini, tetapi saya mencoba memperbaikinya.

Juho

1

Ini bukan "masalah tata bahasa", itu gaya yang berbeda. Ini seperti mengatakan bahwa penutur asli membuat "kesalahan" berbicara dalam bahasa mereka sendiri, padahal sebenarnya bahasa berubah, atau ada perbedaan regional. Dalam hal ini, itu gaya idiom vzn.

Yuval Filmus

-3

Tidak, sebagian besar sambil mempertimbangkan kompleksitas ruang! Kapasitas penyimpanan komputer normal tumbuh secara eksponensial.

Andy
sumber

Tidak akan terbalik benar - jika Anda memiliki penyimpanan 'tak terbatas' Anda tidak perlu repot tentang kompleksitas ruang. Masalahnya bukanlah penyimpanan tumbuh tetapi data untuk beroperasi tumbuh dalam sinkronisasi mengisi percepatan yang ditawarkan oleh peningkatan daya komputasi dan memori - yang merupakan hal yang baik, kami ingin memodelkan kosmos lebih realistis, melipat lebih banyak protein dll. (PS. Saya belum memilih)

Maciej Piechotka

4

Memang benar bahwa banyak pengembang aplikasi seluler tampaknya menganggap sumber daya tak terbatas, tetapi sayangnya perangkat saya sangat terbatas.

Raphael

Apakah algoritma (dan efisiensi secara umum) menjadi kurang penting?

Jawaban: