Arquivos mensais: dezembro 2013

O paradigma BigData

Vemos por aí tanta gente falando sobre o tal BigData, então pareceu ser uma ótima oportunidade para fazer um post sobre ele!

Afinal o que é BigData?

Vamos primeiro analisar a motivação por trás dele, que levou ao surgimento do termo.

Cena do filme Matrix. No contexto de BigData, a informação circula constantemente por todos os lados.

Atualmente estamos vivendo a era das redes sociais, do conteúdo multimídia distribuído, da informação contextual e democratizada.

Os usuários geram conteúdo!

A informação não flui mais apenas em uma direção, do provedor de conteúdo aos usuários, agora os grandes geradores de informação são os próprios usuários. Diante desse cenário, temos um aumento significante no fluxo de informação, ao qual um serviço precisa dar vazão, e também da complexidade, pois já não existe só uma entidade controlando o conteúdo.

Agora é a vez da estatística!

Outra grande mudança foi no valor da informação. No paradigma BigData fazemos as seguintes perguntas:

  • Quantos usuários do Facebook estão postando sobre um mesmo assunto?
  • Qual a relação entre a faixa etária e os termos buscados no Google?
  • Que categoria de vídeo gera visualizações mais rapidamente no Youtube?

A resposta para essas e muitas outras perguntas são as que criam novas oportunidades de negócio, e para obter a informação necessária para respondê-las é necessário guardar todo tipo de informação que circula em um sistema, o que passa a ser inviável com as soluções existentes de banco de dados relacional, pois não será possível operar no fluxo e crescimento da ordem de Terabytes/segundo.

São muitos dados!

Para resolver esse problema, foi necessário pensar diferente, pensar NoSQL!

Para suportar um sistema da ordem de grandeza de TB/s, é necessário um banco de dados com propriedades naturalmente escaláveis, semi-estruturado (já pensou em adicionar uma coluna a uma tabela com 10 bilhões de registros?) e que possa ser fragmentado (vamos manter réplicas dos registros, não do banco todo!). Diante dessas características, o BigData foi aos poucos se moldando, cada vez se contrastando mais com os outros paradigmas, até se definir como um novo e único paradigma.

Por onde eu começo?

O Google foi o grande pioneiro nessa área,  a integração entre seus serviços de busca e propaganda levou aos primeiros modelos de implementação: a BigTable!

A BigTable pode ser vista como uma matriz esparsa tridimensional, ou como um simples JSON de 3 chaves: { “column family: column”, “row”, “timestamp” : “value” }. Essa configuração permite um emprego muito variado de estruturas, como por exemplo:

  • Rows são endereços de páginas, Column Families são tipos de tags presentes no HTML, as Columns são as tags, o Timestamp é a data de modificação, e o valor é o título da página.
  • Rows são posições de latitude, Columns são longitude, Timestamp é a data da última atualização, e o valor é a imagem de satélite em bytes.

Exemplo do Google de organização dos dados coletados por web crawlers.

Exemplo do Google de organização dos dados coletados por web crawlers.

O Google não foi bonzinho em abrir o código da BigTable, porém nossos amigos da Apache implementaram a descrição conceitual que pode ser encontrada neste artigo do Google LINK.

Enter Hadoop e HBase

Para não haver confusão (no meu dia-a-dia eu vejo muita confusão sobre isto!), vamos dar nomes aos bois!

A ferramenta HBase é responsável por implementar a BigTable em si, ela proporciona a mesma estrutura, column families, timestamps, exatamente como descrito pelo Google.

A ferramenta Hadoop é a que faz a magia acontecer. Para se ter um ambiente de BigData operacional, é necessário criar um cluster de no mínimo 4 máquinas, com um sistema de arquivos distribuído, com gerenciamento de replicação, fornecer uma plataforma de desenvolvimento de operações de Inserção, Busca, Remoção (em outras palavras, Map-Reduce) para assim permitir que o sistema seja escalável, fragmentado, replicado e dê vazão para a aplicação!

Ambos são disponibilizados gratuitamente pela Apache, implementados em Java, e fornecem a camada mais baixa de uma aplicação, que é a de gerenciamento do banco de dados em si. Ao se desenvolver uma aplicação BigData, é necessário desenvolver a camada DAO da sua aplicação, e possívelmente será necessário criar APIs para isso, pois cada emprego de BigData define sua própria organização dos dados!

Fechando

Bom agora já dá pra ter uma idéia do que diabos é BigData, como funciona, e por onde dar os primeiros passos, lembrando que BigData não é pra se fazer sistema de padaria! Sempre que estiver em dúvida em usar ou não BigData lembre-se dos seguintes termos: Volume (TB/s), Variedade (Dados semi-estruturados) e Velocidade (Clusters de várias máquinas).

Algoritmo – Um noção sobre Custos

Cena do filme Rede Social

Hoje, vou falar um pouco sobre custos de execução dos algoritmos. A ideia é passar uma noção de como mensurar o custo de um algoritmo.

Vamos pegar o problema abaixo:

Some todos os números entre 1 e 100

A primeira abordagem para resolver o problema acima seria a implementação abaixo:

int total = 0;
for(int i = 1; i <= 100; i++ )
   total = total + i;

Obs: Graças ao Caio, conseguimos colocar código aqui no blog =)

Quanto custa para o computador executar o algoritmo acima ?

Imagine que para cada instrução executada o custo seja 1, por exemplo:

  • Criar a variável total com valor 0, custa 1
  • Criar a variável com valor 1, custa 1
  • Comparar com 100, custa 1
  • Somar total com i e atribuir a total, custa 1
  • Incrementar i, custa 1

Com isso, podemos dizer que a implementação acima tem custo 1 + 1 + 3 * 100 = 302. Porque:

  • 1 – Para criar a variável total
  • 1 – Para criar a variável i
  • 300 – Para cada loop do for temos um custo de 3 ( comparação, soma e incremento) e como são 100 loops teremos um custo de 300.

Agora vamos dificultar um pouco as coisas:

Some todos os números pares entre 1 e 100

Implementando:

int total = 0;
for(int i = 1; i <= 100; i++ )
   if ( i % 2 == 0 )
      total = total + i;

O custo do algoritmo algoritmo sobe para 502 agora, porque colocamos uma instrução aritmética ( i % 2 ) e uma de comparação ( i % 2 == 0 ), ou seja adicionamos 2 de custo para cada loop.

Melhorando…

Imagine que você está executando o algoritmo acima em um celular bem, mas bem velho e bem limitado, você precisa otimizar o algoritmo para somar os números pares. Depois de pensar muito você chegou nisso:

int total = 0;
for(int i = 2; i <= 100; i += 2 )
      total = total + i;

O custo do algoritmo acima é 1 + 1 + 3 * 50 = 152. Porque:

  • 1 – Para criar a variável total
  • 1 – Para criar a variável i
  • 150 – Reduzimos a quantidade de loops para 50, pois incrementamos de 2 em 2 a partir de 2 (papo de louco), mas o custo por loop ainda é 3, logo 3 * 50 = 150

Por quê entender custos?

Ao analisar a segunda implementação que tem custo 502, fica claro que o gargalo está no for e o jeito de melhorá-lo é diminuir o custo dos loops. Você só chega nessa conclusão entendo o custo de execução do algoritmo.

Gauss

Será que dá pra diminuir mais o custo ? 152 é o mínimo ?

Voltando para a oitava série, você deve se lembrar da história sobre Gauss ( todo professor de matemática conta, eu acho =P ).

Um dia na escola de Gauss ( que tinha 8 anos segundo a lenda ), a professora de matemática estava cansada para dar aula, então pediu para os alunos somarem os números de 1 a 100, isso iria ocupar um bom tempo deles. Para infelicidade da professora, em alguns minutos, Gauss aparece com a resposta, ele havia criado a fórmula da progressão aritmética.

Sn = (( a1 + an ) *  n ) / 2

Para conhecer mais: http://pt.wikipedia.org/wiki/Progressão_aritmética

Importância da matemática

Se implementarmos a fórmula de Gauss para os número de 1 a 100:

int total = ((1 + 100) * 100) / 2;

O custo é de 1 + 1 + 1 + 1 = 4. Porque:

  • 1 – Para a operação de soma
  • 1 – Para a operação de multiplicação
  • 1 – Para a operação de divisão
  • 1 – Criar a variável total e atribuir o valor

Agora implementando a fórmula para os números pares:

int total = ((2 + 100) * 50) / 2;

Veja que o custo continua mesmo. É a melhor solução para fazer a soma de um intervalo de números =) . Pois o custo não é sensível aos dados de entrada como nas 3 primeiras implementações, ou seja, se eu quiser somar um número de 1 a 1.000.000, ainda teria custo 4, já na implementação que utiliza o for o custo seria de 3.000.002.

A solução aritmética é sempre a melhor, por isso dê mais valor as aulas de matemática na escola e na faculdade.

O objetivo desse post é passar essa noção de custo e não explicar ao fundo como é mensurado o custo de um algoritmo, pois nem toda instrução tem custo 1, se quiser aprofundar no assunto indico o livro abaixo:

http://www.livrariasaraiva.com.br/produto/4061865

Para o dia a dia, o importante é ter uma noção, não precisa ser o expert em custos. Esse conhecimento é aplicado em outras áreas e não apenas programação, como em processos de produção ou até mesmo numa viagem de fim de semana.

Abraço!

IOS – Trabalhando com cores em Hexadecimais

IMG_0007

Desenvolvemos um aplicativo mobile, no qual o usuário poderia consultar informações da sua empresa como desempenho das vendas e o atingimento das metas.

A ideia era fazer algo semelhante ao Google Now, distribuindo as informações em cartões:

Para deixar o conteúdo de forma customizável o aplicativo solicitava um xml do servidor do cliente. Através desse xml é montado os cartões e as informações dentro dele. Um exemplo está abaixo:

<cards>

<card>

<data>

<line>

<label>Venda</label>

<value>R$ 1.000,00</value>

</line>

</data>

</card>

</cards>

No xml acima não existe o atributo de cor em nenhuma das tags. Decidimos adicionar o atributo color nas tags label e value (da tag line), assim o cliente poderia customizar a cor das ‘linhas’.

No iOS trabalhamos com o UIColor para gerar as cores. Mas UIColor recebe como parâmetro 4 valores ( red, green, blue, alpha ) seria ruim adicionar esses 4 paramêtros na tag, ficando assim:

<line>

<label>Venda</label>

<value colorRed=”255″ colorGreen=”255″ colorBlue=”255″ colorAlpha=”1″>R$ 1.000,00</value>

</line>

Pensamos em trabalhar com cores hexadecimais que reduz os 4 atributos para 1 só. Removemos também o atributo alpha, ficando assim:

<value color=”#00FFD2″>R$ 1.000,00</value>

Agora precisamos dentro da aplicação interpretar o valor hexadecimal e criar um objeto UIColor.

Entendo a cor hexadecimal

Uma cor ela pode ser composta pela variação das 3 cores primárias.

 

Na cor hexadecimal, cada par representa a intensidade de uma cor primária, essa composição forma uma nova cor:

#00FFD2

Como a cor está em base 16 ( hexa ) precisamos converter para base 10 ( decimal ) assim poderemos usar na UIColor. Para entender mais sobre conversão entre sistemas numéricos veja este link: http://pt.wikipedia.org/wiki/Conversão_entre_sistemas_numéricos

Abaixo segue uma implementação em objective-c para conversão de base 16 para base 10:

Screen Shot 2013-12-05 at 7.59.17 AM
Pessoal, não achei um jeito de postar código aqui no blog, por isso a screenshot. Vamos melhor nos próximos posts.

Obs: Podemos converter qualquer caracter para número apenas subtraindo por outro caracter. Ex.:

O caracter ‘1’ pode ser convertido para o valor inteiro 1 fazendo isso:

‘1’ – ‘0’ = 1 (inteiro)

Isso funciona porque a representação decimal desses caracteres é 31 e 30, respectivamente, ou seja, quando fazemos ‘1’ – ‘0’, na verdade estamos fazendo 31 – 30.

Logo, podemos converter ‘A’ para 10 fazendo ‘A’ – ‘A’ + 10.

Agora sabendo como converter a cor hexa para decimal basta criar UIColor com os valores decimais.

Segue abaixo uma implementação para criar UIColor a partir de cor hexadecimal:

Screen Shot 2013-12-05 at 8.10.44 AM

Abraço e até a próxima!