Devaneios sobre conhecimento e otimização · ricardovm

Vez por outra gosto de resolver exercícios de programação no HackerRank. Se você não conhece, funciona assim: ele te dá um exercício que você deve resolver escrevendo um programa, normalmente é apenas uma função. Mas não são exercícios como CRUD ou um microsserviço. São exercícios que vão desde um simples: conte quantas vezes você encontra determinada sequência em um array até coisas (bem) mais complexas. Ele vai aumentando a dificuldade conforme você vai resolvendo.

Esses dias me deparei com um exercício que parei para pensar uns dois minutos e trouxe esta solução em Scala (normalmente resolvo cada exercício na linguagem que me parece mais fácil para ele ou na que estou estudando no momento, e nesse caso, pareceu perfeito para Scala):

def climbingLeaderboard(ranked: Array[Int], player: Array[Int]): Array[Int] = {
  val consRank = ranked.toSet
  player.map(s => consRank.count(r => r > s) + 1)
}

Duas linhas de código… como disse, Scala pareceu perfeito para resolver. Muitas vezes pego alguns minutos e resolve um ou dois exercícios não necessariamente da melhor maneira… a ideia é simplesmente exercitar. Se você já usou o HackerRank sabe que você pode rodar um teste do seu código e, se ele passar nesse teste, você faz a submissão. Rodei o teste e passou. E, como de costume, submeti o código, onde ele roda mais testes. E dessa vez não passou.

O código em si traz resultados corretos mesmo nesses casos em que não passou. Então qual é o problema? Há uma regra do HackerRank que códigos em Scala devem executar em até 7 segundos (varia da linguagem… Java e Kotlin são 4, C e C++ são apenas 2, JavaScript são 10). E por causa desses 7 segundos, meu código de duas linhas não passou. Ou seja, o HackerRank não deixou eu simplesmente oferecer a primeira solução que me apareceu e passar para o próximo exercício.

De cara já vi que aquele .map(… .count(…) ali seria pesado para uma massa de dados maior. Tentei mexer aqui e ali, mas não foi. Aí fui descobrir que esses testes que não passaram eram realmente grandes. Em um deles, os tamanho de consRank era de 199.783 e player era 100.000, o que significava que esse pobre código de duas linhas fazia 19.978.300.000 análises. No meu computador, que tem um processador bem rápido, ele demorou 4 minutos. Ainda no meu computador, com vários núcleos, executando em paralelo, levou 49 segundos. Bem melhor, mas ainda muito longe dos 7 segundos exigidos pelo HackerRank (que provavelmente roda com apenas um núcleo não tão bom).

Então a ideia era mudar a forma de gerar o mesmo resultado sem esses quase 20 bilhões de análises. Resolvi partir pro Java já que teria que usar código imperativo/mutável. Até pensei em C, mas ia ter que relembrar muita coisa, não queria gastar mais tempo com isso (a ideia inicial era só fazer um exercício rápido entre uma atividade e outra). Scala com var ainda seria uma boa opção, mas já que ia partir para código imperativo mutável, achei melhor ir direto pro Java. E o código que saiu foi este:

public static List<Integer> climbingLeaderboard(List<Integer> ranked, List<Integer> player) {
    var result = new LinkedList<Integer>();
 
    var ir = 0;
    var ip = player.size() - 1;
    var pos = 1;
    var lastRanked = ranked.get(0);
 
    while (ip >= 0) {
        if (ir == ranked.size()) {
            result.addFirst(pos + 1);
            ip--;
            continue;
        }
 
        var currentRanked = ranked.get(ir);
        var currentPlayer = player.get(ip);
 
        if (!Objects.equals(lastRanked, currentRanked)) {
            lastRanked = currentRanked;
            pos++;
        }
 
        if (currentPlayer >= currentRanked) {
            result.addFirst(pos);
            ip--;
        } else {
            ir++;
        }
    }
 
    return result;
}

Saí de duas linhas em Scala para 21 (sem contar linhas em branco e fechamento de chaves) em Java. Saí de 4 minutos em Scala (2 linhas mal-pensadas) para 18 milissegundos (sim, milissegundos) em Java (21 linhas, sem processamento paralelo)! Em vez de 20 bilhões de análises, faço somente 300.000 e de forma mais simples (a análise, não o código). O estranho é que eu jamais diria que os dois códigos dão o mesmo resultado apenas olhando para eles.

Aí vem o questionamento: então o segundo código é melhor? Não necessariamente.

Tudo depende do que você precisa. O primeiro código atendia 100% dos requisitos funcionais mas não atendia o requisito não-funcional de tempo com uma massa de dados grande. Mas ele funciona é bem mais fácil de manter.

Já o segundo é um tiro de canhão.

Para massa de dados pequenas, a diferença de tempo de execução é humanamente imperceptível. Mas conforme o volume cresce, essa diferença aparece. E essa é a beleza do que fazemos. Sempre temos opções.

Se você vai escrever um microsserviço com um alto volume de dados, pode ser interessante uma otimização dessas. Vai reduzir drasticamente os custos da aplicação. Em outros casos isso pode não ser relevante.

Infelizmente alguns pensam assim: não preciso aprender algoritmo e estrutura de dados. A linguagem hoje cuida de quase tudo e o hardware é potente. De fato, e as duas linhas em Scala mostram que a linguagem pode cuidar mesmo. Mas quando chegar aquele problema que nem acrescentar mais hardware resolve, só o seu conhecimento vai fazer a diferença. E esse tipo de necessidade é mais comum do que muitos imaginam. Alguns encontram uma solução, outros vão dizer que é impossível resolver.