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 dalam industri? Seberapa sering Anda benar-benar menggunakannya, dan seberapa penting untuk memiliki pola pikir yang terasah untuk masalah ini?

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

Pemahaman yang kuat tentang teori kompleksitas komputasi (misalnya 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 menerapkan sistem yang dapat diukur secara konsisten tanpa pemahaman yang kuat tentang teori kompleksitas. Saya akan cenderung berpikir bahwa itu tidak mungkin.)

Alasan untuk ini adalah karena ini menunjukkan skalabilitas .

Suatu proses yang O (n ^ 2) akan skala lebih buruk dari 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 gilirannya adalah dari Pemrograman Mutiara)

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 adalah, 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 pada 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 memerlukan 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.

Saya tidak pernah benar-benar menerapkan aturan secara 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.

Ya, mungkin sedikit cerita yang menjelaskan mengapa itu PASTI perlu:

Dalam sebuah proyek yang saya kerjakan, ada 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 lebih cepat.

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.

IMHO banyak program ilmu komputer membuat 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 diabstraksikan, 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 pada keseluruhan, hanya saja tidak dengan ketelitian yang sama dengan yang diberikan pada bagian yang lebih kecil, abstrak, dan terdefinisi dengan baik. Tetapi pada akhirnya, ilmu komputasi, memberi Anda kemampuan untuk membuat yang masuk akal keputusan tentang bagaimana mengatur perhitungan Anda, dengan wawasan nyata tentang bagaimana ia akan berperilaku dalam berbagai kondisi.

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 dapat menghemat waktu pengkodean untuk Anda atau orang lain.

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.

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.

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

Seberapa relevan tes 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 suatu rutinitas akan berlangsung, atau berapa banyak memori (on / offline) yang dibutuhkan.

Seberapa sering Anda menggunakannya berulang kali?

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 perlunya memiliki pola pikir yang 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.

Saya akan mengatakan itu sangat sering. Kami umumnya tidak membuktikan sesuatu memiliki O-besar tertentu, tetapi kami telah menginternalisasi idenya, dan mengingat / menjadi terbiasa dengan jaminan O-besar untuk struktur data dan algoritma tertentu, dan kami memilih yang tercepat untuk penggunaan tertentu. Ini membantu untuk memiliki perpustakaan yang penuh dengan semua opsi, seperti perpustakaan 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 linear melintasi 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.

Iya

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).

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.

Saya tidak menganggapnya penting kecuali untuk mengkomunikasikan 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 yang sangat efisien dan algoritma dapat menghasilkan produk-produk baru yang mutakhir sementara algoritma kemarin membuat produk yang sudah usang menjadi usang, sehingga selalu ada upaya untuk melakukan hal-hal yang lebih efisien. 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 pola akses yang ramah terhadap cache? Bagaimana 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, misalnya, 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. Di bidang di mana setiap orang sudah cukup kompeten untuk menggunakan algoritma yang layak dan mutakhir untuk semuanya dengan makalah baru yang diterbitkan sepanjang waktu, keunggulan kompetitif Anda dalam mengalahkan para penyihir algoritmik tidak berasal dari peningkatan dalam kompleksitas algoritme sehingga lebih langsung efisiensi komputasi.

Bidang saya didominasi oleh ahli matematika yang brilian tetapi tidak selalu yang tahu biaya komputasi dari apa yang mereka lakukan atau banyak trik tingkat rendah untuk mempercepat kode. Itu biasanya keunggulan saya atas mereka dalam merancang algoritma dan struktur data yang lebih cepat dan lebih ketat 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 secara drastis lebih murah. Kode yang saya tulis juga cenderung lebih sederhana. Jika orang berpikir versi yang dioptimalkan secara mikro dari algoritma langsung dan struktur data sulit dipahami dan dipelihara,

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 median, tapi saya hanya menyetel penggunaan memori grid dan pola aksesnya 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 yang jauh lebih pintar daripada saya adalah 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 melakukan 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 titik, Anda dapat berakhir dengan struktur hierarki stabil yang memperbarui dengan sangat cepat dan tidak perlu membelah atau menyeimbangkan kembali pohon (hanya perlu memperbarui kotak pembatas setiap bingkai animasi) ... hal-hal seperti ini - algoritma anak-anak tanpa latar belakang matematika yang berat bisa muncul jika mereka hanya memahami konsep dasar, tetapi yang menghindari matematika karena mereka tidak memikirkan hal-hal dengan cara yang begitu dekat dengan cara pengguna bekerja dan terlalu banyak berpikir hanya tentang sifat-sifat geometri dan bukan bagaimana geometri biasa 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.

Ya, kompleksitas penting dalam industri ini. 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 awal yang baik.

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 ia melakukan banyak loop melalui memori untuk setiap N, atau apakah itu membagi dan menaklukkan atau sesuatu seperti itu. Jika perlu, 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.

Pertanyaan-pertanyaan yang ditanyakan dalam wawancara ada di sana untuk mengetahui apakah Anda dapat menjelaskan berbagai hal dan berpikir secara logis . Pewawancara juga berusaha mencari tahu apakah Anda dapat menggunakan apa yang Anda ketahui untuk menyelesaikan masalah terkait .

Setiap orang yang telah melakukan pembelajaran yang berharga tentang rekayasa perangkat lunak akan menemukan "Big O", juga untuk menjawab pertanyaan yang bagus tentang "Big O" Anda juga harus memiliki beberapa pemahaman tentang struktur data standar dan algoritma.

Saat mewawancarai seorang anggota staf, Anda mencari seseorang yang dapat mempelajari pekerjaan itu dengan cepat, bukan seseorang yang sudah mengetahui seperangkat keterampilan terinci, sehingga sangat sulit untuk memilih pertanyaan yang pewawancara dan orang yang diwawancarai memiliki pemahaman yang sama. dari.

Jadi pertanyaan tentang "big O" bisa sangat relevan dengan proses wawancara.

Setidaknya setiap tahun dalam waktu lama sebagai programmer komputer saya harus memperbaiki kode yang lambat karena seseorang tidak memahami struktur data dan algoritma yang tepat untuk digunakan, tetapi Anda dapat menyelesaikan masalah ini tanpa memiliki pemahaman rinci tentang Big O. Namun orang-orang yang mengerti Big O tent tidak menghindari masalah ini sejak awal.