Saya pikir, di Habré ada penggemar seri Silicon Valley . Minggu ini, untuk pertama kalinya dalam semua enam musim, mereka menunjukkan kode besar - tentu saja, saya langsung ingin membahasnya di sini.
Ingin mempermalukan karakter utama Richard Hendrix, mantan bosnya menunjukkan pada sebuah pertemuan potongan kode lamanya. Di sana, pencarian linier diterapkan ke data yang sudah diurutkan - sehingga tugas akan selesai, tetapi terlihat sangat tidak efisien.
Richard sendiri tidak berpendapat bahwa kode itu buruk. Namun, di antara pemirsa seri, keputusannya tiba-tiba menemukan pembela, dan sekarang saya bertanya-tanya apa pendapat Habr tentang posisi mereka.
Cuplikan kode Richard yang dikenal terlihat seperti ini:
int index = 0; while (!element.equals(sortedList.get(index)) && sortedList.size() > ++index); return index < sortedList.size() ? index : -1;
Di sini, pencarian linear bergiliran ke setiap elemen dari beberapa daftar yang diurutkan, hingga mencapai yang benar. Sebagai aturan, mereka lebih suka pencarian biner pada data yang diurutkan, yang setiap kali membagi set menjadi setengah, membuang setengah yang tidak sesuai secara keseluruhan (karena dengan peningkatan volume data, jumlah iterasi dalam linear meningkat jauh lebih cepat daripada dalam biner). Tetapi dalam subreddit / r / SiliconValleyHBO komentar berikut muncul:
"Saya ingin belajar sedikit dan menunjukkan bahwa" kesalahan "Richard dalam menggunakan pencarian linier daripada pencarian biner pada data yang diurutkan sebenarnya ternyata lebih produktif dalam banyak kasus. Dengan dataset raksasa (saya pikir ambangnya ada pada jutaan elemen) pencarian biner lebih cepat. Tetapi secara umum, jika dataset Anda tidak besar, pencarian linier akan lebih baik di-cache oleh prosesor, lebih cocok untuk prediktor cabang, dan algoritma Anda juga bisa di-vektor. Pencarian linear membutuhkan lebih banyak iterasi, tetapi masing-masing lebih cepat dari iterasi pencarian biner. Ini berlawanan dengan intuisi dan bertentangan dengan semua yang diajarkan pada Anda di universitas, tetapi ternyata demikian.
Laporan ini sangat menarik dan menunjukkan beberapa hasil pengukuran kinerja nyata yang menakjubkan. "
Dan anggota lain dari thread mendukung komentator: ya, dalam teori, semua iterasi adalah setara, tetapi pada perangkat keras nyata dengan optimasi nyata, semuanya benar-benar berbeda. Seperti, pencipta seri, Mike Judge, bekerja di Lembah kembali di tahun 80-an, ketika semua cache L1 dan prediksi cabang belum diucapkan secara khusus, sehingga perilaku CPU jauh lebih dekat dengan model ideal - ini adalah contoh dalam seri.
Bagi saya, seperti yang dikatakan dalam komentar, semuanya kedengarannya berlawanan dengan intuisi, tetapi menjadi menarik untuk mengetahui apakah Richard benar. Tentu saja, itu mengganggu fakta bahwa tidak seluruh konteks diberikan dalam seri: misalnya, kita tidak tahu berapa banyak data yang diulang. Di satu sisi, Richard kemudian bekerja untuk raksasa internet Hooli, di mana ia mungkin harus berurusan dengan jutaan catatan, tetapi di sisi lain, itu adalah hari kerja pertamanya, dan ia tidak bisa langsung dibuang ke jutaan. Kami mengajukan pertanyaan seperti ini: bahkan jika pencarian biner jelas lebih baik untuk sebagian besar tugas di Hooli, mungkinkah Richard membuat keputusan yang tepat untuk kondisinya dan karakter lain menertawakannya dengan sia-sia, tidak mengetahui konteksnya?
Untuk memahami, saya membuka laporan yang dikutip oleh Reddit. Seperti yang dijanjikan, ternyata menarik (tidak mengejutkan, mengingat bahwa ini adalah laporan oleh Andrei Alexandrescu ), tetapi setelah melihat bagian dan mengklik sisanya, saya tidak melihat pengukuran perbandingan pencarian biner dan linear di sana.
Tetapi saya ingat bahwa pada konferensi DotNext kami, Alexandrescu yang sama juga berbicara tentang kinerja. Saya membuka versi teks laporannya, yang kami buat untuk Habr, dan mencari kata "linear". Ternyata, antara lain, itu hanya memberikan contoh skenario aneh di mana pencarian ini akan jauh lebih efektif daripada yang biner (mencari elemen yang cocok dari dua set dalam kasus ketika set ini identik) - tetapi ini adalah kasus yang sangat spesifik, yang tidak ada kesimpulan umum " pencarian linier diremehkan. "
Googled apa yang dikatakan Internet modern tentang ini - tetapi pada dasarnya menemukan jawaban Stack Overflow, di mana mereka hanya menulis "gunakan biner, kurangi iterasi." Ada juga kasus di mana mereka mencoba melakukan benchmark, tetapi juga tidak terlihat meyakinkan bagi saya.
Di sini, tentu saja, opsi ini meminta "Anda harus membandingkan diri sendiri untuk melihat semuanya sendiri di perangkat keras yang sebenarnya."
Tetapi jika untuk semua kunjungan saya ke DotNext saya belajar sesuatu dari dua Andreev yang sadar-kinerja (Alexandrescu dan Akinshina ), ini merupakan realisasi dari seberapa sering orang melakukan benchmark secara tidak benar dan berapa banyak yang tidak mereka perhitungkan. Oleh karena itu, saya memiliki kepercayaan yang rendah pada posting Internet acak dengan tolok ukur, tetapi untuk diri saya bahkan lebih rendah.
Untungnya, ada orang-orang di Habr yang jauh lebih mengerti daripada saya (misalnya, Andrey DreamWalker yang sama Akinshin, yang menulis seluruh buku tentang benchmarking). Karena itu, jika Anda mengerti topiknya - beri tahu kami di komentar bagaimana semuanya sebenarnya. Untuk ukuran data apa pendekatan linear masih bisa menjadi pilihan yang baik? Seberapa besar kemungkinan Richard melakukan segalanya dengan benar, bahkan jika dia sendiri tidak siap untuk mempertahankannya?
Dan jika tidak ada komentator yang berpengetahuan, saya harus melampirkan Akinshin ke baterai pada DotNext berikutnya dan membuat tolok ukur.