Problema real - Extraindo padrões de textos

Olá meus amigos nerds! Hoje vamos ver que o conhecimento que adquirimos ao brincar em maratonas de programação pode nos ser útil no mundo real. Vou compartilhar com vocês um problema desafiador que tive que resolver essa semana no trabalho.

Essa semana estava trabalhando em um modelo para prever se um candidato seria uma boa indicação para uma dada vaga. Feliz ou infelizmente,  o dataset que eu tinha a minha disposição é bem grande, mas a maior parte da informação contida nele está em forma de texto.

Parte da arte de se criar bons modelos de machine learning está em escolher  e usar as informações certas ao construir o modelo. Features textuais costumam conter bastante informação, entretanto extrair essa informação costuma ser problemático, já que as máquinas gostam de lidar com números.

Em particular, no modelo que eu estava criando, eu gostaria de usar as skills (descrições curtas de habilidades do candidato) presentes nos currículos. E, para minha felicidade, eu tinha a minha disposição uma tabela contendo tal informação.

Infelizmente eu não tinha essa mesma informação para as vagas, então decidi extraí-la da descrição das mesmas. Aí começa o problema.

Dada a descrição textual de uma vaga e uma tabela contendo skills (ex: mineração de dados, vendas, etc) eu gostaria de saber quais são as skills exigidas pela vaga.

O problema

Ué mas não é só dar um .find() das skills no texto e pronto? Onde está o problema desafiador? Aqui no blog já resolvemos alguns problemas de casamento de padrões mais difíceis que esse!

Bem meus amigos, o problema está na escala! Minha tabela de skills continha algo em torno de 1 milhão de registros. Além disso, eu também tinha alguns milhões de vagas o que torna a solução de força bruta inaplicável.

Problemas envolvendo escala costumam ser interessantes e esse não é diferente. Vamos ver como, mesmo algo que é simples quando lidamos com pequenos volume de dados, pode se tornar desafiador quando o tamanho dos dados realmente importa.

Para você ter uma ideia, a biblioteca de regex do python levou um ou dois minutos para compilar toda a tabela em padrões da forma p1|p2|...|pn. Além disso, o automato gerado por ela levava em torno de 1s para extrair os padrões de apenas uma vaga. 1s é o  mesmo que infinito, se considerarmos que o SLA (tempo de resposta acordado) para a maioria das APIs que eu trabalho gira em torno de 200ms. Só para vocês terem uma ideia, usando-se uma máquina moderna levaríamos cerca de 10 dias só para extrair as skills de 1M vagas.

Ou seja, nosso problema é grande o suficiente para que a biblioteca padrão (consideravelmente otimizada) de uma linguagem moderna não seja suficiente.

Solução

Se todas as nossas skills fossem compostas apenas de uma palavra a solução de complexidade ótima (O(# palavras na descrição das vagas)) seria indexar nossas skills em uma tabela hash. Assim, para cada palavra na descrição da vaga, poderíamos verificar se ela esta presente no hash ou não.

O nosso problema é que as skills não são formadas apenas por uma palavra. Para contorná-lo basta criar uma árvore com as palavras das skills, onde cada nó da árvore representa uma palavra e existe uma aresta ligando dois nós se uma skill possui as duas palavras em sequência. Em outras palavras, a ideia para resolver esse problema é uma árvore de prefixos. Cada nó da árvore pode ter vários filhos, que podem ser mantidos em um hash para otimizar a busca.

Para buscar pelas skills então basta tokenizar o texto da vaga e para cada token ir andando com ele na árvore de prefixos de skills, verificando se aquele token gera ou não um match.

Implementação

 

Acho que essa é a primeira vez que uso uma de minhas linguagens preferidas para resolver um problema por aqui. O código Python abaixo implementa a ideia da árvore de prefixos.

11646. Olimpíadas

Olá meus amigos nerds! Vendo os problemas que nós já resolvemos aqui no blog, nesses seis meses, descobri que não tínhamos resolvido sequer um único problema de ordenação. E como ordenação é um dos temas mais importantes e úteis de computação resolvi fazer esse post para amenizar nossa falha.

Hoje vamos falar de olimpíadas, já que o problema 11646. Olimpíadas trata, justamente, disso. Nossa tarefa é, dada a informação dos países que receberam medalhas, gerar a classificação dos países na competição. Nesta tarefa, os países serão identificados por números inteiros. O melhor colocado deve ser o país que conseguiu o maior número de medalhas de ouro. Se houver empate entre países no número de medalhas de ouro, o melhor colocado entre esses é o país que conseguiu o maior número de medalhas de prata. Se houver empate também no número de medalhas de prata, o melhor colocado entre esses é o país que recebeu o maior número de medalhas de bronze. Se ainda assim houver empate entre dois países, o melhor classificado é o que tem o menor número de identificação.

Solução

Esse é um típico problema de ordenação, basta ordenar os países de acordo com a regra dada e pronto. O único cuidado que devemos ter é usar um algoritmo de ordenação rápido, isto é, um algoritmo com complexidade O(n*log n) para não recebermos um TLE.

Esse problema não teria graça nenhuma, caso não falássemos um pouco sobre os algoritmos de ordenação. Sendo assim decidi explicar um pouco sobre o Quicksort (principal e mais rápido algoritmo de ordenação para a maioria dos problemas de ordenação).

O Quicksort é um algoritmo de divisão e conquista. Sua estratégia consiste em rearranjar os elementos de modo que os elementos "menores" que um dado elemento, chamado pivô, precedam esse elemento, enquanto os elementos "maiores" que o pivô o sucedam. Em seguida o Quicksort ordena recursivamente as duas sublistas definidas pelo pivô e as extremidades do array.

De forma mais algorítmica:

1. Escolha um elemento da lista, denominado pivô;
2. Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Essa operação é denominada partição;
3. Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;

O Quicksort é um algoritmo tão famoso que nós deveríamos, não só entende-lo, como também, ser capazes de implementá-lo. Se você nunca tentou implementar o Quicksort, eu o convidaria a tentar.

Uma boa referência, não só a respeito de ordenação, mas também de algoritmos e estruturas de dados de um modo geral é o livro do Cormem. Se você quer se aprofundar um pouco no assunto, eu recomendaria a leitura do capítulo 2 desse livro.

Implementação

Observe como o problema fica simples usando o sort da lib algorithm :)

Dica do Peão Programador - Hibernate e Cache

Olá meus amigos nerds, hoje estou aqui para falar de problemas do mundo real, que vocês podem ter que lidar quando estiverem desenvolvendo algum sistema de grande porte.

Outro dia eu precisava fazer uma atualização em algumas tabelas de um banco de dados, para acomodar algumas melhorias em um dos sistemas que eu ajudo a desenvolver.

Eu tinha a opção de gerar o sql de atualização na unha ou usar o Hibernate para isso. Como a atualização não era simples, optei por fazê-la usando o Hibernate (sou preguiçoso como todo bom cientista da computação)

(Se você não conhece o Hibernate, ele é um framework muito útil para desenvolvimento de aplicações (java) que precisam se comunicar com bancos de dados relacionais. A grosso modo, ele faz o mapeamento dos objetos da sua aplicação para as tabelas do seu banco de dados, gerando para você o sql das consultas de modo transparente.)

Você deve estar se perguntando qual o problema. Isso qualquer peão programador consegue fazer. O problema estava no número de objetos (linhas das tabelas) que eu tinha que atualizar (alguns milhares). É claro que, como um bom nerd, eu estava atento a esse fato. E para evitar problemas de memória, eu havia implementado meu código de modo a fazer a atualização de forma paginada, ou seja, eu carregava apenas uma parte dos objetos a serem atualizados de cada vez na memória. 

Testei meu código usando um dump do banco de dados e para minha surpresa ele começou a demorar muito a executar. Meu instinto nerd me dizia, deu merda! Então eu voltei ao código e o instrumentei (adicionei informações de tempo ao log da execução) de modo a obter informações de onde estava o problema. Eis que encontrei o seguinte comportamento:

Tempo de execução do método de atualização sobre a 1ª página de dados 1s

Tempo de execução do método de atualização sobre a 2ª página de dados 2s

Tempo de execução do método de atualização sobre a 3ª página de dados 4s

Tempo de execução do método de atualização sobre a 4ª página de dados 6s

...

Você é capaz de me dizer onde está o problema? Tanto o tamanho das páginas, quanto a natureza dos dados que o método de atualização lidava não mudavam. Sendo assim, o tempo de execução de uma página deveria ser mais ou menos constante. Então como explicar esse resultado? Além do mais, não poderia ser problema de paginação de memória, já que eu havia tomado esse cuidado de antemão. Correto? Então o que poderia ser?

Minha análize do problema me dizia: isso cheira a problema de memória! Para confirmar ou refutar essa hipótese, verifiquei o consumo de memória do java. Estava mais alto do que seria esperado! Era problema de memória. Mas não deveria ser meu código que o está causando o problema, pois eu havia sido cuidadoso, inclusive eu havia incluído instruções de flush para garantir que eu teria apenas os dados de uma página na memória. 

Então formulei a seguinte hipótese: O Hibernate esta se tornando mais lento ao executar uma página, pois ele não deve estar fazendo o flush dos objetos já atualizados. Para confirmar ou refutar essa hipótese, recorri ao google e pesquisei o comportamento do Hibernate. Eis que em algum site eu encontrei a informação de que se você der um flush no Hibernate, fica a critério dele liberar memória ou não! Se eu quisesse forçar o Hibernate a fazer o flush e limpar sua memória interna eu deveria usar o método session.clear().

Adicionei uma chamada a session.clear(), testei novamente meu atualizador e voilá. Problema resolvido! 

Lembra da primeira execução do meu atualizador, pois é, ela ainda estava rodando quando terminei de resolver o problema. Ela gastou no final das contas uma hora e pouco para executar, enquanto a versão corrigida gastou menos de um minuto. (Deixei terminar de executar só para poder me gabar depois do speedup da alteração que eu fiz no código do meu atualizador :P)

A lição que fica aqui é que você sempre deve conhecer a arquitetura interna dos frameworks, bibliotecas, etc, que você usa. Esse conhecimento salva vidas e te poupa muita dor de cabeça.

P.S.: Observe que em nenhum momento eu saí colocando breakpoints no meu código e dando step in ou step out em algum debuger visual. A técnica de debug que eu usei para resolver esse problema (de fazer suposições, colher dados e rejeitar ou confirmar as suposições até encontrar o bug) é muito útil na solução de diversos problemas. Em uma outra oportunidade irei falar mais sobre ela.