Um encontro da teoria com a prática na ciência da computação – parte 2

Dando continuidade ao artigo já publicado um encontro da teoria com a prática no curso de ciência da computação, será apresentado um novo cenário onde, embora os conceitos aplicados sejam simples, estes também contribuem para a proposta de aperfeiçoar o entendimento referente à aplicabilidade da teoria ensinada em cursos de graduação que envolvem Computação.

Recentemente, foi solicitado que nossa equipe realizasse uma migração de dados, onde esta deveria ser importada para o banco de dados da empresa, contemplando algumas tabelas que se encontravam no servidor de um determinado fornecedor. Com isso, foram recebidos alguns arquivos com extensão txt, onde cada um destes envolvia uma tabela que deveria ser importada.

Para exemplificar melhor, um dos arquivos recebidos, intitulado compras.txt diz respeito a tabela compras do banco de dados. Dentro deste arquivo, cada linha representa uma linha da tabela mencionada, sendo que para identificar o conteúdo de cada coluna, o arquivo utiliza o caractere delimitador §. Desta forma, o conteúdo do arquivo possui um formato semelhante ao mencionado logo abaixo:

cpf_cliente§conta§valor_comprado§vencimento
05069358674§40582§99.50§2012-09-30

Antes de importar os dados em ambiente de produção, obviamente estes deveriam antes ser validados em ambiente de teste. Contudo, há um pequeno detalhe: alguns destes arquivos possuem tamanho consideravelmente grande. Somente o arquivo mencionado de compras possui tamanho de 18 GB, com cerca de 135 milhões de linhas. Dado o imenso volume de dados a ser importado, concluiu-se que seria necessário trabalhar em ambiente de teste apenas com uma amostra, ou seja, ao invés de importar para este ambiente todas as 135 milhões de compras, deveriam ser importadas apenas as compras referentes a uma amostra de dez mil contas selecionadas para validação. Para isso, estas contas foram colocadas em um arquivo, e deveria ser gerado um novo arquivo contemplando apenas as compras destas.

Ao analisar a solução empregada, foi adotada uma alternativa simples, onde primeiramente importava a amostragem de contas em uma lista, como mostra o código abaixo, escrito na linguagem VB.NET:

Dim arquivoContas As System.IO.StreamReader
arquivoContas = System.IO.File.OpenText(“c:\contas.txt”)

Dim listaContas As List(Of String) = New List(Of String)

Dim linhaArquivoContas As String = arquivoContas.ReadLine

While Not linhaArquivoContas Is Nothing
listaContas.Add(linhaArquivoContas)
linhaArquivoContas = arquivoContas.ReadLine
End While

Após este procedimento, foi realizado um loop no imenso arquivo de compras, verificando para cada uma das 135 milhões de linhas, se a conta de cada linha está na lista de contas importada no código apresentado acima. E caso sim, esta linha precisa ser salva em um novo arquivo. O código abaixo mostra o procedimento realizado

Dim cp1252 As Encoding = Encoding.GetEncoding(1252)
Dim arquivoSaida As System.IO.StreamWriter
arquivoSaida = New System.IO.StreamWriter(“c:\COMPRAS_AMOSTRA.txt”, False, cp1252)

Dim arquivoCompras As System.IO.StreamReader
arquivoCompras = System.IO.File.OpenText(“C:\COMPRAS.txt”)

Dim linhaArquivoCompras = arquivoCompras.ReadLine

While Not linhaArquivoCompras Is Nothing
Dim numeroConta As String = linhaArquivoCompras.Split(“§”).GetValue(1)
If listaContas.Contains(numeroConta) Then
arquivoSaida.WriteLine(linhaArquivoCompras)
End If
linhaArquivoCompras = arquivoCompras.ReadLine
End While
arquivoSaida.Close()

Ao analisar a resposta, a execução do código estava devolvendo a saída esperada, contudo após 2 horas de processamento, apenas 18 das 135 milhões de linhas haviam sido lidas. Caso o processamento continuasse linear a este tempo, este processo gastaria cerca de quinze horas para ser concluído. E ainda precisavam ser importados mais alguns arquivos de tamanho proporcional a este, como extratos, pagamentos, entre outros. Estava claro que, embora fosse necessário efetuar este processamento apenas uma única vez, o desempenho se encontrava em um estado crítico e ninguém iria querer esperar alguns dias apenas para ser gerada uma amostra de testes. E importar toda a base de dados para ambiente de teste também estava fora de cogitação. Ao depararmos com este código, rapidamente foi percebido que, para cada uma das 135 milhões de linhas a serem importadas, este método contains() faz uma busca ao tradicional estilo “tentativa-erro” nas 10 mil contas, ou seja, o número de comparações é consideravelmente alto.

Para resolver o problema, foi necessário lançar mão de um simples conceito ensinado em cadeiras como Estrutura de Dados ou Análise de Algoritmos, que é a busca binária. Empregando este, basta ordenar a lista das contas uma única vez (por se tratar de apenas 10 mil contas, o algoritmo de ordenação empregado praticamente não terá impacto na solução), e após isso, buscar o elemento nesta lista ordenada quebrando a lista recursivamente. Em uma linguagem de alto nível como VB.NET, a implementação está pronta, bastando ordenar a lista com um método como listaContas.Sort() , e após isso, substituir a implementação do loop While por:

While Not linhaArquivoCompras Is Nothing
Dim numeroConta As String = linhaArquivoCompras.Split(“§”).GetValue(1)
Dim index As Integer = listaContas.BinarySearch(numeroConta)
If index > 0 Then
arquivoSaida.WriteLine(linhaArquivoCompras)
End If
linhaArquivoCompras = arquivoCompras.ReadLine
End While

Com esta simples modificação, o processamento diminuiu de quinze horas para apenas meia hora, viabilizando rapidamente todos os arquivos, contemplando as amostras desejadas. É óbvio que algumas linguagens podem não possuir esta facilidade dos métodos prontos, contudo é consideravelmente simples criar métodos de ordenação e busca binária.

É óbvio que muitos podem argumentar que nunca precisaram de soluções desta natureza, mas é necessário analisar as possibilidades de entrada referente a cada caso, além de possíveis restrições de processamento, especialmente em casos onde as buscas de dados precisem funcionar em dispositivos móveis. No problema citado, caso a entrada fosse menor, da grandeza de apenas alguns milhares de linhas, provavelmente muitos não se importariam em utilizar a pior solução, pois esta perderia poucos segundos em relação à melhor solução, o que em um cenário como o mencionado é irrelevante. Mas, em entradas maiores, bons algoritmos certamente farão uma grande diferença, como foi apresentado. Por isso que, mesmo com tantas soluções e componentes prontos, em muitos cenários o domínio dos conceitos será primordial, e este tipo de profissional sempre será cobiçado.

Concluindo, pode-se ver mais uma vez que, conceitos aprendidos nos cursos de graduação envolvendo computação são e sempre serão muito úteis na resolução de diversos problemas de mercado, destacando profissionais que valorizaram os fundamentos teóricos. Este artigo obviamente não teve nenhuma intenção no ensino da técnica busca binária, que é simples e bastante disseminada em qualquer graduação decente de computação, mas apenas em evidenciar como esta poderia ser utilizada em casos onde o seu uso faria toda a diferença.

About CarlosEduardoXP

Especialista em desenvolvimento de Sistemas Distribuídos, sempre aplicando boas práticas e padrões difundidos na comunidade. Auto didata, fanático por refatoração e performance, sempre buscando reutilização e testes automatizados cada vez mais eficazes.
This entry was posted in Software Development. Bookmark the permalink.

2 Responses to Um encontro da teoria com a prática na ciência da computação – parte 2

  1. Hugo says:

    Excelente post. Hoje em dia com os diversos frameworks existentes entregando tudo mastigado, nem todos se dão ao trabalho de buscar a melhor solução para os problemas enfrentados no dia a dia.

  2. Carlos,

    Olha que interessante, acabei de comentar no seu outro post e essa solução que você adotou já aconteceu comigo e também resolvi o problema da mesma forma.

    Nesses momentos, a satisfação profissional valem a pena – Conforme você citou no outro Post.

    Até mais.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s