De 10 a 22 de setembro, será realizado o concurso de desenvolvimento móvel Yandex.Blitz. O registro está
aberto . O Blitz é um caminho curto para o Yandex: os 5 principais participantes terão que passar com êxito em uma seção da entrevista, em vez das quatro padrão para obter uma oferta de emprego.
Na ocasião do concurso, conversamos com colegas sobre tarefas interessantes que se aplicam imediatamente a plataformas e algoritmos móveis. Hoje vamos compartilhar suas histórias com os leitores de Habr.
Acredita-se que o desenvolvimento de aplicativos móveis seja algo especial, longe da programação no sentido geral, e os especialistas que escrevem para Android e iOS nunca encontram tarefas para resolver tarefas intensivas em algoritmos, limitando-se a conectar bibliotecas prontas, telas de digitação, escrever lógica de negócios simples e pesquisando bugs de uma plataforma específica. Mas não é tão simples.
A criação de software para dispositivos móveis está sempre cheia de limitações. Mesmo em dispositivos de ponta, CPUs e GPUs não são tão poderosas e não têm tanta memória quanto em um computador moderno. Ao mesmo tempo, a parte principal do mercado é o orçamento de smartphones com hardware ainda mais fraco. Seus proprietários são particularmente afetados pela falta de recursos.
O desenvolvimento de um projeto competitivo complexo é impossível sem o uso de soluções que lidam com tarefas mais rapidamente do que em um período quadrático. Os usuários podem procurar um concorrente se não gostarem da velocidade do trabalho ou de como seu aplicativo consome energia da bateria.
Historicamente, o Blitz é uma competição pelo conhecimento de algoritmos e pela capacidade de traduzir a idéia de uma solução em código. O Blitz, que será realizado em setembro, não será uma exceção. Tentamos selecionar tarefas com algoritmos semelhantes aos usados pelos desenvolvedores de dispositivos móveis Yandex em projetos reais para Android e iOS.
Acelerando o Navegador Sugest
Mikhail Efimov, desenvolvedor principal :
- Eu fiz omnibox - String de pesquisa do navegador. O preenchimento automático funciona nele - basta digitar o início da palavra e ofereceremos a palavra inteira. A tarefa inicial pode ser simplificada para o seguinte: após receber uma sequência de entrada, encontre todas as palavras de um conjunto predefinido no qual a sequência de entrada aparece como uma substring. Para fazer isso, usamos todos os sufixos da palavra - todas as substrings com as quais ela termina. Por exemplo, para a palavra "tabela" será "tabela" e "tol". Sufixos de um ou dois caracteres - aqui teríamos "ol" e "l" - não são levados em consideração, porque através deles o lixo entra no teste.
Assim, em vez de uma palavra, temos duas. Se consistisse em cinco letras, elas receberiam três etc. Além disso, por exemplo, você pode criar uma estrutura de dados conhecida, que permite procurar por elas. Mas essa estrutura tem uma desvantagem - pode ocupar muito espaço de memória.
Por sua vez, mantivemos uma lista classificada de sufixos - matriz de sufixos. O elemento na matriz não é o sufixo inteiro - então a estrutura ocuparia muita memória, uma quantidade quadrática - mas apenas um par de ponteiros. O primeiro deles indica a palavra ou frase que você deseja usar, o segundo - o símbolo na palavra ou frase com a qual o sufixo começa. Essa abordagem economiza memória. Temos apenas dois ponteiros, dois números de oito bytes em vez de palavras muito longas.
A próxima pergunta é como armazenar uma lista já classificada. Ele pode ser armazenado como uma matriz simples - mas novas entradas serão inseridas nela por um período muito longo. Portanto, eu escolhi armazenar a árvore de pesquisa binária "aumentada" - árvore de pesquisa binária aumentada. Como chave, cada nó da árvore contém um determinado sufixo para uma determinada palavra e, como um "complemento", as informações sobre prioridades são armazenadas nos nós. Tudo o que você precisa fazer é encontrar o nó da árvore que corresponde ao prefixo inserido. Além disso, você pode analisar este e os nós vizinhos para entender qual das palavras pode ser usada para emissão.
Entre eles, aqueles com maior prioridade são selecionados. A prioridade é afetada pelo comprimento da indentação do sufixo desde o início da palavra. Para palavras com recuo zero, a prioridade é maior - por exemplo, se o usuário digitar "st", a palavra "tabela" terá prioridade muito maior que a palavra "ponte". Mas, em princípio, você pode inserir uma sequência de caracteres que o Navegador em resposta aconselhe a palavra onde essa sequência ocorre no meio ou no final. Por exemplo, se não houver uma palavra que comece com esta sequência.
Exibição de câmeras de CFTV no Yandex.Maps móvel
Sergey Kuznetsov, desenvolvedor principal :- Tivemos um algoritmo que exibia câmeras em um mapa. Ele trabalhou no tempo quadrático, não muito rápido. Havia uma idéia de que ele pode ser melhorado, sem recorrer a qualquer frescura.
Se falamos sobre a declaração do problema, tivemos muitas câmeras que precisam ser exibidas. Em altas escalas do mapa, eles podiam se cruzar, e era feio - era necessário exibir uma câmera em vez de muitas se cruzarem.
Se formalizarmos esse problema, ele se resumiu ao seguinte: no plano, existem n quadrados idênticos com lados paralelos aos eixos das coordenadas, e você precisa escolher um número tão grande de quadrados para que não se cruzem dentro dele e todos os outros quadrados se cruzem pelo menos um dos quadrados do conjunto original. O algoritmo de solução mais simples - quando selecionamos um quadrado e o cruzamos com todos os outros - funcionava para n 2 . Mas o problema pode ser resolvido em n * log (n), usando uma certa classe de algoritmos, que na literatura é chamada de "linha de varredura". Se você não conhece essa abordagem, é claro que esse problema pode ser resolvido, mas se você souber, pode ser resolvido com muito mais facilidade. Você sabe imediatamente em que direção pensar.
Câmeras em mapas móveis. Se você diminuir o zoom, resta apenas um ícone
Obtendo dados de uma das fontes do Sugest Browser
Alexander Yashkin, chefe do grupo de back-end do portal :- Existem várias fontes de dicas "pesadas" que são exibidas ao digitar no navegador da omnibox. Uma dessas fontes é o histórico local do usuário. As dicas do histórico são enviadas por um provedor histórico - um componente veio do Chromium. O que há de especial na omnibox? Deve ser muito rápido, pronto imediatamente, enquanto você digita, para que as fontes sejam principalmente síncronas. Quando o navegador é iniciado, o provedor cria um índice rápido de dicas de histórico na semana passada. No Chromium, o índice de histórico da omnibox usava os contêineres associativos std :: set e std :: map da biblioteca padrão C ++. Para armazenar dados dentro desses recipientes, geralmente é usada madeira vermelha e preta.
Nossa tarefa era acelerar a pesquisa de histórico na omnibox. A partir dos histogramas dos usuários, vimos que a pesquisa histórica leva mais tempo e, em computadores lentos, as pessoas realmente sofrem. Para alguns, a expectativa era de um décimo de segundo - quando você digita rapidamente caracteres na omnibox, é muito longo e pode ser ainda pior.
Fiz várias abordagens, otimizações, upstream no Chromium. Ao mesmo tempo, fizemos alterações no nosso código. Em seguida, a tarefa passou para o nosso desenvolvedor Denis Yaroshevsky. Ele é um desenvolvedor bastante entusiasmado - ele está interessado em algoritmos C ++, STL. Depois de vasculhar, ele propôs agir radicalmente: substitua std :: set por flat_set e std :: map por flat_map. Ou seja, basta alterar a estrutura básica. std :: set e std :: map armazenam seus elementos nos nós da árvore, e flat_set e flat_map, de fato, são wrappers sobre o vetor classificado. Contêineres planos são um dos contêineres mais populares que não fazem parte da biblioteca padrão C ++. Talvez no próximo padrão eles ainda caiam nele.
A princípio, houve certa desconfiança: o caminho proposto parecia simples demais, deitado na superfície. Para provar a eficácia, fizemos um teste de desempenho: pegamos o perfil de um de nossos colegas, criamos um índice de histórico a partir dele e fizemos consultas populares sobre ele. Escolhemos 10 consultas e contamos os tempos. Denis me mostrou o resultado, as melhorias foram óbvias e eu também acreditei na ideia dele.
O problema encontrado não era específico para o Yandex.Browser. Ele afetou qualquer navegador baseado em Chromium; portanto, primeiro, como participantes do projeto Chromium, decidimos fazer um upstream. Mas no Chromium há muitos que se comprometem, e algumas das idéias propostas são selvagens. Os desenvolvedores de cromo têm uma atitude bastante cautelosa em relação a todos que se oferecem para mudar algo de fora, de maneira mais radical. No começo, eles não queriam pegar nosso patch. Eles sugeriram antes disso para provar a eficácia e escrever um mini-design-doc para que eles possam entender a idéia, beneficiar e criticar a proposta.
Além disso, eles disseram: assim que precisar, escreva e adicione implementações separadas de contêineres planos. Não adicione novas bibliotecas ao nosso projeto - as implementações já existem no boost, eastl. Recipientes planos deveriam ser adicionados aos componentes básicos do Chromium. Este é um análogo da biblioteca padrão, e as pessoas com cromo estão muito preocupadas para que nada supérfluo entre nela.
Denis Yaroshevsky fez tudo isso, passou um tempo escrevendo um documento de design, escreveu a implementação flat_set em modelos C ++, aplicou muita mágica de modelo, escreveu testes cobrindo a funcionalidade dos contêineres, criou outro teste sintético - não era possível enviar o teste perf com real perfil de um colega. Denis discutiu com os proprietários do código base e da omnibox, reformulou substancialmente o código com base nos resultados da revisão - e finalmente os superou e enviou o código para o Chromium.
Essa saga inteira durou seis meses. O cromo escreveu: “Sim, realmente vimos uma melhoria de 10 a 20% em todos os histogramas. Ótimo, obrigado! ” Deles, já através do jusante chegou até nós no navegador e, em seguida, um final feliz. De fato, o índice histórico acelerou significativamente em todas as configurações, em todas as plataformas. Nesse índice, as vantagens dos contêineres planos são muito melhores que as desvantagens.
Após o upstream, flat_set e flat_map começaram a ser usados com muito mais frequência - agora no código você pode encontrar centenas de locais onde eles estão envolvidos. Moralidade - paciência e mão-de-obra trituram tudo e escolhem com cuidado não apenas algoritmos para o seu código, mas também estruturas de dados adequadas.
Veja o lado esquerdo do gráfico. Uma queda acentuada no tempo de carregamento dos resultados da omnibox no início de 2017 se deve precisamente à transição para flat_set e flat_map
Acelerando um dos HashMap no Chromium
Oleg Maksimenko, desenvolvedor principal :"O objetivo era acelerar o armazenamento de páginas HTML regulares em um de nossos subprojetos". Eu usei os meios padrão de criação de perfil do código - observei quais partes do código estão “quentes” no processo de salvar. Me deparei com um lugar inesperado. Ou seja, essa não é a lógica principal, mas apenas uma pesquisa no contêiner HashMap, que deve ocupar uma pequena porcentagem do tempo total. Em vez disso, havia custos realmente fortes.
Eu decidi substituir a implementação existente. Era um HashMap interno, da Chromium. Eu o substituí e ganhei várias vezes. Depois fui um pouco mais longe e me certifiquei de que isso não fosse um erro dos caras do Google, que não se tratasse de implementar todo o HashMap, mas uma função de hash. Isso é uma coisa externa. E aconteceu que eles tinham um hash trivial no código que usamos, o endereço na memória foi usado como um hash. Talvez, devido a alguns recursos, por exemplo, um pequeno volume, essa solução lhes convenha. Talvez o HashMap deles não fosse um ponto quente, mas se tornou nosso quando aplicamos essa estrutura. Simplesmente substituindo a função hash ingênua e trivial por std :: hash, obtivemos um aumento de velocidade de 3 a 10 vezes. Como resultado, esse apelo à memória hash desapareceu da lista de pontos de acesso, passou a ocupar uma pequena porcentagem, como era esperado inicialmente. Tudo ficou bom e bonito.