Haruskah seorang programmer yang kompeten dapat membuat algoritma jalur terpendeknya sendiri?

58

Saya menderita krisis kepercayaan pada kemampuan saya sebagai programmer komputer.

Kemarin saya mencoba untuk membuat algoritma jalur terpendek saya sendiri untuk grafik dan setelah beberapa jam saya hanya menyerah dan mempelajari algoritma Dijkstra.

Apakah ini jenis hal yang harus dapat "diciptakan kembali" oleh programmer yang baik dalam beberapa jam atau apakah saya tidak realistis?

Oh well, setidaknya saya bisa menemukan kembali jenis gelembung: D

Pemula Pemula
sumber
7
Seseorang yang telah melakukan UI selama 20 tahun mungkin akan kesulitan menemukan solusi untuk masalah dari domain lain, dalam waktu singkat.
Coder
38
Menghabiskan banyak waktu di situs SE memberi semua orang krisis kepercayaan diri! (Bukan berarti itu hal yang buruk). Kebahagiaan dalam hidup adalah menemukan keseimbangan sempurna antara penerimaan apa yang ada dan keinginan untuk mengubahnya.
TrojanName
2
Saya tidak dapat menemukan kembali sendiri, tetapi saya mencoba mengingat cara kerjanya. pastikan Anda memahami animasi ini: unggah.wikimedia.org/wikipedia/commons/2/23/…
Job
6
@ Tragedi Brian jenius lokal. Anda hampir tidak pernah bisa menjadi yang terbaik dalam hal apa pun lagi.
Rei Miyasaka
7
ilmuwan komputer yang baik harus tetapi tidak harus seorang programmer komputer atau insinyur perangkat lunak
Neil McGuigan

Jawaban:

118

Seorang programmer yang baik harus menyadari bahwa algoritma yang hebat telah ditulis untuk memecahkan masalah dan tidak membuang waktu untuk menemukan kembali roda.

Saya ragu Dijkstra menghasilkan algoritma jalur terpendek dalam beberapa jam, jadi sepertinya standar yang sangat tinggi untuk digunakan untuk menentukan apakah seseorang adalah 'programmer yang baik'

GSto
sumber
25
@Nakilon - Programmer yang mengabaikan solusi yang ada hanya membuang-buang waktu mereka, dan jika mereka tidak membuang waktu mereka, mereka membuat solusi yang lebih buruk. Lihat: Semua orang membuat skema hashing kata sandi sendiri vs bcrypt.
Pasang kembali Monica
10
@GSto: menurut wikipedia, Dijkstra muncul dengan algoritme dalam waktu kurang dari satu jam: 20 menit, menurut catatan pertama di wikipedia: en.wikipedia.org/wiki/Dijkstra%27s_algorithm
woliveirajr
9
Ini adalah algoritma yang relatif sederhana, tetapi Dijkstra sangat berbakat, dan telah dilatih dalam fisika teoretis dan matematika tingkat lanjut. Tidak ada yang seperti beberapa tahun menulis bukti untuk meningkatkan kemampuan seseorang untuk merancang algoritma.
kevin cline
19
@woliveirajr - Yah, saya yakin Newton mengambil jumlah waktu yang sama untuk membuat hukum gerak. Setelah memikirkannya selama 20 tahun pertama.
Benteng
6
@Nakilon - Ya itu sebabnya semua orang menulis semuanya dalam bahasa C, karena kalau tidak, Anda hanya seorang pembuat kode, menggunakan bahasa tingkat tinggi orang lain. Oh, tunggu, maksud saya perakitan, kalau tidak Anda hanya menggunakan bahasa tingkat rendah orang lain. Oh, tunggu, maksudku membalik saklar untuk mengubah sirkuit listrik, jika tidak, kamu hanya menggunakan set instruksi orang lain. Atau Anda tahu, Anda bisa menggunakan apa yang sudah ada di sana dan bekerja untuk menciptakan sesuatu yang baru . Mengapa membuang-buang waktu menciptakan kembali algoritma Dijkstra ketika Anda dapat menemukan sesuatu yang baru, seperti program yang menggunakannya?
Pasang kembali Monica
54

Apakah ini jenis hal yang harus dapat "diciptakan kembali" oleh programmer yang baik dalam beberapa jam atau apakah saya tidak realistis?

Pertama, Anda mungkin membingungkan pemrograman dengan ilmu komputer teoretis. Seorang programmer yang hebat membutuhkan dasar yang bagus dalam ilmu komputer tetapi dia tidak perlu menjadi fantastis. Dijkstra luar biasa dalam ilmu komputer.

Kedua, saya mengharapkan siapa pun dengan pemahaman grafik yang baik untuk mengembangkan grafik traversal mereka sendiri setelah berpikir sebentar. Tapi bukan algoritma jalur terpendek. Algoritma Dijkstra khususnya sangat canggih. Setelah Anda memahaminya, itu sangat jelas. Tetapi kebanyakan hal seperti itu.

Anda mungkin dapat memperoleh beberapa jenis algoritma jalur terpendek setelah mencoba beberapa hal dan memberikan ide beberapa saat. Tetapi jangan kecewa jika itu membutuhkan waktu berjam-jam, atau bahkan beberapa hari. Ini sepenuhnya OK dan normal.

(Peringatan: well, Anda harus bisa memaksa masalah dalam beberapa jam puncak, tetapi ini tidak akan menghasilkan algoritma yang bekerja bahkan pada grafik yang cukup kecil.)

Konrad Rudolph
sumber
56
Jangan khawatir, jika brute force tidak berfungsi, Anda tidak cukup menggunakannya.
Robbie
2
+1 untuk melihat perbedaan antara CS teoretis dan pemrograman. Pemrograman adalah pemecahan masalah dunia nyata, dan CS teoritis ada untuk mendukung pemrograman. Namun CS teoritis tidak 100% esensial dalam pemrograman sehari-hari kebanyakan orang.
Phil
17

Apakah ini jenis hal yang harus dapat "diciptakan kembali" oleh programmer yang baik dalam beberapa jam atau apakah saya tidak realistis?

Jelas tidak realistis. Orang tidak hanya "muncul" dengan algoritma dalam beberapa jam. Dibutuhkan banyak usaha dan kerja keras. Mengutip blog ini :

Dalam Pemrograman Mutiara, Bentley, mengutip Donald Knuth, mengatakan "Sementara pencarian biner pertama kali diterbitkan pada tahun 1946, pencarian biner pertama yang bekerja dengan benar untuk semua nilai n tidak muncul sampai 1962."

dan versi Bentley juga bermasalah ketika diimplementasikan untuk set besar.

Selain itu, seorang programmer yang baik tahu alat apa yang tersedia dan kapan harus menggunakan alat tersebut. Anda tidak mendapatkan poin ekstra untuk orisinalitas atau melakukan hal-hal berbeda - Anda ingin itu berfungsi dan bekerja dengan baik.

Selikuran
sumber
1
BlackJack, saya harus bergabung dengan forum ini untuk menunjukkan bahwa Bentley tidak mengatakan apa yang Anda katakan, katanya: Knuth mengatakannya, dan Bentley mengutipnya. Ketika saya membaca komentar Anda, saya pikir Anda telah membuat poin bagus, tetapi saya ingin memverifikasi sumber saya dan belum pernah mendengar tentang Bentley. Namun, saya pernah mendengar tentang Knuth dan bisa memercayai apa yang dia katakan. Silakan periksa sumber Anda lebih baik lain kali.
Richard
8
@ Richard - Komentarnya adalah "Dalam Pemrograman Mutiara, Bentley mengatakan .." Knuth adalah orang pertama yang mengatakannya, tetapi sumber saya Pemrograman Mutiara, bukan TAoCP, jadi saya menulis apa yang ditulis Bentley. Saya tidak mengklaim bahwa Bentley adalah pencetusnya - saya hanya mengutip apa yang dikatakan dalam buku itu. Banyak materi dalam buku tidak ditemukan oleh penulis sendiri, jadi saya tidak mengerti mengapa Anda melihatnya seperti itu.
BlackJack
Dengan mengaitkan penawaran hanya kepada Bentley Anda gagal karena kredit Knuth dan, jika pernyataan "Bentley" salah, Anda menempatkan Bentley pada posisi menghasilkan informasi yang salah, bukan hanya menyebarkannya. Sebenarnya, Anda tidak mengatakan apa yang dikatakan Bentley: jika Anda melakukannya, Anda akan mengatakan, "Bentley mengatakan bahwa Knuth mengatakan itu ...". Kutipan ini digunakan dengan baik di sini, tetapi kutipan itu diambil dari konteks di mana dikatakan.
Richard
3
@ Richard - Kutipan yang saya cantumkan adalah langsung dari blog, yang mengutip langsung dari buku (secara harfiah, saya pikir itu halaman 57 dari edisi pertama). Jika Anda memiliki masalah sebanyak ini dengan pernyataan tersebut, maka hubungi pembuat blog dan minta dia mengubahnya.
BlackJack
1
@ Richard dan BlackJack: Anda berdua benar, tetapi atribusi ke penulis asli menambah kepercayaan dan konteks pada pernyataan. Hasil edit saya harus memadai.
Steven Evers
9

Sangat tidak mungkin Anda dapat menemukan solusi yang lebih baik daripada yang bisa Anda pilih.

Keluar dengan algoritma yang lebih baik daripada yang dianggap "yang terbaik" (dalam kasus Anda, yang terpendek) bukanlah sesuatu yang dapat dilakukan semua orang. Mungkin itu bahkan tidak mungkin.

Seorang programmer yang baik harus dapat memahami logika di balik algoritma, dan mengapa itu lebih baik atau lebih buruk (atau hanya tidak cukup untuk masalah khusus itu) daripada algoritma lain yang mencoba untuk memecahkan masalah yang sama.

(s) Ia harus juga dapat mengetahui apakah itu benar-benar cara terbaik untuk menyelesaikan masalah khusus itu.

Pokoknya jika Anda ingin berlatih, Anda masih bisa mencoba menulis implementasi algoritma pribadi Anda, mencoba menyelesaikan masalah menggunakan pikiran Anda. Ini mungkin bukan yang terbaik, tetapi ini adalah praktik yang baik untuk pemecahan masalah.

Jose Faeti
sumber
6

Ini mengingatkan saya pada sesuatu yang saya baca tentang perbedaan antara "rekayasa perangkat lunak" (apa yang saya sebut pemrograman) dan disiplin ilmu teknik lainnya. Kalau dipikir-pikir, saya pikir itu adalah buku Pola Desain asli. Saya yakin seseorang di sini dapat mengutipnya dari atas kepalanya.

Pokoknya, intinya (meskipun tidak sepenuhnya diarahkan pada desain algoritma) adalah bahwa disiplin ilmu teknik dikodifikasi; tidak ada insinyur sipil yang cenderung menghabiskan waktu untuk mencoba menemukan kembali berkas-I, tetapi pemrogram selalu melakukannya. Masalahnya (dan saya menyadari bahwa saya hanya menggemakan sentimen banyak orang) adalah bahwa perilaku ini boros dan rentan kesalahan, dan melayani ego lebih dari solusi.

Ilmu komputer membimbing saya ke pemrograman, dan saya suka keduanya. Namun, saya seorang programmer yang jauh lebih baik daripada ilmuwan komputer. Saya tidak akan pernah menuduh Anda tidak kompeten karena Anda tidak dapat menemukan kembali algoritma Dijkstra dalam satu sore. Saya akan mempertanyakan kompetensi Anda sebagai programmer jika Anda tidak dapat mengenali masalah yang dapat diselesaikan melalui algoritma grafik jalur terpendek.

Yang mengatakan, saya percaya bahwa berpikir tentang algoritma dan mencoba untuk merancang dan mengimplementasikan yang baru (berpotensi) menyenangkan dan (hampir) selalu instruktif. Saya hanya mencoba untuk memisahkan waktu CS saya dari waktu pemrograman saya. Untuk programmer, waktu kita (terutama yang dibayar) lebih baik dihabiskan untuk menyelesaikan masalah-masalah praktis daripada yang asbtract. Selain itu, waktu CS hampir selalu menghancurkan kepercayaan diri saya.

Keith Layne
sumber
Oh ironisnya ... sekarang saya bisa berkomentar di mana saja, haruskah saya menghapus jawaban yang memberi saya hak istimewa itu? Seharusnya ada lencana untuk itu.
Keith Layne
Namun - Disiplin , jika reputasi Anda dihitung ulang, Anda akan kembali ke 1.
ChrisF
Ya, itulah tepatnya poin saya ... Saya akan melampaui dan melampaui disiplin pada saat itu IMO. Jika saya mengonversi jawaban saya menjadi komentar sebelum dihapus, saya dapat memiliki semuanya ... Saya menyarankan lencana baru yang disebut UberDisiplinkan untuk penghapusan apa pun yang menyebabkan Anda kembali ke status pengguna baru. :)
Keith Layne
3

Anda tidak akan memperhatikan hal-hal yang sama seperti yang dilakukan orang lain. Saya pikir itu hanya fakta kehidupan yang harus kita jalani. Sebagian besar berasal dari pembelajaran pasif Anda dan model mental yang telah Anda kembangkan sebagai akibatnya.

Saya kenal beberapa programmer yang sangat cerdas dan kompeten yang harus diajarkan hukum DeMorgan di sekolah sebelum mereka bisa melakukannya secara konsisten. Saya kebetulan mengetahui Algoritma Dijkstra sendiri (dan saya harus mengakui bahwa saya sedikit bangga akan hal itu), tetapi butuh waktu yang sangat lama sampai saya bahkan bisa memahami semacam gelembung.

Lebih terkenal, Einstein, yang Anda pikir akan menjadi ahli dalam teori simpul, tidak bisa mengikat tali sepatu sendiri sampai dia berusia sekitar sepuluh tahun.

Kemungkinannya bagus bahwa Anda secara tidak sadar telah menemukan kembali banyak hal yang tidak akan pernah dipikirkan oleh banyak orang lain seandainya mereka tidak diajarkan secara eksplisit.

Rei Miyasaka
sumber
3

Saya mohon berbeda untuk apa yang sebagian besar jawaban katakan. Sementara saya tidak akan mengharapkan seorang programmer dari level mana pun untuk dapat muncul sendiri pada algoritma Dijkstra, saya pasti akan mengharapkan dia untuk datang dengan cara apa pun (efisien atau tidak) untuk menyelesaikan masalah.

Misalnya, Anda mengatakan sebagai komentar sampingan bahwa Anda dapat membuat semacam gelembung sendiri. Saya tahu ini adalah algoritma penyortiran yang paling sulit, tetapi Anda menemukan cara untuk memecahkan masalah, dan itulah yang saya harapkan para programmer dapat: menemukan cara untuk memecahkan masalah.

Tentu saja, menyelidiki dan menemukan solusi yang dilakukan oleh orang lain juga berhasil, tetapi hal yang paling ekstrem adalah seorang pria yang tidak memikirkan dirinya sendiri dan program-programnya merupakan ringkasan pencarian Google.

Saya pikir saya terdengar lebih keras daripada yang sebenarnya saya inginkan, tetapi poin saya adalah: Saya berharap seorang programmer cukup kreatif untuk menghasilkan solusi untuk suatu masalah, bahkan jika solusinya buggy atau berantakan.


Jadi, kembali ke kasus Anda, saya tidak berpikir Anda harus datang dengan algoritma Dijkstra, tetapi jika Anda memiliki kemampuan untuk menulis algoritma untuk mencoba beberapa kemungkinan dan menemukan jalur terpendek tanpa berakhir pada loop tak terbatas, maka Anda sudah mendapat persetujuan saya.

(BTW persetujuan saya diperhitungkan dalam urutan yang sama pentingnya dengan kupon cuci mobil gratis.)

Alfa
sumber
3
Saya setuju bahwa ya, seorang programmer yang kompeten harus dapat memunculkan bubble sort atau yang setara. Bahkan mungkin merupakan penggunaan waktu yang produktif untuk benar-benar mengimplementasikannya dan mencobanya, mungkin hanya untuk memahami masalahnya dengan lebih baik. Tapi saya pikir perlu dikatakan bahwa tidak ada programmer yang kompeten yang akan melanjutkan dan benar-benar menggunakannya dalam kode produksi. Melakukan hal itulah yang membuat pelanggan Anda kembali tahun depan dan mengeluh bahwa, sekarang mereka memiliki lebih banyak data untuk diproses, algoritme O (n!) Anda akan membutuhkan waktu dua kali lipat jagat raya ...
Thomas Padron-McCarthy
Siapa yang peduli jika Anda dapat menemukan algoritma, jika Anda bahkan tidak bisa mengenali ketika itu menyebalkan? Mengkritik diri sendiri sama pentingnya bagi seorang programmer dengan kreativitas. Saya lebih suka bekerja dengan seorang programmer yang cepat mengakui ketika mereka tahu solusi mereka sendiri terlalu lama atau tidak mungkin menjadi yang terbaik, daripada dengan seorang programmer yang ingin menemukan kembali setiap roda karena memar ego mereka untuk melakukan sebaliknya.
Rei Miyasaka
Saya setuju pada kedua poin, tetapi saya pikir kita mengukur dua hal yang berbeda. Salah satunya adalah kemampuan bagi programmer untuk memecahkan masalah (sesuatu yang saya anggap penting). Lainnya adalah kritik-diri (saya menganggap ini penting tetapi tidak untuk pemrograman: seumur hidup) dan kemampuan untuk menilai kode (sangat diinginkan). Saya juga akan mengatakan bahwa solusi yang membutuhkan waktu lama bukanlah solusi, bukan? ;)
Alpha
2

Ya, dia harus.

Mungkin ini setara dengan moral bubble sort, tapi saya pikir seorang programmer yang baik harus bisa menghasilkan setidaknya sesuatu yang berfungsi, betapapun tidak efisiennya.

Tak perlu dikatakan, jika masalah tertentu akan muncul programmer yang baik pertama-tama akan melihat apakah ada perpustakaan untuk melakukannya untuknya, atau algoritma yang diterbitkan melakukan itu dan mudah diimplementasikan.

Tentu saja, banyak tugas pemrograman tidak terlalu sulit dan tidak semua orang harus mampu mengatasi masalah sulit seperti itu. Tetapi Anda ingin memiliki seseorang dengan pikiran seperti itu di tim Anda, karena Anda mungkin memiliki beberapa masalah spesifik proyek yang rumit di mana Anda tidak dapat mengandalkan banyak penelitian ilmiah sebelumnya.

Hans-Peter Störr
sumber
1

Jangan khawatir

Sebagai seorang Programer Perl, saya hampir tidak pernah menemukan kembali roda. Itu adalah pekerjaan CPAN. Jika ada algoritma atau modul yang sederhana dan didukung dengan baik, kami menggunakannya. Jika tidak ada modul yang baik, maka kami menciptakan roda. Itu adalah salah satu hal terbesar tentang Perl.

Jadi yang saya katakan adalah ini:

  1. Saya tidak merekomendasikan menciptakan kembali roda tetapi ketika Anda melakukannya ...
  2. Cobalah untuk tidak sepenuhnya menciptakan kembali dan ...
  3. Jangan khawatir jika Anda tidak bisa melakukannya. Itu sebabnya kami memiliki komunitas pemrograman :-).
Dinamis
sumber
Ini bukan tentang menciptakan kembali, ini adalah tentang menyelesaikan masalah secara umum. Jika Anda tidak mencoba untuk menciptakan barang-barang Anda sendiri, Anda tidak akan pernah membaik.
Nils
0

Teori grafik, dan algoritma yang berlaku untuk itu, terlihat sederhana di permukaan tetapi umumnya jauh dari itu. Anda akan berpikir pembentukan grafik non-persimpangan (planar) sederhana, misalnya, pada pandangan pertama. Tahun lalu saya melihat secara luas masalah ini (planaritas melalui penghapusan subgraph Kuratowski). Saya dapat memberi tahu Anda, dari pengalaman itu, bahwa orang-orang yang menulis algoritma ini biasanya menghabiskan durasi studi PhD mereka, dan kadang-kadang penelitian itu dilakukan dalam tim. Dan sebagai peneliti , itulah satu-satunya fokus kerja mereka selama periode waktu itu. Tidak masuk akal untuk berpikir bahwa para insinyur di lapangan dapat mengharapkan hal yang sama. Seperti orang lain di sini katakan dengan benar, itu sangat jelas setelah solusinya ada di depan Anda. Sepertinya selalu begitu!

Insinyur
sumber
0

Apakah ini jenis hal yang harus dapat "diciptakan kembali" oleh programmer yang baik dalam beberapa jam atau apakah saya tidak realistis?

Saya akan mengatakan bahwa jika Anda dapat menemukan algoritma untuk masalah terkenal seperti Shortest Path sendiri, Anda menjadi programmer yang buruk .

Itu berarti Anda mengabaikan sejarah pada masalah Shortest Path , pergi dari algoritma O (| V | ^ 4) yang diterbitkan pada tahun 1955 ke algoritma O (E + V log V) yang diterbitkan pada tahun 1984 (yang merupakan Dijkstra's algoritma dengan pohon Fibonacci). Anda hampir dijamin melakukan lebih buruk daripada algoritma yang telah dirancang. Lebih buruk lagi, ada kemungkinan besar algoritma Anda memiliki kesenjangan atau kesalahan sehingga membuatnya salah. Selain itu, Anda hampir pasti akan menghabiskan lebih banyak waktu memikirkan algoritma Anda, mengimplementasikannya dan mengujinya daripada waktu yang diperlukan untuk menggunakan kembali algoritma yang ada.

Serahkan desain algoritme kepada desainer algoritme. Programmer adalah konsumen dari hasil mereka. Pemrogram menggabungkan algoritma dan membuatnya bekerja pada tugas-tugas dunia nyata. Seorang perwira polisi tidak perlu dapat menemukan kembali hukum untuk dapat bekerja, atau menjadi petugas yang baik.

Saya bahkan mendorong Anda untuk menggunakan implementasi yang dibuat oleh para ahli daripada mengimplementasikan sendiri algoritma untuk algoritma yang cukup rumit. Ini lebih cenderung benar, kemungkinan mereka membuatnya lebih cepat daripada yang pernah Anda lakukan dan itu menghemat banyak waktu. Ini terutama berlaku untuk algoritma kriptografi, karena Anda mendapatkan permintaan keamanan tambahan, yang biasanya hanya disediakan oleh para ahli.

Alex ten Brink
sumber
Algoritma kriptografi mudah untuk memverifikasi implementasi; vektor uji yang dikenal benar adalah selusin sepeser pun untuk setiap algoritma yang ditentukan secara publik, dan itu benar atau tidak. (Anda mungkin mendapatkan kinerja suboptimal dengan implementasi kustom, tetapi jika itu hanya benar, itu dapat dikerjakan.) Bagian yang sulit dalam kriptografi adalah hal-hal seperti pembuatan angka acak, penanganan yang tepat dari kunci mentah dan tabel ekspansi kunci dalam memori, benar penanganan input pengguna (pengasinan, dll.), menyimpan sesuatu untuk memungkinkan Anda mengetahui apakah data yang didekripsi valid, dan sebagainya.
CVn
Saya berpikir lebih banyak tentang serangan timing dll, hal-hal yang hampir tidak diketahui oleh programmer. Itu tidak selalu menjadi masalah, tetapi yang penting tetap saja. Selain itu, menggabungkan kriptografi primitif biasanya tidak berfungsi seperti yang diharapkan, ini juga merupakan bagian sulit dari keamanan.
Alex ten Brink
Sementara serangan waktu dll tentu saja merupakan kekhawatiran yang valid (dan tidak hanya dalam kriptografi), saya berpendapat bahwa kerentanan implementasi terhadap hal tersebut tidak berdampak pada kebenarannya . Dan ada banyak, banyak cara untuk melakukan kesalahan dalam cara kriptografi lebih dari sekedar mengaktifkan serangan waktu. Bruce Schneier biasa menjalankan seri Doghouse- nya; Saya belum melihat apa pun di dalamnya baru-baru ini, tetapi ada banyak contoh peringatan di sana. google.com/search?q=site%3Aschneier.com+%22the+doghouse%22
a CVn