Kapan 'mengoptimalkan kode' == 'menyusun data'?

Artikel terbaru oleh ycombinator mencantumkan komentar dengan prinsip-prinsip seorang programmer hebat.

#7. Pemrogram yang baik: Saya mengoptimalkan kode. Programmer yang lebih baik: Saya menyusun data. Programmer terbaik: Apa bedanya?

Mengakui konsep subyektif dan kontroversial - apakah ada yang punya posisi tentang apa artinya ini? Ya, tapi saya ingin mengedit pertanyaan ini nanti dengan pikiran saya agar tidak mempengaruhi jawaban.

Sembilan dari sepuluh, ketika Anda menyusun kode / model dengan baik, optimasi akan menjadi jelas. Berapa kali Anda melihat sarang lebah dan menemukannya benar-benar suboptimal, di mana setelah merestrukturisasi, banyak redudansi menjadi sangat jelas.

Seorang desainer tahu ia telah mencapai kesempurnaan bukan ketika tidak ada lagi yang tersisa untuk ditambahkan, tetapi ketika tidak ada lagi yang tersisa untuk diambil. - Antoine de Saint-Exupery

Sistem yang terstruktur dengan baik akan bersifat minimal, dan karena sifatnya yang minimal, sistem ini akan dioptimalkan karena seberapa kecil ada yang terkait langsung dengan seberapa sedikit yang dilakukannya untuk mencapai tujuannya.

Sunting: Untuk menguraikan pada titik yang diambil orang lain dari ini, itu juga sepenuhnya akurat untuk melihat pernyataan sebagai mengidentifikasi hubungan antara kode dan data. Karenanya, relasi itu: Jika Anda mengubah struktur data Anda, Anda perlu mengubah kode Anda untuk menghormati struktur yang diubah. Jika Anda ingin mengoptimalkan kode Anda, kemungkinan Anda perlu mengubah struktur data Anda agar kode Anda mampu menangani data lebih optimal.

Yang mengatakan, ada kemungkinan yang benar-benar terpisah yang sedang dihindari di sini, dan itu adalah bahwa orang yang memiliki hubungan dengan YCombinator ini mungkin merujuk pada data kode AS dalam tradisi LISP tentang homoikonisitas. Sangat sulit untuk menduga ini sebagai makna dalam pikiran saya, tetapi ini adalah YCombinator sehingga saya tidak akan mengesampingkan bahwa kutipan tersebut hanya mengatakan LISPers adalah "Programmer Terbaik".

Saya pikir penulis mengisyaratkan bahwa setiap restrukturisasi data mengarah pada restrukturisasi kode. Karenanya, merestrukturisasi data dengan tujuan mengoptimalkan sistem Anda akan memaksa Anda untuk mengoptimalkan kode Anda juga, mendorong "apa bedanya?" tanggapan.

Perhatikan bahwa "programmer uber-excellent" dapat menjawab "apa bedanya?" bahwa ada beberapa perbedaan yang tersisa di sana: setelah Anda berani mengoptimalkan penggunaan cache CPU yang lebih baik, Anda dapat menjaga tata letak struktur data Anda tetap sama, tetapi mengubah urutan di mana Anda mengaksesnya dapat membuat banyak perbedaan.

Pertimbangkan contoh paling jelas tentang ini - "mencari data pengguna terlalu lambat!"

Jika data pengguna Anda tidak diindeks atau setidaknya diurutkan, maka restrukturisasi data Anda akan dengan cepat menghasilkan peningkatan kinerja kode. Jika data terstruktur dengan benar dan Anda hanya mengulangi melalui koleksi (daripada menggunakan indeks atau melakukan sesuatu seperti pencarian biner) maka memodifikasi kode menghasilkan peningkatan kinerja kode.

Programmer adalah pemecah masalah. Meskipun berguna untuk membedakan antara algoritma dan struktur data, mereka tidak sering ada dalam isolasi. Pemrogram terbaik tahu ini, dan tidak mengisolasi diri mereka sendiri jika tidak perlu.

Saya tidak setuju dengan pernyataan yang disebutkan di atas, paling tidak tanpa penjelasan. Saya melihat pengkodean adalah kegiatan yang melibatkan pemanfaatan beberapa struktur data. Struktur data umumnya akan mempengaruhi pengkodean. Jadi ada perbedaan antara keduanya menurut saya.

Saya pikir penulis seharusnya menulis bagian terakhir sebagai "Programer terbaik: Saya mengoptimalkan keduanya."

Ada buku yang bagus (paling tidak ketika diterbitkan) yang disebut: Algoritma + Struktur Data = Program .

Mengoptimalkan kode kadang-kadang dapat meningkatkan kecepatan dengan faktor dua, dan kadang-kadang dengan faktor sepuluh atau bahkan dua puluh, tapi itu saja. Itu mungkin terdengar seperti banyak, dan jika 75% dari waktu pelaksanaan program dihabiskan dalam rutinitas lima baris yang kecepatannya dapat digandakan, optimasi seperti itu mungkin layak dilakukan. Di sisi lain, pemilihan struktur data seseorang dapat memengaruhi kecepatan eksekusi oleh banyak urutan besarnya. Prosesor multi-ulir modern yang dioptimalkan untuk hiper yang menjalankan kode super-dioptimalkan untuk mencari data dengan kunci dalam 10.000.000 item daftar terkait linier yang disimpan dalam RAM akan lebih lambat daripada prosesor yang jauh lebih lambat yang menjalankan tabel hash bersandi yang cukup sederhana. Memang, jika seseorang memiliki data yang ditata dengan benar, bahkan tahun 1980 '

Yang telah dikatakan, mendesain struktur data yang efisien seringkali membutuhkan pertukaran yang lebih kompleks daripada mengoptimalkan kode. Misalnya, dalam banyak kasus, struktur data yang memungkinkan data diakses secara paling efisien kurang efisien untuk diperbarui (kadang-kadang berdasarkan urutan besarnya) daripada yang memungkinkan pembaruan cepat, dan yang memungkinkan pembaruan tercepat memungkinkan akses paling lambat. Lebih lanjut, dalam banyak kasus, struktur data yang optimal untuk kumpulan data besar mungkin relatif tidak efisien dengan yang kecil. Seorang programmer yang baik harus berusaha untuk menyeimbangkan faktor-faktor yang bersaing dengan jumlah waktu programmer yang diperlukan untuk mengimplementasikan dan memelihara berbagai struktur data, dan mampu mencapai keseimbangan yang layak di antara mereka.

Struktur data mendorong banyak hal relatif terhadap kinerja. Saya pikir kita dapat melihat masalah dengan panjang dan panjang dengan ide yang terbentuk sebelumnya tentang struktur data yang ideal, dan dalam konteks pemikiran ini, bahkan membuat bukti (seringkali dengan induksi) optimalitas. Misalnya, jika kita meletakkan daftar yang diurutkan ke dalam array dan mengevaluasi hal-hal seperti biaya untuk memasukkan elemen, kita mungkin memutuskan rata-rata kita perlu menggeser 1/2 dari array untuk setiap penyisipan. Untuk setiap pencarian biner , kami dapat menemukan item yang cocok (atau tidak) dalam log n langkah.

Sebagai alternatif, jika kita menunda keputusan tentang struktur data (menghindari optimasi prematur ) dan mempelajari data yang masuk dan konteks di mana kita akan menggunakannya, seberapa besar itu, latensi apa yang terjadi dan mana yang penting bagi pengguna, berapa banyak memori yang kita miliki vs. akan digunakan dengan representasi data yang kita tahu atau dapat rancang.

Di bidang seperti penyortiran dan pencarian, ada banyak hal yang perlu diketahui. Benar-benar programmer hebat telah mengerjakan ini sejak lama. Memahami masalah-masalah ini dengan baik bermanfaat, dan itu adalah hal yang hebat jika Anda tahu lebih banyak metode daripada ketika Anda selesai kelas struktur data sarjana. Pohon biner dapat memberikan kinerja yang unggul untuk pemasangan dengan imbalan penggunaan memori yang lebih tinggi. Tabel hash memberikan peningkatan yang lebih besar, tetapi untuk lebih banyak memori. Pohon radix dan jenis radix dapat membawa perbaikan lebih jauh.

Penataan data secara kreatif dapat membantu membingkai ulang masalah dan membuka pintu bagi algoritme baru yang membuat aplikasi sulit lebih cepat dan terkadang tugas yang mustahil menjadi mungkin.

Untuk mengartikulasikan tebakan terbaik saya pada apa arti artikel itu, saya akan mengasumsikan subteks tak terucapkan (yang tampaknya hilang dalam artikel) bahwa setiap programmer harus mengerti tentang optimasi:

• optimisasi muncul hanya setelah Anda menjalankan dan menjalankan program dengan benar:
  • membuatnya berjalan dengan benar, lalu membuatnya berlari cepat
  • prinsip ini adalah poin dari pepatah Knuth, "optimasi prematur adalah akar dari semua kejahatan"
• jika dan ketika Anda telah menentukan bahwa pengoptimalan tidak prematur, Anda harus mengukurnya dengan benar terlebih dahulu untuk menentukan apa yang sebenarnya perlu dioptimalkan, dan berulang kali selama pengoptimalan, untuk mengetahui efek apa yang dimiliki upaya pengoptimalan Anda.
  • jika kode Anda berjalan dalam pengembangan, profiler adalah teman Anda dalam hal ini.
  • jika kode Anda berjalan dalam produksi, Anda harus memasukkan kode Anda, dan berteman dengan sistem logging Anda.

Sekarang, lalu: pengukuran Anda akan memberi tahu Anda di mana dalam kode Anda mesin paling banyak membakar siklus. Seorang programmer "baik" akan fokus pada mengoptimalkan bagian-bagian kode, daripada membuang-buang waktu mengoptimalkan bagian-bagian yang tidak relevan.

Namun, Anda sering dapat memperoleh keuntungan yang lebih besar dengan melihat sistem secara keseluruhan, dan menemukan beberapa cara untuk memungkinkan mesin melakukan lebih sedikit pekerjaan. Seringkali, perubahan ini membutuhkan pengerjaan ulang organisasi data Anda; dengan demikian, seorang programmer "lebih baik" akan mendapati dirinya menyusun data lebih sering daripada tidak.

"Programmer terbaik" akan memiliki model mental menyeluruh tentang cara kerja mesin, landasan yang baik dalam desain algoritma, dan pemahaman praktis tentang bagaimana mereka berinteraksi. Ini memungkinkan dia untuk mempertimbangkan sistem sebagai keseluruhan yang terintegrasi - dia tidak akan melihat perbedaan antara mengoptimalkan kode dan data, karena dia mengevaluasi mereka pada tingkat arsitektur.

Programmer terbaik: Apa bedanya?

Programmer terbaik? Tidak, programmer yang buruk. Saya mengasumsikan kata "optimasi" berarti hal-hal yang biasanya dioptimalkan oleh pemrogram, waktu memori atau CPU. Dalam hal ini, optimasi bertentangan dengan hampir semua metrik perangkat lunak lainnya. Dapat dimengerti, rawatan, dapat diuji, dll. Ini semua memerlukan sedikit perhatian ketika pengoptimalan adalah tujuannya - kecuali yang ingin dioptimalkan adalah pemahaman manusia, rawatan, uji, dll. Belum lagi biaya. Menulis algoritma kecepatan / ruang optimal biayanya jauh lebih banyak dalam hal waktu pengembang daripada pengkodean algoritma secara naif seperti yang disajikan dalam beberapa teks atau jurnal. Seorang programmer yang buruk tidak tahu bedanya. Yang bagus tidak. Pemrogram terbaik tahu bagaimana menentukan dengan tepat apa yang perlu dioptimalkan dan melakukannya dengan bijaksana.