Du 10 au 22 septembre aura lieu le concours de développement mobile Yandex.Blitz. L'inscription est
ouverte . Blitz est un court chemin vers Yandex: les 5 meilleurs participants devront réussir une section de l'entretien au lieu des quatre standards pour obtenir une offre d'emploi.
À l'occasion du concours, nous avons discuté avec des collègues de tâches intéressantes qui s'appliquent immédiatement aux plateformes mobiles et aux algorithmes. Aujourd'hui, nous partagerons leurs histoires avec les lecteurs de Habr.
On pense que le développement d'applications mobiles est quelque chose de spécial, loin de la programmation au sens général, et les spécialistes qui écrivent pour Android et iOS ne rencontrent jamais de résolution de tâches gourmandes en algorithmes, se limitant à connecter des bibliothèques prêtes à l'emploi, à composer des écrans, à écrire une logique métier simple et la recherche de bogues d'une plate-forme spécifique. Mais pas si simple.
La création de logiciels pour les appareils mobiles est toujours lourde de limites. Même dans les appareils haut de gamme, les processeurs et les GPU ne sont pas aussi puissants et pas autant de mémoire que sur un ordinateur moderne. Dans le même temps, la majeure partie du marché est constituée de smartphones économiques dotés d'un matériel encore plus faible. Leurs propriétaires sont particulièrement touchés par le manque de ressources.
Le développement d'un projet concurrentiel complexe est impossible sans l'utilisation de solutions qui gèrent les tâches plus rapidement qu'en temps quadratique. Les utilisateurs peuvent s'adresser à un concurrent s'ils n'aiment pas la vitesse de travail ou la façon dont votre application consomme l'énergie de la batterie.
Historiquement, Blitz est un concours pour la connaissance des algorithmes et la capacité de traduire l'idée d'une solution en code. Le Blitz, qui se tiendra en septembre, ne fera pas exception. Nous avons essayé de sélectionner des tâches avec des algorithmes similaires à ceux utilisés par les développeurs mobiles Yandex dans des projets réels pour Android et iOS.
Accélérer le navigateur Sugest
Mikhail Efimov, développeur principal :
- J'ai fait omnibox - Chaîne de recherche du navigateur. Le remplissage automatique fonctionne - entrez simplement le début du mot, et nous vous proposerons le mot entier. La tâche initiale peut être simplifiée comme suit: après avoir reçu une chaîne d'entrée, recherchez tous les mots d'un ensemble prédéfini dans lequel la chaîne d'entrée apparaît comme une sous-chaîne. Pour ce faire, nous prenons tous les suffixes du mot - toutes les sous-chaînes avec lesquelles il se termine. Par exemple, pour le mot «table», ce sera «table» et «tol». Les suffixes d'un ou deux caractères - ici nous aurions "ol" et "l" - ne sont pas pris en compte, car à travers eux les ordures entrent dans le sest.
Ainsi, au lieu d'un mot, nous en obtenons deux. S'il se composait de cinq lettres, ils en obtiendraient trois, etc. De plus, par exemple, vous pouvez créer un trie de structure de données bien connu, qui vous permet de les rechercher. Mais cette structure a un inconvénient - elle peut occuper beaucoup d'espace mémoire.
À notre tour, nous avons conservé une liste triée de suffixes - tableau de suffixes. L'élément dans le tableau n'est pas le suffixe entier - alors la structure prendrait trop de mémoire, une quantité quadratique - mais juste une paire de pointeurs. Le premier d'entre eux indique le mot ou la phrase que vous souhaitez utiliser, le second - le symbole dans le mot ou la phrase par lequel le suffixe commence. Cette approche économise de la mémoire. Nous n'avons que deux pointeurs, deux nombres de huit octets au lieu de très longs mots.
La question suivante est de savoir comment stocker une liste déjà triée. Il peut être stocké comme un simple tableau - mais de nouvelles entrées y seront insérées pendant très longtemps. Par conséquent, j'ai choisi de stocker l'arborescence de recherche binaire "augmentée" - l'arborescence de recherche binaire augmentée. En tant que clé, chaque nœud de l'arborescence contient un certain suffixe pour un certain mot, et en tant que «supplément», des informations sur les priorités sont stockées dans les nœuds. Il vous suffit de trouver le nœud d'arbre correspondant au préfixe saisi. De plus, vous pouvez analyser ce nœud et les nœuds voisins pour comprendre lequel des mots peut être utilisé pour l'émission.
Parmi eux, ceux qui ont une priorité plus élevée sont sélectionnés. La priorité est affectée par la longueur de l'indentation du suffixe depuis le début du mot. Pour les mots avec une indentation nulle, la priorité est plus élevée - par exemple, si l'utilisateur a entré "st", alors le mot "table" sera beaucoup plus prioritaire que le mot "bridge". Mais en principe, vous pouvez entrer une telle séquence de caractères que le navigateur en réponse indiquera le mot où cette séquence se produit au milieu ou à la fin. Par exemple, s'il n'y a pas de mot commençant par cette séquence.
Affichage des caméras de vidéosurveillance sur mobile Yandex.
Sergey Kuznetsov, développeur principal :- Nous avions un algorithme qui affichait les caméras sur une carte. Il a travaillé en temps quadratique, pas très vite. Il y avait une idée qu'il peut être amélioré, sans recourir à des fioritures.
Si nous parlons de l'énoncé du problème, nous avions beaucoup de caméras à afficher. À des échelles élevées de la carte, ils pouvaient se croiser, et c'était moche - il fallait afficher une caméra au lieu de plusieurs se croisant.
Si nous formalisons ce problème, il se résumait à ce qui suit: sur le plan, il y a n carrés identiques avec des côtés parallèles aux axes de coordonnées, et vous devez choisir parmi eux un si grand nombre de carrés afin qu'ils ne se croisent pas à l'intérieur, et tous les autres carrés se croisent au moins l'un des carrés de l'ensemble d'origine. L'algorithme de solution le plus simple - lorsque nous avons sélectionné un carré et l'avons intersecté avec tous les autres - a fonctionné pour n 2 . Mais le problème peut être résolu dans n * log (n), en utilisant une certaine classe d'algorithmes, que dans la littérature on appelle la «ligne de balayage». Si vous ne connaissez pas cette approche, ce problème peut bien sûr être résolu, mais si vous le savez, il peut être résolu beaucoup plus facilement. Vous savez immédiatement dans quelle direction penser.
Caméras sur cartes mobiles. Si vous effectuez un zoom arrière, une seule icône reste
Obtention de données à partir d'une des sources du navigateur Sugest
Alexander Yashkin, chef du groupe back-end du portail :- Il existe plusieurs sources "lourdes" de conseils qui s'affichent lors de la saisie dans le navigateur omnibox. L'une de ces sources est l'historique local de l'utilisateur. Les conseils de l'historique sont téléchargés par un fournisseur historique - un composant nous est venu de Chromium. Quelle est la particularité d'omnibox? Cela devrait être très rapide, demander immédiatement au fur et à mesure que vous tapez, donc les sources sont principalement synchrones. Lorsque le navigateur démarre, le fournisseur crée un index rapide des conseils d'historique au cours de la semaine dernière. Dans Chromium, l'index d'historique pour omnibox a utilisé les conteneurs associatifs std :: set et std :: map de la bibliothèque standard C ++. Pour stocker des données à l'intérieur de ces conteneurs, du bois rouge-noir est généralement utilisé.
Notre tâche était d'accélérer la recherche d'historique dans l'omnibox. À partir des histogrammes des utilisateurs, nous avons vu que la recherche historique prend le plus de temps, et sur les ordinateurs lents, les gens souffrent vraiment. Pour certains, l'attente était d'un dixième de seconde - lorsque vous tapez rapidement des caractères dans l'omnibox, c'est trop long et cela peut être encore pire.
J'ai fait plusieurs démarches, optimisations, en amont dans Chrome. En même temps, nous avons modifié notre code. La tâche est ensuite passée à notre développeur Denis Yaroshevsky. C'est un développeur plutôt enthousiaste - il s'intéresse aux algorithmes C ++, STL et. Après avoir fouillé, il a proposé d'agir radicalement: remplacer std :: set par flat_set, et std :: map par flat_map. Autrement dit, changez simplement la structure de base. std :: set et std :: map stockent leurs éléments dans les nœuds de l'arbre, et flat_set et flat_map, en fait, sont des wrappers sur le vecteur trié. Les conteneurs plats sont l'un des conteneurs les plus populaires qui ne font pas partie de la bibliothèque standard C ++. Peut-être que dans la prochaine norme, ils y tomberont encore.
Au début, il y avait une certaine méfiance: le chemin proposé semblait trop simple, allongé à la surface. Pour prouver l'efficacité, nous avons fait un test de perf: nous avons pris le profil d'un de nos collègues, construit un index d'historique à partir de celui-ci et lancé des requêtes populaires dessus. Nous avons choisi 10 requêtes et compté le temps. Denis m'a montré le résultat, les améliorations étaient évidentes et je croyais aussi en son idée.
Le problème trouvé n'était pas spécifique à Yandex.Browser. Cela affectait n'importe quel navigateur basé sur Chromium, donc d'abord, en tant que participants au projet Chromium, nous avons décidé de faire un amont. Mais chez Chromium, nombreux sont ceux qui s'engagent et certaines des idées proposées sont folles. Les développeurs de chrome ont une attitude plutôt méfiante vis-à-vis de tous ceux qui proposent de changer quelque chose de l'extérieur, de manière encore plus radicale. Au début, ils ne voulaient pas prendre notre patch. Ils ont suggéré avant cela de prouver l'efficacité et d'écrire un mini-design-doc afin de pouvoir comprendre l'idée, en tirer profit et critiquer la proposition.
En outre, ils ont dit: une fois que vous en avez besoin, écrivez et ajoutez des implémentations distinctes de conteneurs plats. N'ajoutez aucune nouvelle bibliothèque à notre projet - des implémentations existent déjà dans boost, eastl. Des conteneurs plats devaient être ajoutés aux composants de base du chrome. Il s'agit d'un analogue de la bibliothèque standard, et les gens du chrome sont très inquiets afin que rien de plus n'y pénètre.
Denis Yaroshevsky a fait tout cela, a passé du temps à écrire un document de conception, a écrit l'implémentation de flat_set dans des modèles C ++, a appliqué beaucoup de magie de modèle, a écrit des tests couvrant la fonctionnalité des conteneurs, a créé un autre test de performance synthétique - nous ne pouvions pas envoyer de test de performance avec de vrais profil d'un collègue. Denis s'est disputé avec les propriétaires du code de base et de l'omniboxe, a retravaillé substantiellement le code en fonction des résultats de l'examen - et les a finalement surmontés et a téléchargé le code sur Chromium.
Toute cette saga a duré six mois. Le chrome a ensuite écrit: «Oui, nous avons vraiment constaté une amélioration de 10 à 20% de tous les histogrammes. Super, merci! ” D'eux, cela nous est déjà parvenu en aval dans le navigateur, puis une fin heureuse. En effet, l'indice historique s'est considérablement accéléré sur toutes les configurations, sur toutes les plateformes. Dans cet indice, les avantages des conteneurs plats sont bien meilleurs que les inconvénients.
Après l'amont, flat_set et flat_map ont commencé à être utilisés beaucoup plus souvent - maintenant, dans le code, vous pouvez trouver plusieurs centaines d'endroits où ils sont impliqués. Moralité - la patience et le travail vont tout broyer et choisir soigneusement non seulement des algorithmes pour votre code, mais aussi des structures de données appropriées.
Voir le côté gauche du graphique. Une nette diminution du temps de chargement des résultats de l'omnibox début 2017 est précisément due au passage à flat_set et flat_map
Accélérer l'un des HashMap dans Chromium
Oleg Maksimenko, développeur principal :"L'objectif était d'accélérer le stockage des pages HTML régulières dans l'un de nos sous-projets." J'ai utilisé les moyens standard de profilage du code - j'ai regardé quels morceaux de code sont «chauds» dans le processus de sauvegarde. Je suis tombé sur un endroit inattendu. Autrement dit, ce n'est pas la logique principale, mais juste une recherche sur le conteneur HashMap, qui devrait occuper un petit pourcentage du temps total. Au lieu de cela, il y avait des coûts vraiment élevés.
J'ai décidé de remplacer l'implémentation existante. C'était un HashMap interne, de Chromium. Je l'ai remplacé et j'ai gagné plusieurs fois. Ensuite, je suis allé un peu plus loin et je me suis assuré que ce n'était pas une erreur des gars de Google, qu'il ne s'agissait pas d'implémenter l'intégralité de HashMap, mais une fonction de hachage. C'est une chose externe. Et il s'est avéré qu'ils avaient un hachage trivial dans le code que nous avons utilisé, l'adresse en mémoire a été utilisée comme hachage. Peut-être, en raison de certaines fonctionnalités, par exemple, un petit volume, une telle solution leur convenait. Peut-être que leur HashMap n'était pas un point chaud, mais il est devenu le nôtre lorsque nous avons appliqué cette structure. En remplaçant simplement la fonction de hachage naïve et triviale par std :: hash, nous avons obtenu une augmentation de la vitesse de 3 à 10 fois. En conséquence, cet appel à la mémoire de hachage a disparu de la liste des points chauds, il a commencé à occuper un petit pourcentage, comme prévu au départ. Tout est devenu bon et beau.