Vom 10. bis 22. September findet der mobile Entwicklungswettbewerb Yandex.Blitz statt. Die Registrierung ist
offen . Blitz ist ein kurzer Weg zu Yandex: Die fünf besten Teilnehmer müssen einen Abschnitt des Interviews anstelle der vier Standardabschnitte erfolgreich bestehen, um ein Stellenangebot zu erhalten.
Anlässlich des Wettbewerbs haben wir mit Kollegen über interessante Aufgaben gesprochen, die sich sofort auf mobile Plattformen und Algorithmen beziehen. Heute werden wir ihre Geschichten mit Lesern von Habr teilen.
Es wird angenommen, dass die Entwicklung mobiler Anwendungen etwas Besonderes ist, weit entfernt von der Programmierung im allgemeinen Sinne, und Spezialisten, die für Android und iOS schreiben, nie auf die Lösung algorithmisch intensiver Aufgaben stoßen, sondern sich darauf beschränken, vorgefertigte Bibliotheken zu verbinden, Bildschirme zu setzen, einfache Geschäftslogik zu schreiben und Erforschung von Fehlern einer bestimmten Plattform. Aber nicht so einfach.
Das Erstellen von Software für mobile Geräte ist immer mit Einschränkungen verbunden. Selbst in High-End-Geräten sind CPUs und GPUs nicht so leistungsfähig und haben nicht so viel Speicher wie in einem modernen Computer. Gleichzeitig sind Budget-Smartphones mit noch schwächerer Hardware der Hauptteil des Marktes. Ihre Eigentümer sind besonders von einem Mangel an Ressourcen betroffen.
Die Entwicklung eines komplexen Wettbewerbsprojekts ist ohne den Einsatz von Lösungen, die Aufgaben schneller als in einer quadratischen Zeit bewältigen, nicht möglich. Benutzer können sich an einen Mitbewerber wenden, wenn ihnen die Arbeitsgeschwindigkeit oder der Verbrauch von Batteriestrom in Ihrer Anwendung nicht gefällt.
Historisch gesehen ist Blitz ein Wettbewerb um die Kenntnis von Algorithmen und die Fähigkeit, die Idee einer Lösung in Code umzusetzen. Blitz, der im September stattfinden wird, wird keine Ausnahme sein. Wir haben versucht, Aufgaben mit Algorithmen auszuwählen, die denen ähneln, die von Yandex-Mobilentwicklern in realen Projekten für Android und iOS verwendet werden.
Beschleunigen Sie den Sugest Browser
Mikhail Efimov, Hauptentwickler :
- Ich habe Omnibox - Browser-Suchzeichenfolge. Die automatische Ausfüllung funktioniert darin - geben Sie einfach den Wortanfang ein, und wir bieten das ganze Wort an. Die anfängliche Aufgabe kann wie folgt vereinfacht werden: Nachdem Sie eine Eingabezeichenfolge erhalten haben, suchen Sie alle Wörter aus einer vordefinierten Menge, in der die Eingabezeichenfolge als Teilzeichenfolge angezeigt wird. Dazu nehmen wir alle Suffixe des Wortes - alle Teilzeichenfolgen, mit denen es endet. Für das Wort "Tabelle" sind es beispielsweise "Tabelle" und "Tol". Suffixe mit ein oder zwei Zeichen - hier hätten wir "ol" und "l" - werden nicht berücksichtigt, da durch sie Müll in den Sest gelangt.
Anstelle eines Wortes erhalten wir also zwei. Wenn es aus fünf Buchstaben bestehen würde, würden sie drei usw. erhalten. Außerdem können Sie beispielsweise eine bekannte Datenstruktur erstellen, mit der Sie nach ihnen suchen können. Diese Struktur hat jedoch einen Nachteil: Sie kann viel Speicherplatz beanspruchen.
Wir haben wiederum eine sortierte Liste von Suffixen geführt - Suffix-Array. Das Element im Array ist nicht das gesamte Suffix - dann würde die Struktur zu viel Speicher beanspruchen, eine quadratische Menge -, sondern nur ein Paar Zeiger. Der erste gibt das Wort oder die Phrase an, die Sie verwenden möchten, der zweite das Symbol in dem Wort oder der Phrase, mit dem das Suffix beginnt. Dieser Ansatz spart Speicher. Wir haben nur zwei Zeiger, zwei Acht-Byte-Zahlen anstelle von sehr langen Wörtern.
Die nächste Frage ist, wie eine bereits sortierte Liste gespeichert wird. Es kann als einfaches Array gespeichert werden - aber dann werden sehr lange neue Einträge in das Array eingefügt. Daher habe ich mich entschieden, den "erweiterten" binären Suchbaum zu speichern - den erweiterten binären Suchbaum. Als Schlüssel enthält jeder Knoten im Baum ein bestimmtes Suffix für ein bestimmtes Wort, und als „Ergänzung“ werden Informationen zu Prioritäten in den Knoten gespeichert. Sie müssen lediglich den Baumknoten finden, der dem eingegebenen Präfix entspricht. Außerdem können Sie diesen und benachbarte Knoten analysieren, um zu verstehen, welches der Wörter für die Ausgabe verwendet werden kann.
Unter diesen werden diejenigen mit einer höheren Priorität ausgewählt. Die Priorität wird durch die Länge des Einrückens des Suffixes vom Wortanfang an beeinflusst. Bei Wörtern ohne Einzug ist die Priorität höher. Wenn der Benutzer beispielsweise "st" eingegeben hat, hat das Wort "Tabelle" eine viel höhere Priorität als das Wort "Brücke". Im Prinzip können Sie jedoch eine solche Zeichenfolge eingeben, dass der Browser als Antwort das Wort anzeigt, bei dem diese Reihenfolge in der Mitte oder am Ende auftritt. Zum Beispiel, wenn es kein Wort gibt, das mit dieser Sequenz beginnt.
Anzeige von CCTV-Kameras auf mobilen Yandex.Maps
Sergey Kuznetsov, Hauptentwickler :- Wir hatten einen Algorithmus, der Kameras auf einer Karte anzeigte. Er arbeitete in quadratischer Zeit, nicht sehr schnell. Es gab die Idee, dass es verbessert werden kann, ohne auf Schnickschnack zurückzugreifen.
Wenn wir über die Aussage des Problems sprechen, dann hatten wir viele Kameras, die angezeigt werden müssen. In hohen Maßstäben der Karte konnten sie sich überschneiden, und es war hässlich - es musste eine Kamera angezeigt werden, anstatt dass sich viele überschnitten.
Wenn wir dieses Problem formalisieren, läuft es auf Folgendes hinaus: In der Ebene gibt es n identische Quadrate mit Seiten parallel zu den Koordinatenachsen, und Sie müssen aus ihnen eine so große Anzahl von Quadraten auswählen, dass sie sich nicht darin schneiden und alle anderen Quadrate mindestens eines schneiden Quadrate des ursprünglichen Satzes. Der einfachste Lösungsalgorithmus - als wir ein Quadrat ausgewählt und mit allen anderen geschnitten haben - funktionierte für n 2 . Das Problem kann jedoch in n * log (n) unter Verwendung einer bestimmten Klasse von Algorithmen gelöst werden, die in der Literatur als "Abtastzeile" bezeichnet wird. Wenn Sie diesen Ansatz nicht kennen, kann dieses Problem natürlich gelöst werden, aber wenn Sie es wissen, kann es viel einfacher gelöst werden. Sie wissen sofort, in welche Richtung Sie denken müssen.
Kameras auf mobilen Karten. Wenn Sie verkleinern, bleibt nur ein Symbol übrig
Abrufen von Daten aus einer der Quellen des Sugest-Browsers
Alexander Yashkin, Leiter der Portal-Backend-Gruppe :- Es gibt mehrere "schwere" Quellen für Tipps, die beim Eingeben im Omnibox-Browser angezeigt werden. Eine solche Quelle ist der lokale Verlauf des Benutzers. Tipps aus der Geschichte werden von einem historischen Anbieter hochgeladen - eine Komponente kam von Chromium zu uns. Was ist das Besondere an Omnibox? Es sollte sehr schnell sein und sofort während der Eingabe angezeigt werden, damit die Quellen größtenteils synchron sind. Wenn der Browser gestartet wird, erstellt der Anbieter einen schnellen Index der Verlaufstipps der letzten Woche. In Chromium verwendete der Verlaufsindex für Omnibox die assoziativen Container std :: set und std :: map aus der C ++ - Standardbibliothek. Um Daten in solchen Behältern zu speichern, wird normalerweise rot-schwarzes Holz verwendet.
Unsere Aufgabe war es, die Verlaufssuche in der Omnibox zu beschleunigen. Anhand der Histogramme der Benutzer haben wir gesehen, dass die historische Suche die meiste Zeit in Anspruch nimmt und auf langsamen Computern die Menschen wirklich leiden. Für einige war die Erwartung eine Zehntelsekunde - wenn Sie schnell Zeichen in die Omnibox eingeben, ist sie zu lang und kann noch schlimmer sein.
Ich habe verschiedene Ansätze, Optimierungen, vorgelagert in Chromium gemacht. Gleichzeitig wurden Änderungen an unserem Code vorgenommen. Dann ging die Aufgabe an unseren Entwickler Denis Yaroshevsky über. Er ist ein ziemlich begeisterter Entwickler - er interessiert sich für C ++, STL, Algorithmen. Nach dem Stöbern schlug er vor, radikal zu handeln: Ersetzen Sie std :: set durch flat_set und std :: map durch flat_map. Ändern Sie einfach die Grundstruktur. std :: set und std :: map speichern ihre Elemente in den Knoten des Baums, und flat_set und flat_map sind tatsächlich Wrapper über dem sortierten Vektor. Flache Container sind einer der beliebtesten Container, die nicht Teil der C ++ - Standardbibliothek sind. Vielleicht fallen sie im nächsten Standard noch hinein.
Zuerst gab es ein gewisses Misstrauen: Der vorgeschlagene Weg schien zu einfach und lag an der Oberfläche. Um die Wirksamkeit zu beweisen, haben wir einen Perf-Test durchgeführt: Wir haben das Profil eines unserer Kollegen erstellt, daraus einen Verlaufsindex erstellt und beliebte Abfragen durchgeführt. Wir haben 10 Anfragen ausgewählt und die Zeiten gezählt. Denis zeigte mir das Ergebnis, die Verbesserungen waren offensichtlich und ich glaubte auch an seine Idee.
Das gefundene Problem war nicht spezifisch für Yandex.Browser. Es betraf jeden Chromium-basierten Browser. Als Teilnehmer des Chromium-Projekts haben wir uns daher zunächst für einen Upstream entschieden. Aber in Chrom gibt es viele, die sich verpflichten, und einige der vorgeschlagenen Ideen sind wild. Chrom-Entwickler stehen allen, die anbieten, etwas von außen zu ändern, umso vorsichtiger gegenüber, umso radikaler. Zuerst wollten sie unseren Patch nicht nehmen. Sie schlugen zuvor vor, die Wirksamkeit zu beweisen und ein Mini-Design-Dokument zu schreiben, damit sie die Idee verstehen, davon profitieren und den Vorschlag kritisieren können.
Außerdem hieß es: Wenn Sie es brauchen, schreiben Sie separate Implementierungen von flachen Containern und fügen Sie sie hinzu. Fügen Sie unserem Projekt keine neuen Bibliotheken hinzu - Implementierungen sind bereits in boost, eastl vorhanden. Den Grundkomponenten von Chrom sollten flache Behälter zugesetzt werden. Dies ist ein Analogon zur Standardbibliothek, und Chromleute sind sehr besorgt, damit nichts Überflüssiges in sie gelangt.
Denis Yaroshevsky hat das alles getan, Zeit damit verbracht, ein Designdokument zu schreiben, die Implementierung von flat_set in C ++ - Vorlagen zu schreiben, viel Template-Magie anzuwenden, Tests über die Funktionalität von Containern zu schreiben und einen weiteren synthetischen Perf-Test zu erstellen - wir konnten keinen Perf-Test mit real senden Profil eines Kollegen. Denis diskutierte mit den Eigentümern des Basis- und Omnibox-Codes, überarbeitete den Code basierend auf den Ergebnissen der Überprüfung grundlegend - und überwand sie schließlich und lud den Code auf Chromium hoch.
Diese ganze Saga dauerte sechs Monate. Das Chrom schrieb dann: „Ja, wir haben wirklich eine 10–20% ige Verbesserung aller Histogramme gesehen. Großartig, danke! " Von ihnen kam es uns schon durch den Downstream im Browser und dann ein Happy End. In der Tat hat sich der historische Index bei allen Konfigurationen und auf allen Plattformen erheblich beschleunigt. In diesem Index sind die Vorteile von Flachbehältern viel besser als die Nachteile.
Nach dem Upstream wurden flat_set und flat_map viel häufiger verwendet - jetzt finden Sie im Code mehrere hundert Stellen, an denen sie beteiligt sind. Moral - Geduld und Arbeit werden alles zermahlen und sorgfältig nicht nur Algorithmen für Ihren Code auswählen, sondern auch geeignete Datenstrukturen.
Siehe die linke Seite des Diagramms. Ein starker Rückgang der Ladezeit der Omnibox-Ergebnisse zu Beginn des Jahres 2017 ist genau auf den Übergang zu flat_set und flat_map zurückzuführen
Beschleunigen einer der HashMap in Chromium
Oleg Maksimenko, Hauptentwickler :"Ziel war es, die Speicherung regulärer HTML-Seiten in einem unserer Teilprojekte zu beschleunigen." Ich habe die Standardmethode zum Profilieren des Codes verwendet - ich habe mir angesehen, welche Codeteile beim Speichern „heiß“ sind. Ich bin auf einen unerwarteten Ort gestoßen. Das heißt, dies ist nicht die Hauptlogik, sondern nur eine Suche im HashMap-Container, die einen kleinen Prozentsatz der Gesamtzeit einnehmen sollte. Stattdessen gab es wirklich hohe Kosten.
Ich habe beschlossen, die bestehende Implementierung zu ersetzen. Es war eine interne HashMap von Chromium. Ich habe ihn ersetzt und mehrmals gewonnen. Dann ging ich noch ein Stück weiter und stellte sicher, dass dies kein Fehler der Jungs von Google war, dass es nicht darum ging, die gesamte HashMap zu implementieren, sondern eine Hash-Funktion. Das ist eine äußere Sache. Und es stellte sich heraus, dass der von uns verwendete Code einen trivialen Hash enthielt. Die Adresse im Speicher wurde als Hash verwendet. Möglicherweise passte eine solche Lösung aufgrund einiger Merkmale, beispielsweise eines kleinen Volumens, zu ihnen. Vielleicht war ihre HashMap kein Hot Spot, aber sie wurde uns, als wir diese Struktur anwendeten. Durch einfaches Ersetzen der naiven und trivialen Hash-Funktion durch std :: hash wurde die Geschwindigkeit um das 3- bis 10-fache erhöht. Infolgedessen verschwand dieser Appell an das Hash-Gedächtnis von der Liste der Hot Spots und nahm, wie zunächst erwartet, einen kleinen Prozentsatz ein. Alles wurde gut und schön.