Dari 10 hingga 22 September, kontes pengembangan ponsel Yandex.Blitz akan diadakan. Pendaftaran
terbuka . Blitz adalah cara singkat untuk Yandex: 5 peserta teratas harus berhasil melewati satu bagian wawancara, bukan empat standar untuk mendapatkan tawaran pekerjaan.
Pada kesempatan kontes, kami berbicara dengan kolega tentang tugas menarik yang langsung diterapkan ke platform dan algoritme seluler. Hari ini kami akan berbagi kisah mereka dengan pembaca Habr.
Dipercayai bahwa pengembangan aplikasi mobile adalah sesuatu yang istimewa, jauh dari pemrograman dalam pengertian umum, dan spesialis yang menulis untuk Android dan iOS tidak pernah menemui penyelesaian tugas algoritma yang intensif, membatasi diri mereka untuk menghubungkan perpustakaan yang sudah jadi, layar penyusunan huruf, menulis logika bisnis sederhana dan meneliti bug dari platform tertentu. Tapi tidak sesederhana itu.
Membuat perangkat lunak untuk perangkat seluler selalu penuh dengan keterbatasan. Bahkan di perangkat kelas atas, CPU dan GPU tidak sekuat dan memori tidak sebanyak di komputer modern. Pada saat yang sama, bagian utama dari pasar adalah smartphone murah dengan perangkat keras yang bahkan lebih lemah. Pemiliknya sangat dipengaruhi oleh kurangnya sumber daya.
Pengembangan proyek kompetitif yang kompleks tidak mungkin tanpa menggunakan solusi yang mengatasi tugas lebih cepat daripada dalam waktu kuadratik. Pengguna dapat pergi ke pesaing jika mereka tidak menyukai kecepatan kerja atau bagaimana aplikasi Anda mengkonsumsi daya baterai.
Secara historis, Blitz adalah kompetisi untuk pengetahuan tentang algoritma dan kemampuan untuk menerjemahkan ide solusi ke dalam kode. Blitz, yang akan diadakan pada bulan September, tidak akan menjadi pengecualian. Kami mencoba memilih tugas dengan algoritme yang serupa dengan yang digunakan oleh pengembang seluler Yandex dalam proyek nyata untuk Android dan iOS.
Mempercepat Browser Sugest
Mikhail Efimov, pengembang utama :
- Saya melakukan omnibox - String pencarian browser. IsiOtomatis berfungsi di dalamnya - cukup masukkan awal kata, dan kami akan menawarkan seluruh kata. Tugas awal dapat disederhanakan sebagai berikut: setelah menerima string input, cari semua kata dari set yang telah ditetapkan di mana string input muncul sebagai substring. Untuk melakukan ini, kita mengambil semua sufiks kata - semua substring yang dengannya kata itu berakhir. Misalnya, untuk kata "tabel" itu akan menjadi "tabel" dan "tol". Sufiks satu atau dua karakter - di sini kita akan memiliki "ol" dan "l" - jangan diperhitungkan, karena melalui mereka sampah masuk ke sest.
Jadi, alih-alih satu kata, kita dapat dua. Jika terdiri dari lima huruf, mereka akan mendapatkan tiga, dll. Selanjutnya, dari mereka, misalnya, Anda dapat membangun trio struktur data yang terkenal, yang memungkinkan Anda untuk mencarinya. Tetapi struktur ini memiliki kelemahan - ia dapat mengambil banyak ruang memori.
Kami, pada gilirannya, menyimpan daftar sufiks yang diurutkan - array sufiks. Elemen dalam array bukanlah seluruh akhiran - maka struktur akan memakan terlalu banyak memori, jumlah kuadrat - tetapi hanya sepasang pointer. Yang pertama menunjukkan kata atau frasa yang ingin Anda gunakan, yang kedua - simbol dalam kata atau frasa tempat sufiks dimulai. Pendekatan ini menghemat memori. Kami hanya memiliki dua pointer, dua angka delapan byte, bukan kata-kata yang sangat panjang.
Pertanyaan selanjutnya adalah bagaimana cara menyimpan daftar yang sudah diurutkan. Ini dapat disimpan sebagai array sederhana - tetapi kemudian entri baru akan dimasukkan ke dalamnya untuk waktu yang sangat lama. Oleh karena itu, saya memilih untuk menyimpan pohon pencarian biner "augmented" - pohon pencarian biner augmented. Sebagai kunci, setiap node di pohon berisi akhiran tertentu untuk kata tertentu, dan sebagai "suplemen", informasi tentang prioritas disimpan dalam node. Yang perlu Anda lakukan adalah menemukan simpul pohon yang cocok dengan awalan yang dimasukkan. Lebih lanjut, Anda dapat menganalisis ini dan simpul tetangga untuk memahami kata mana yang dapat digunakan untuk menerbitkan.
Di antara mereka, mereka yang memiliki prioritas lebih tinggi dipilih. Prioritas dipengaruhi oleh panjangnya lekukan akhiran dari awal kata. Untuk kata-kata dengan lekukan nol, prioritas lebih tinggi - katakanlah, jika pengguna memasukkan "st", maka kata "tabel" akan jauh lebih tinggi dalam prioritas daripada kata "jembatan". Tetapi pada prinsipnya, Anda dapat memasukkan urutan karakter sehingga Browser sebagai respons akan menyarankan kata di mana urutan ini terjadi di tengah atau akhir. Misalnya, jika tidak ada kata yang dimulai dengan urutan ini.
Tampilan kamera CCTV di ponsel Yandex.Maps
Sergey Kuznetsov, pengembang utama :- Kami memiliki algoritme yang menampilkan kamera pada peta. Dia bekerja di waktu kuadratik, tidak terlalu cepat. Ada ide bahwa itu dapat ditingkatkan, tanpa menggunakan embel-embel.
Jika kita berbicara tentang pernyataan masalah, maka kita memiliki banyak kamera yang perlu ditampilkan. Pada skala tinggi peta, mereka dapat berpotongan satu sama lain, dan itu jelek - diperlukan untuk menampilkan satu kamera daripada banyak berpotongan.
Jika kita meresmikan masalah ini, masalah ini bermuara pada hal-hal berikut: di pesawat ada n kotak yang identik dengan sisi yang sejajar dengan sumbu koordinat, dan Anda harus memilih dari mereka sejumlah besar kotak sehingga mereka tidak berpotongan di dalamnya, dan semua kotak lainnya berpotongan setidaknya satu dari kotak dari set aslinya. Algoritma solusi paling sederhana - ketika kami memilih kotak dan memotongnya dengan yang lain - bekerja untuk n 2 . Tetapi masalahnya dapat diselesaikan dalam n * log (n), menggunakan kelas algoritma tertentu, yang dalam literatur disebut "garis pemindaian". Jika Anda tidak tahu tentang pendekatan ini, maka masalah ini, tentu saja, bisa diselesaikan, tetapi jika Anda tahu, itu bisa diselesaikan dengan lebih mudah. Anda langsung tahu ke arah mana harus berpikir.
Kamera di Maps seluler. Jika Anda memperkecil, hanya satu ikon yang tersisa
Mendapatkan data dari salah satu sumber Browser Sugest
Alexander Yashkin, kepala kelompok portal backend :- Ada beberapa sumber tips "berat" yang ditampilkan saat mengetik di Browser omnibox. Salah satu sumber tersebut adalah sejarah lokal pengguna. Kiat dari riwayat diunggah oleh penyedia riwayat - komponen datang kepada kami dari Chromium. Apa yang istimewa tentang mahakotak? Itu harus sangat cepat, segera, saat Anda mengetik, sehingga sebagian besar sumbernya sinkron. Saat browser dimulai, penyedia membuat indeks cepat tips sejarah selama seminggu terakhir. Di Chromium, indeks riwayat untuk omnibox menggunakan wadah asosiatif std :: set dan std :: map dari pustaka standar C ++. Untuk menyimpan data di dalam wadah seperti itu, kayu merah-hitam biasanya digunakan.
Tugas kami adalah mempercepat pencarian riwayat di mahakotak. Dari histogram dari pengguna, kami melihat bahwa pencarian historis membutuhkan waktu paling banyak, dan pada komputer yang lambat orang sangat menderita. Bagi sebagian orang, harapannya sepersepuluh detik - ketika Anda mengetik karakter dengan cepat di mahakotak, itu terlalu lama, dan itu bisa lebih buruk.
Saya membuat beberapa pendekatan, optimisasi, hulu di Chromium. Pada saat yang sama membuat perubahan pada kode kami. Kemudian tugas diteruskan ke pengembang kami Denis Yaroshevsky. Dia adalah pengembang yang agak antusias - dia tertarik pada algoritma C ++, STL,. Setelah mencari-cari, ia mengusulkan untuk bertindak secara radikal: ganti std :: set dengan flat_set, dan std :: map dengan flat_map. Artinya, ubah saja struktur dasarnya. std :: set dan std :: map menyimpan elemen-elemen mereka di node pohon, dan flat_set dan flat_map, pada kenyataannya, adalah pembungkus vektor yang diurutkan. Wadah datar adalah salah satu wadah paling populer yang bukan bagian dari pustaka standar C ++. Mungkin dalam standar berikutnya mereka masih akan jatuh ke dalamnya.
Pada awalnya ada beberapa ketidakpercayaan: jalan yang diusulkan tampak terlalu sederhana, terbaring di permukaan. Untuk membuktikan efektivitasnya, kami melakukan tes perf: kami mengambil profil salah satu kolega kami, membangun indeks sejarah darinya dan menjalankan pertanyaan populer di atasnya. Kami memilih 10 pertanyaan dan menghitung waktu. Denis menunjukkan kepada saya hasilnya, perbaikannya jelas, dan saya juga percaya pada idenya.
Masalah yang ditemukan tidak spesifik untuk Yandex.Browser. Ini memengaruhi browser berbasis Chromium, jadi pertama-tama, sebagai peserta dalam proyek Chromium, kami memutuskan untuk melakukan upstream. Tetapi di Chromium ada banyak yang berkomitmen, dan beberapa ide yang diajukan liar. Pengembang Chromium memiliki sikap agak waspada terhadap semua orang yang menawarkan untuk mengubah sesuatu dari luar, semuanya lebih radikal. Awalnya mereka tidak ingin mengambil tambalan kami. Mereka menyarankan sebelumnya untuk membuktikan keefektifan dan menulis mini-design-doc sehingga mereka dapat memahami ide, manfaat dan mengkritik proposal.
Selain itu, mereka berkata: sekali Anda perlu, tulis dan tambahkan implementasi terpisah dari wadah datar. Jangan menambahkan perpustakaan baru ke proyek kami - implementasi sudah ada di boost, eastl. Wadah datar harus ditambahkan ke komponen dasar Chromium. Ini adalah analog dari perpustakaan standar, dan orang-orang kromium sangat khawatir sehingga tidak ada yang berlebihan masuk ke dalamnya.
Denis Yaroshevsky melakukan semua ini, menghabiskan waktu menulis dokumen desain, menulis implementasi flat_set dalam templat C ++, menerapkan banyak keajaiban templat, menulis tes yang mencakup fungsionalitas wadah, membuat tes perf sintetis lain - kami tidak dapat mengirim tes perf dengan nyata profil seorang kolega. Denis berdebat dengan pemilik kode pangkalan dan omnibox, secara substansial mengerjakan ulang kode berdasarkan hasil ulasan - dan akhirnya mengatasinya dan mengunggah kode tersebut ke Chromium.
Seluruh hikayat ini berlangsung enam bulan. Kromium kemudian menulis: “Ya, kami benar-benar melihat peningkatan 10-20% dalam semua histogram. Hebat, terima kasih! " Dari mereka itu sudah melalui hilir datang kepada kami di browser, dan kemudian berakhir bahagia. Memang, indeks historis telah dipercepat secara signifikan pada semua konfigurasi, pada semua platform. Dalam indeks ini, keuntungan wadah datar jauh lebih baik daripada kerugiannya.
Setelah upstream, flat_set dan flat_map mulai digunakan lebih sering - sekarang dalam kode Anda dapat menemukan beberapa ratus tempat di mana mereka terlibat. Moralitas - kesabaran dan kerja keras akan menggiling semuanya, dan dengan hati-hati memilih tidak hanya algoritma untuk kode Anda, tetapi juga struktur data yang sesuai.
Lihat sisi kiri grafik. Penurunan tajam pada waktu pemuatan hasil omnibox pada awal 2017 disebabkan oleh transisi ke flat_set dan flat_map
Mempercepat salah satu HashMap di Chromium
Oleg Maksimenko, pengembang utama :"Tujuannya adalah untuk mempercepat penyimpanan halaman HTML biasa di salah satu sub proyek kami." Saya menggunakan cara standar untuk membuat profil kode - saya melihat potongan kode mana yang "panas" dalam proses penyimpanan. Saya menemukan tempat yang tidak terduga. Artinya, ini bukan logika utama, tetapi hanya pencarian pada wadah HashMap, yang seharusnya menempati sebagian kecil dari total waktu. Sebaliknya, ada biaya yang sangat kuat.
Saya memutuskan untuk mengganti implementasi yang ada. Itu adalah HashMap internal, dari Chromium. Saya menggantikannya dan mendapat kemenangan beberapa kali. Kemudian saya melangkah lebih jauh dan memastikan bahwa ini bukan kesalahan orang-orang dari Google, bahwa itu bukan masalah menerapkan seluruh HashMap, tetapi fungsi hash. Ini adalah hal eksternal. Dan ternyata mereka memiliki hash sepele dalam kode yang kami gunakan, alamat dalam memori digunakan sebagai hash. Mungkin, karena beberapa fitur, misalnya, volume kecil, solusi seperti itu cocok untuk mereka. Mungkin HashMap mereka bukan hot spot, tapi itu menjadi milik kami ketika kami menerapkan struktur ini. Dengan hanya mengganti fungsi hash naif dan sepele dengan std :: hash kita mendapatkan peningkatan kecepatan 3-10 kali. Akibatnya, daya tarik ke memori hash menghilang dari daftar hot spot, mulai menempati beberapa persentase kecil, seperti yang diharapkan pada awalnya. Semuanya menjadi baik dan indah.