it-swarm-id.com

Apakah big-O benar-benar relevan ketika bekerja di industri?

Dalam setiap wawancara yang telah saya ikuti, saya ditanyai tentang analisis kompleksitas matematika, termasuk notasi O-besar.

Seberapa relevan analisis big-O untuk pengembangan di industri? Seberapa sering Anda benar-benar menggunakannya, dan seberapa penting untuk memiliki pola pikir yang terasah untuk masalah ini?

66
MM01

Pertanyaan saya adalah, seberapa relevankah tes ini dengan pengembangan di industri?

Pemahaman yang kuat tentang teori kompleksitas komputasi (mis. Notasi O besar) sangat penting untuk merancang algoritma, aplikasi, dan sistem yang dapat diskalakan. Karena skalabilitas sangat relevan dengan komputasi dalam industri, notasi O besar juga.

Seberapa sering Anda menggunakannya, dan seberapa penting untuk memiliki pola pikir yang terasah untuk masalah ini?

Tergantung apa yang Anda maksud dengan "gunakan secara teratur". Di satu sisi, saya tidak pernah melakukan bukti formal kompleksitas komputasi untuk perangkat lunak yang saya tulis. Di sisi lain, sebagian besar hari saya harus berurusan dengan aplikasi di mana skalabilitas merupakan masalah potensial, dan keputusan desain mencakup pemilihan (misalnya) jenis koleksi yang tepat berdasarkan karakteristik kompleksitasnya.

(Saya tidak tahu apakah mungkin untuk secara konsisten menerapkan sistem yang dapat diskalakan tanpa pemahaman yang kuat tentang teori kompleksitas. Saya akan cenderung berpikir bahwa itu bukan.)

76
Stephen C

Alasan untuk ini adalah karena ini menunjukkan skalabilitas .

Suatu proses yang O (n ^ 2) akan skala lebih buruk daripada yang O (n log n), tetapi lebih baik dari satu di O (n ^ 3) atau bahkan O (n!).

Jika Anda tidak tahu perbedaannya dan kapan mereka berlaku, Anda kurang cocok untuk memilih implementasi fungsionalitas yang tepat, serta mengekstrapolasi kinerja pengujian ke dalam kinerja produksi.


EDIT: Perbandingan 48n dengan n ^ 3 dari http://www.codinghorror.com/blog/2007/09/everything-is-fast-for-small-n.html (yang pada giliran dari Pemrograman Mutiara)

enter image description here

36
user1249

Itu tergantung pada apa yang Anda lakukan.

Untuk pengembang web (seperti saya) ini biasanya penting. Anda ingin skala aplikasi web. Jika aplikasi Anda memiliki hambatan yang berskala dengan O (n ^ 2), dan Anda pikir ini baik-baik saja, karena server Anda dapat menangani 1000 pengguna secara bersamaan, sepertinya Anda tidak perlu peduli. Masalahnya, untuk menangani hanya dua kali lebih banyak (yang mungkin terjadi pada malam hari), Anda akan membutuhkan 4 kali kekuatan komputasi. Idealnya Anda ingin aplikasi web untuk skala di O (n), karena perangkat keras murah dengan rasio pengguna/server konstan yang masuk akal.

Umumnya di aplikasi, di mana Anda memiliki 100000 objek, O besar akan datang dan memakan Anda. Anda sangat rentan terhadap puncak. Misalnya, saya sedang mengerjakan game 3D, yang merupakan aplikasi yang menangani banyak data. Selain rendering, Anda memiliki pemeriksaan tabrakan, navigasi dll. Anda tidak mampu hanya dengan cara yang jelas. Anda membutuhkan algoritma yang efisien, Anda perlu banyak caching sehingga yang kurang efisien diamortisasi. Dan seterusnya.

Tentu saja jika yang Anda lakukan adalah membuat aplikasi seluler dengan menggabungkan GUI dalam perancang antarmuka, menghubungkannya dengan beberapa layanan web dan hanya itu, maka Anda tidak akan pernah memiliki masalah dengan kompleksitas. Karena layanan web yang Anda panggil sudah mengurusnya.

32
back2dos

Saya tidak pernah benar-benar menerapkan aturan formal dalam kehidupan kerja saya.

Namun Anda harus terbiasa dengan konsep itu, dan menerapkannya dengan cara yang intuitif setiap kali Anda merancang suatu algoritma.

Aturannya adalah:

Anda harus cukup terbiasa dengan notasi O untuk dapat menentukan, untuk tugas yang diberikan, jika diperlukan untuk menghitungnya secara formal, atau hanya cukup untuk mengevaluasinya secara intuitif, atau jika Anda dapat melewatkannya seluruhnya. Sama seperti banyak konsep matematika dasar lainnya.

22
Wizard79

Yah, mungkin sedikit cerita yang menjelaskan mengapa itu PASTI IS diperlukan:

Dalam sebuah proyek yang saya kerjakan, ada sebuah program yang bertanggung jawab untuk mencetak semua jenis dokumen (label, daftar pilih dll.) Program ini terdiri dari dua bagian, satu membaca semua data yang diperlukan dari database dan menulisnya ke dalam File .ini-style, dan bagian lain yang membaca file-file itu dan mengisinya ke dalam templat. Ini bekerja cukup baik untuk label dan daftar kecil (dengan hanya beberapa bidang) tetapi berjalan selama hampir 10 menit ketika harus mencetak daftar "besar" ~ 20 halaman. Karena mengakses file-file ini menghasilkan waktu akses O (n²), n menjadi jumlah bidang yang akan dicetak.

Seandainya programmer asli dari program ini memahami notasi-O, mereka tidak akan pernah berhasil seperti itu. Mengganti kebodohan itu dengan hashtable membuatnya jadi lebih cepat.

10
user281377

Kinerja Big-O itu penting, tetapi sebagian besar sudah diinternalisasi.

Kinerja penyortiran dan pencarian Big-O tidak masalah, karena orang umumnya menggunakan yang disediakan sistem, dan mereka akan sebaik yang mereka bisa (mengingat bahwa mereka perlu berguna secara umum). Ada struktur data yang lebih efisien untuk hal-hal yang berbeda, tetapi biasanya dapat dipilih berdasarkan prinsip umum (dan biasanya dibangun ke dalam bahasa modern). Ada beberapa rasa algoritma yang melakukan atau tidak skala.

Hasilnya adalah bahwa masalah formal jarang muncul dalam praktik, tetapi praktik dibangun di atas prinsip yang sama.

8
David Thornley

IMHO banyak program ilmu komputer meninggalkan banyak siswa berkeliaran di sana di gulma. Program-program ini tidak pernah cukup mengkomunikasikan gambaran besar tentang apa itu ilmu komputasi. Para siswa memasuki industri, bergulat dengan bagaimana menerapkan konsep yang telah mereka pelajari, dengan sedikit wawasan tentang bagaimana mereka berhubungan dengan dunia nyata.

Saya akan mengatakan bahwa inti ilmu komputasi adalah kemampuan untuk berpikir tentang komputasi. Dan Anda belajar berbagai metode dan teknik untuk melakukan ini, dan menerapkannya pada masalah yang diabstraksi, yang merupakan primitif prototipikal yang ditemukan di banyak masalah dunia nyata. Kuncinya adalah menemukan primitif prototipikal ini di dunia nyata, dan kemudian alasan tentang hal-hal seperti kebenaran, kompleksitas, waktu dll, yang, Anda mungkin setuju, adalah masalah nyata yang perlu Anda khawatirkan. Wawasan tentang bagaimana bagian-bagian berperilaku, sering memberi Anda wawasan tentang bagaimana keseluruhan berperilaku. Dan metode dan teknik umum yang sama juga dapat diterapkan untuk keseluruhan, hanya saja tidak dengan ketelitian yang sama yang diberikan pada bagian yang lebih kecil, abstrak, dan terdefinisi dengan baik. Tetapi pada akhirnya, ilmu komputasi, memberi Anda kemampuan untuk membuat masuk akal keputusan tentang bagaimana mengatur perhitungan Anda, dengan wawasan nyata tentang bagaimana ia akan berperilaku dalam berbagai kondisi.

7
Ziffusion

Memo untuk diri sendiri:

Saya dan banyak orang lain bertanya pada diri sendiri pertanyaan ini secara teratur.

Saya pikir alasan sebenarnya kami menanyakan ini adalah karena kami menjadi malas.

Pengetahuan ini tidak akan pernah tanggal atau menjadi usang. Anda mungkin tidak menerapkannya secara langsung setiap hari tetapi Anda akan menggunakannya secara tidak sadar dan itu akan berdampak positif pada keputusan desain Anda. Suatu hari itu mungkin menghemat Anda atau orang lain berjam-jam dan berhari-hari.

Karena semakin banyak masalah yang dirangkum oleh perpustakaan dan alat pihak ketiga dan tersedia untuk semakin banyak pengembang, Anda perlu mengetahui pengetahuan ini untuk membedakan diri Anda dari orang lain dan untuk membantu memecahkan masalah baru.

5
Conor

Tidak juga. Pada dasarnya satu-satunya waktu saya memikirkannya adalah ketika mengakses database. Saya biasanya akan melihat kode dan mengatakan "Itu melakukan n + 1 permintaan, Anda harus mengubahnya untuk melakukan hanya 1 atau 2"

Karena semua data saya sedang dibaca dari database dan ditunjukkan kepada pengguna, saya mencoba untuk meminimalkan jumlah data yang saya kerjakan sampai pada titik di mana perbedaan antara algoritma linier dan O (n ^ 2) cukup dapat diabaikan.

Jika ada masalah, kami akan membuat profil dan memperbaikinya nanti.

5
Greg

Tiga pertanyaan yang Anda ajukan dan saya pikir jawaban bentuk pendek dapat membantu argumen yang lebih panjang yang diberikan sejauh ini.

Seberapa relevan pengujian ini dengan pengembangan di industri?

Tergantung pada industri.

Di mana pun di mana kecepatan kode atau ruang kode merupakan masalah, itu sepenuhnya relevan dengan industri yang terlibat. Seringkali Anda perlu tahu berapa lama rutinitas akan diperlukan, atau berapa banyak memori (on/offline) yang dibutuhkan.

Seberapa sering Anda menggunakannya?

Tergantung pada industri.

Jika kinerja dan penskalaan tidak terlalu mempedulikan pekerjaan yang ada, maka jarang, hanya ketika ada kekurangan kinerja yang serius. Jika Anda seorang insinyur untuk sistem kritis yang sangat sering digunakan, mungkin setiap hari.

Seberapa penting untuk memiliki pola pikir terasah untuk masalah ini?

Sangat diperlukan.

Anda mungkin harus menggunakannya setiap hari, atau hanya dalam keadaan yang mengerikan; tapi terkadang itu dibutuhkan. Lebih disukai selama desain sebelum masalah tiba, daripada dengan putus asa membuat profil sistem tersedak.

3
Orbling

Saya akan mengatakan itu sangat sering. Kami biasanya tidak membuktikan sesuatu memiliki O-besar tertentu, tetapi kami telah menginternalisasi idenya, dan menghafal/menjadi terbiasa dengan jaminan O-besar untuk struktur data dan algoritma tertentu, dan kami memilih yang tercepat untuk penggunaan tertentu. Ini membantu untuk memiliki pustaka yang penuh dengan semua opsi, seperti pustaka koleksi Java, atau C++ STL. Anda secara implisit dan alami menggunakan big-O setiap hari = ketika Anda memilih untuk menggunakan Java.util.HashMap (O(1) lookup) daripada Java.util.TreeMap (O(lg n) lookup) dan tentu saja memilih untuk tidak menjalankan pencarian linier lintas a Java.util.LinkedList (O(n) lookup) untuk sesuatu di mana Anda tidak perlu akses yang diurutkan.

Ketika seseorang memilih implementasi suboptimal dan seseorang yang tahu lebih baik datang dan melihat kode mereka, itu adalah bagian dari kosa kata kami untuk memperbaikinya "implementasi Anda membutuhkan waktu kuadratik, tetapi kita bisa menurunkannya ke waktu n-log-n dengan melakukannya dengan cara ini sebagai gantinya "secara alami dan otomatis seperti yang kita akan menggunakan bahasa Inggris untuk memesan pizza.

3
Ken Bloom

Ya

Anda mungkin tidak harus melakukan analisis formal, tetapi setidaknya pemahaman tentang urutan kompleksitas algoritma - dan bagaimana membandingkan dua algoritma di sekitar itu - sangat penting jika Anda ingin melakukan pekerjaan non-sepele dan membuatnya berjalan dengan baik.

Saya telah bekerja pada dua sistem yang berbeda yang kelihatannya bagus dalam pengembangan awal, tetapi membuat perangkat keras bertekuk lutut dalam pengujian produksi, karena seseorang menggunakan algoritma O (n ^ 2). Dan dalam kedua kasus, perbaikannya adalah perubahan sepele untuk algoritma O(n).

3
Bob Murphy

Ini mungkin digunakan di tempat-tempat mereka mengembangkan API untuk konsumsi. C++ STL adalah salah satu dari beberapa API yang memiliki batasan kompleksitas yang dikenakan pada algoritme-nya. Tetapi untuk programmer/programmer/desainer/arsitek senior yang bekerja sehari-hari itu tidak banyak terlintas dalam pikiran mereka.

1
sashang

Saya tidak menganggapnya penting kecuali untuk mengomunikasikan ide, dan saya bekerja di bidang yang sangat kritis terhadap kinerja (raytracing, pemrosesan gambar dan mesh, sistem partikel, mesin fisika, dll.) Dan harus merancang banyak algoritma dan struktur data berpemilik saat bekerja di R&D. Di area ini, seringkali beberapa struktur data dan algoritma yang sangat efisien dapat menghasilkan produk-produk baru yang mutakhir sementara algoritma kemarin membuat produk yang sudah ada menjadi usang, jadi selalu ada upaya untuk melakukan sesuatu dengan lebih efisien. Namun, sebagai peringatan, saya tidak pernah menerbitkan makalah tentang algoritma yang saya buat. Semuanya milik. Jika saya melakukannya, saya akan membutuhkan bantuan ahli matematika untuk merumuskan bukti dan sebagainya.

Namun menurut saya jumlah pekerjaan komputasi per iterasi sering kali lebih menarik daripada skalabilitas algoritma kecuali jika skala algoritma benar-benar buruk. Jika seseorang datang dengan teknik canggih untuk raytracing, saya lebih tertarik pada teknik komputasi seperti bagaimana mereka mewakili dan mengakses data daripada kompleksitas algoritmik karena skalabilitas yang wajar sudah diberikan dalam skenario kompetitif dan inovatif ini. Anda tidak dapat bersaing dengan algoritma yang tidak memiliki skala.

Tentu saja jika Anda membandingkan kompleksitas kuadratik dengan linearitmik, itu perbedaan besar. Tetapi kebanyakan orang di bidang saya cukup kompeten untuk menghindari penerapan algoritma kompleksitas kuadrat pada input epik. Jadi skalabilitas seringkali sangat tersirat, dan pertanyaan yang lebih bermakna dan menarik menjadi seperti, "Apakah Anda menggunakan GPGPU? SIMD? Apakah itu berjalan secara paralel? Bagaimana Anda mewakili data? Apakah Anda mengatur ulang untuk ramah cache pola akses? Berapa banyak memori yang dibutuhkan? Bisakah menangani kasus ini dengan kuat? Apakah Anda menunda pemrosesan tertentu atau melakukan semuanya sekaligus? "

Bahkan algoritma linearithmic dapat mengungguli algoritma linear-waktu jika yang pertama mengakses memori dalam pola yang lebih optimal, mis., Atau lebih cocok untuk multithreading dan/atau SIMD. Kadang-kadang bahkan suatu algoritma linier dapat mengungguli algoritma logaritmik untuk alasan-alasan ini, dan secara alami algoritma linear waktu mengungguli yang logaritmik untuk input kecil.

Jadi bagi saya yang lebih penting adalah apa yang beberapa orang sebut "optimasi mikro", seperti representasi data (tata letak memori, pola akses dengan pemisahan bidang panas/dingin, dll.), Multithreading, SIMD, dan kadang-kadang GPGPU. Dalam bidang di mana setiap orang sudah cukup kompeten untuk menggunakan algoritma yang layak untuk mutakhir untuk semua hal dengan makalah baru yang diterbitkan sepanjang waktu, Edge kompetitif Anda dalam mengalahkan para penyihir algoritmik tidak datang dari peningkatan dalam kompleksitas algoritme sehingga lebih langsung efisiensi komputasi.

Bidang saya didominasi oleh ahli matematika yang brilian tetapi tidak selalu orang yang mengetahui biaya komputasi dari apa yang mereka lakukan atau banyak trik tingkat rendah untuk mempercepat kode. Itu biasanya Edge saya atas mereka dalam merancang algoritma lebih cepat dan lebih ketat dan struktur data meskipun saya jauh lebih canggih. Saya bermain dengan apa yang disukai perangkat keras, terhadap bit dan byte dan membuat setiap iterasi pekerjaan lebih murah bahkan jika saya melakukan beberapa iterasi pekerjaan lebih daripada algoritma yang benar-benar canggih - pekerjaan dalam kasus saya jauh lebih murah secara drastis. Kode yang saya tulis juga cenderung jauh lebih sederhana. Jika orang berpikir versi yang dioptimalkan secara mikro dari algoritma langsung dan struktur data sulit dipahami dan dipelihara, cobalah memahami dan memelihara koleksi algoritma terkait mesh eksotis dan struktur data yang belum pernah terlihat sebelumnya di industri dengan kertas 20 halaman yang menjelaskan langkah-langkah mereka secara matematis .

Sebagai contoh dasar, saya datang dengan struktur grid sederhana yang akhirnya mengungguli pohon-KD di perusahaan kami untuk deteksi tabrakan dan penghapusan titik redundan. Grid kasar saya sangat jauh kurang canggih secara algoritmik dan saya jauh lebih sedikit secara matematis dan algoritmik daripada orang yang menerapkan KD-tree dengan cara novelnya menemukan titik tengah, tetapi saya hanya menyetel penggunaan memori dan pola akses grid saya dan itu sudah cukup untuk mengungguli sesuatu yang jauh lebih canggih.

Keunggulan lain yang saya miliki yang memungkinkan saya bertahan di bidang yang didominasi oleh orang-orang yang jauh lebih pintar daripada saya hanyalah benar-benar memahami cara kerja pengguna, karena saya menggunakan perangkat lunak yang saya kembangkan dengan cara yang sama. Itu memberi saya ide untuk algoritma yang benar-benar menyelaraskan dengan minat pengguna. Sebagai contoh dasar di sana, kebanyakan orang mencoba untuk mempercepat hal-hal seperti deteksi tabrakan menggunakan pengindeksan spasial. Saya membuat pengamatan pembentukan karir sederhana hampir beberapa dekade yang lalu untuk model organik yang, misalnya, jika karakter meletakkan tangannya di wajahnya, struktur pengindeksan spasial ingin harus membagi node dan melakukan pembaruan mahal jika karakter lalu melepaskan tangannya dari wajahnya. Sebaliknya, jika Anda mempartisi berdasarkan data konektivitas daripada posisi vertex, Anda dapat berakhir dengan struktur hierarki yang stabil yang memperbarui dengan sangat cepat dan tidak perlu membelah atau menyeimbangkan kembali pohon (hanya harus memperbarui kotak pembatas setiap frame animasi). .. hal-hal seperti ini - algoritma anak tanpa latar belakang matematika yang berat dapat muncul jika mereka hanya memahami konsep dasar, tetapi yang menghindari para ahli matematika karena mereka tidak memikirkan hal-hal dengan cara yang begitu dekat dengan bagaimana para pengguna bekerja dan berpikir terlalu banyak tentang sifat-sifat geometri dan bukan bagaimana geometri umum digunakan. Saya cukup rukun dengan bersandar lebih pada pengetahuan komputasi umum dan pengetahuan pengguna akhir daripada sihir algoritmik. Jadi, saya belum benar-benar menganggapnya penting untuk fokus pada kompleksitas algoritmik.

1
user204677

Saya tidak pernah memikirkan O besar dalam perspektif matematika, saya tidak pernah berpikir tentang O besar sama sekali, kecuali ditanya. Saya hanya melihat sebuah algoritma di kepala saya, dan saya bisa tahu apakah itu buruk karena melakukan banyak loop melalui memori untuk setiap N, atau apakah itu membagi dan menaklukkan atau sesuatu seperti itu. Jika diperlukan, saya bisa menerjemahkannya ke notasi O besar dalam beberapa detik, tetapi lebih mudah bagi saya untuk hanya mengetahui bagaimana algoritma/wadah bekerja dengan memori, daripada berpikir tentang perspektif matematika.

0
Coder

Ya, kompleksitas penting di industri. Jika Anda akhirnya merancang sesuatu di mana skala jalur kritis sebagai N-kuadrat (menggandakan jumlah sesuatu membuat sistem empat kali lipat), Anda akan menekan bottleneck scaling Anda jauh lebih cepat daripada jika Anda memiliki sesuatu yang timbangan pada N.

Namun, itu biasanya tidak dilakukan sebagai bukti yang tepat, formal, bahwa sesuatu berada pada kompleksitas yang diberikan, jadi memiliki intuisi yang baik untuk kompleksitas pola operasi memiliki permulaan yang baik.

0
Vatine