Del 10 al 22 de septiembre, se llevará a cabo el concurso de desarrollo móvil Yandex.Blitz. El registro está
abierto . Blitz es un camino corto para llegar a Yandex: los 5 mejores participantes deberán aprobar con éxito una sección de la entrevista en lugar de las cuatro estándar para obtener una oferta de trabajo.
Con motivo del concurso, hablamos con colegas sobre tareas interesantes que se aplican inmediatamente a plataformas y algoritmos móviles. Hoy compartiremos sus historias con los lectores de Habr.
Se cree que el desarrollo de aplicaciones móviles es algo especial, lejos de la programación en el sentido general, y los especialistas que escriben para Android e iOS nunca encuentran la solución de tareas intensivas en algoritmos, limitándose a conectar bibliotecas preparadas, diseño de pantallas, escribir lógica comercial simple y investigando errores de una plataforma específica. Pero no tan simple.
Crear software para dispositivos móviles siempre está lleno de limitaciones. Incluso en dispositivos de gama alta, las CPU y GPU no son tan potentes y no tienen tanta memoria como en una computadora moderna. Al mismo tiempo, la parte principal del mercado son los teléfonos inteligentes económicos con hardware aún más débil. Sus propietarios se ven particularmente afectados por la falta de recursos.
El desarrollo de un proyecto competitivo complejo es imposible sin el uso de soluciones que se encarguen de las tareas más rápido que en un tiempo cuadrático. Los usuarios pueden acudir a un competidor si no les gusta la velocidad del trabajo o cómo su aplicación consume energía de la batería.
Históricamente, Blitz es una competencia por el conocimiento de algoritmos y la capacidad de traducir la idea de una solución en código. Blitz, que se celebrará en septiembre, no será una excepción. Intentamos seleccionar tareas con algoritmos similares a los utilizados por los desarrolladores móviles de Yandex en proyectos reales para Android e iOS.
Acelerando el navegador Sugest
Mikhail Efimov, desarrollador principal :
- Hice omnibox - Cadena de búsqueda del navegador. Autocompletar funciona: solo ingrese el comienzo de la palabra y le ofreceremos la palabra completa. La tarea inicial se puede simplificar de la siguiente manera: después de recibir una cadena de entrada, busque todas las palabras de un conjunto predefinido en el que la cadena de entrada aparece como una subcadena. Para hacer esto, tomamos todos los sufijos de la palabra, todas las subcadenas con las que termina. Por ejemplo, para la palabra "tabla" será "tabla" y "tol". Los sufijos de uno o dos caracteres, aquí tendríamos "ol" y "l", no se tienen en cuenta, porque a través de ellos la basura se mete en el set.
Por lo tanto, en lugar de una palabra, obtenemos dos. Si consistiera en cinco letras, obtendrían tres, etc. Además, de ellas, por ejemplo, puede construir un trie de estructura de datos conocido, que le permite buscarlas. Pero esta estructura tiene un inconveniente: puede ocupar mucho espacio en la memoria.
Nosotros, a su vez, mantuvimos una lista ordenada de sufijos: matriz de sufijos. El elemento en la matriz no es el sufijo completo, entonces la estructura ocuparía demasiada memoria, una cantidad cuadrática, sino solo un par de punteros. El primero de ellos indica la palabra o frase que desea usar, el segundo, el símbolo en la palabra o frase con la que comienza el sufijo. Este enfoque ahorra memoria. Solo tenemos dos punteros, dos números de ocho bytes en lugar de palabras muy largas.
La siguiente pregunta es cómo almacenar una lista ya ordenada. Se puede almacenar como una matriz simple, pero luego se insertarán nuevas entradas durante mucho tiempo. Por lo tanto, elegí almacenar el árbol de búsqueda binaria "aumentada" - árbol de búsqueda binaria aumentada. Como clave, cada nodo en el árbol contiene un determinado sufijo para una palabra determinada, y como un "suplemento", la información sobre las prioridades se almacena en los nodos. Todo lo que necesita hacer es encontrar el nodo del árbol que coincida con el prefijo ingresado. Además, puede analizar este y los nodos vecinos para comprender cuál de las palabras se puede utilizar para emitir.
Entre ellos, se seleccionan aquellos con mayor prioridad. La prioridad se ve afectada por la longitud de la sangría del sufijo desde el comienzo de la palabra. Para las palabras con sangría cero, la prioridad es mayor; por ejemplo, si el usuario ingresó "st", entonces la palabra "tabla" tendrá una prioridad mucho mayor que la palabra "puente". Pero, en principio, puede ingresar una secuencia de caracteres tal que, en respuesta, el navegador avisará a la palabra dónde se produce esta secuencia en el medio o al final. Por ejemplo, si no hay una palabra que comience con esta secuencia.
Visualización de cámaras de CCTV en dispositivos móviles Yandex.
Sergey Kuznetsov, desarrollador principal :- Teníamos un algoritmo que mostraba cámaras en un mapa. Trabajó en tiempo cuadrático, no muy rápido. Hubo una idea de que se puede mejorar, sin recurrir a ningún adorno.
Si hablamos sobre el enunciado del problema, entonces teníamos muchas cámaras que debían mostrarse. A grandes escalas del mapa, podían cruzarse entre sí, y era feo: era necesario mostrar una cámara en lugar de muchas intersecciones.
Si formalizamos este problema, se reduce a lo siguiente: en el plano hay n cuadrados idénticos con lados paralelos a los ejes de coordenadas, y debe elegir entre ellos un número tan grande de cuadrados para que no se crucen dentro de él, y todos los otros cuadrados se cruzan al menos uno de cuadrados del conjunto original. El algoritmo de solución más simple, cuando seleccionamos un cuadrado y lo intersectamos con todos los demás, funcionó para n 2 . Pero el problema puede resolverse en n * log (n), utilizando una cierta clase de algoritmos, que en la literatura se llama la "línea de exploración". Si no conoce este enfoque, entonces este problema, por supuesto, puede resolverse, pero si lo sabe, puede resolverse mucho más fácilmente. Inmediatamente sabes en qué dirección pensar.
Cámaras en mapas móviles. Si aleja, solo queda un icono
Obtener datos de una de las fuentes del navegador Sugest
Alexander Yashkin, jefe del grupo de backend del portal :- Hay varias fuentes "pesadas" de sugerencias que se muestran al escribir en el navegador omnibox. Una de esas fuentes es el historial local del usuario. Un proveedor histórico carga las sugerencias del historial; Chromium nos envió un componente. ¿Qué tiene de especial el omnibox? Debe ser muy rápido, solicitarlo inmediatamente, a medida que escribe, por lo que las fuentes son principalmente sincrónicas. Cuando se inicia el navegador, el proveedor crea un índice rápido de consejos de historial durante la semana pasada. En Chromium, el índice de historial para omnibox utilizó los contenedores asociativos std :: set y std :: map de la biblioteca estándar de C ++. Para almacenar datos dentro de dichos contenedores, generalmente se utiliza madera roja-negra.
Nuestra tarea era acelerar la búsqueda del historial en el omnibox. De los histogramas de los usuarios, vimos que la búsqueda histórica lleva más tiempo, y en computadoras lentas la gente realmente sufre. Para algunos, la expectativa era una décima de segundo: cuando escribes rápidamente caracteres en el omnibox, es demasiado largo y puede ser aún peor.
Hice varios enfoques, optimizaciones, aguas arriba en Chromium. Al mismo tiempo hizo cambios a nuestro código. Luego la tarea pasó a nuestro desarrollador Denis Yaroshevsky. Es un desarrollador bastante entusiasta: le interesan los algoritmos de C ++, STL. Después de hurgar, propuso actuar radicalmente: reemplazar std :: set con flat_set y std :: map con flat_map. Es decir, solo cambia la estructura básica. std :: set y std :: map almacenan sus elementos en los nodos del árbol, y flat_set y flat_map, de hecho, son envoltorios sobre el vector ordenado. Los contenedores planos son uno de los contenedores más populares que no forman parte de la biblioteca estándar de C ++. Quizás en el próximo estándar todavía caerán en él.
Al principio hubo cierta desconfianza: el camino propuesto parecía demasiado simple, yaciendo en la superficie. Para probar la efectividad, hicimos una prueba de rendimiento: tomamos el perfil de uno de nuestros colegas, construimos un índice de historial a partir de él y realizamos consultas populares sobre él. Elegimos 10 consultas y contamos los tiempos. Denis me mostró el resultado, las mejoras fueron obvias, y también creí en su idea.
El problema encontrado no era específico de Yandex.Browser. Afectó a cualquier navegador basado en Chromium, así que primero, como participantes en el proyecto Chromium, decidimos hacer un flujo ascendente. Pero en Chromium hay muchos que se comprometen, y algunas de las ideas propuestas son descabelladas. Los desarrolladores de Chromium tienen una actitud bastante cautelosa hacia todos los que ofrecen cambiar algo desde el exterior, aún más radicalmente. Al principio no querían tomar nuestro parche. Antes de eso, sugirieron probar la efectividad y escribir un mini-diseño-documento para que puedan entender la idea, beneficiarse y criticar la propuesta.
Además, dijeron: una vez que lo necesite, escriba y agregue implementaciones separadas de contenedores planos. No agregue ninguna biblioteca nueva a nuestro proyecto, ya existen implementaciones en boost, eastl. Los contenedores planos debían agregarse a los componentes base de Chromium. Este es un análogo de la biblioteca estándar, y las personas de cromo están muy preocupadas por lo que no entra nada superfluo.
Denis Yaroshevsky hizo todo esto, pasó tiempo escribiendo un documento de diseño, escribió la implementación flat_set en plantillas C ++, aplicó mucha magia de plantilla, escribió pruebas que cubrían la funcionalidad de los contenedores, creó otra prueba de perf sintética: no pudimos enviar la prueba de perf con real Perfil de un colega. Denis discutió con los propietarios del código base y omnibox, modificó sustancialmente el código en función de los resultados de la revisión, y finalmente los superó y subió el código a Chromium.
Toda esta saga duró seis meses. El cromo luego escribió: “Sí, realmente vimos una mejora del 10–20% en todos los histogramas. ¡Genial, gracias! De ellos, ya a través del flujo descendente, nos llegó en el navegador, y luego un final feliz. De hecho, el índice histórico se ha acelerado significativamente en todas las configuraciones, en todas las plataformas. En este índice, las ventajas de los contenedores planos son mucho mejores que las desventajas.
Después del flujo ascendente, flat_set y flat_map comenzaron a usarse con mucha más frecuencia, ahora en el código puede encontrar varios cientos de lugares donde están involucrados. Moralidad: la paciencia y el trabajo lo molerán todo y elegirán cuidadosamente no solo algoritmos para su código, sino también estructuras de datos adecuadas.
Vea el lado izquierdo de la gráfica. Una fuerte disminución en el tiempo de carga de los resultados del omnibox a principios de 2017 se debe precisamente a la transición a flat_set y flat_map
Acelerando uno de los HashMap en Chromium
Oleg Maksimenko, desarrollador principal :"El objetivo era acelerar el almacenamiento de páginas HTML normales en uno de nuestros subproyectos". Utilicé los medios estándar para perfilar el código: miré qué partes del código están "activas" en el proceso de guardar. Encontré un lugar inesperado. Es decir, esta no es la lógica principal, sino solo una búsqueda en el contenedor HashMap, que debería ocupar un pequeño porcentaje del tiempo total. En cambio, hubo costos realmente altos.
Decidí reemplazar la implementación existente. Era un HashMap interno, de Chromium. Lo reemplacé y obtuve una victoria varias veces. Luego fui un poco más allá y me aseguré de que esto no fuera un error de los chicos de Google, que no se tratara de implementar todo el HashMap, sino de una función hash. Esto es algo externo. Y resultó que tenían un hash trivial en el código que usamos, la dirección en la memoria se usó como un hash. Quizás, debido a algunas características, por ejemplo, un volumen pequeño, tal solución les convenía. Quizás su HashMap no era un punto caliente, pero se convirtió en nuestro cuando aplicamos esta estructura. Simplemente reemplazando la función hash ingenua y trivial con std :: hash, obtuvimos un aumento de velocidad de 3 a 10 veces. Como resultado, este atractivo para la memoria hash desapareció de la lista de puntos calientes, comenzó a ocupar un pequeño porcentaje, como se esperaba al principio. Todo se volvió bueno y hermoso.