Archive for January, 2008
Grafos no Orkut
Author: Jonas Abreu21 Jan
Essa é mais uma feature que o Google possui que está acelerando o processo de calvicie em mim.
Todo mundo conhece o orkut. Aquele sistema bobo, sem muita utilidade concreta mas que faz um sucesso absurdo (Inclusive, existe uma comunidade do VidaGeek.net lá).
O que muitos não notam é um pequeno detalhe que aparece quando você está no perfil de outra pessoa. O Orkut mostra pra você o caminho mais curto entre você e essa outra pessoa (atravéz de amigos).
O que que isso tem de assustador? É apenas uma busca em um grafo… Com milhões de vértices. Faça um programa simples que faz uma busca em um grafo com milhões de vértices e você vai entender do que estou falando. Demora muito mais do que uma requisição no Orkut pode demorar.
Ou seja, tudo isso está pré-calculado. Quando você acessa o perfil de outra pessoa, o algoritmo já rodou e ele simplesmente recupera a informação e devolve para você.
O jeito mais simples de fazer isso? Um Floyd-Warshall modificado (para não levar o peso das arestas em consideração), com complexidade O(n^3) rodado quando algum usuário se cadastra no Orkut ou sai dele.
Isso não funciona. Com a quantidade de usuários que o orkut tem, ele teria saido do ar há muito tempo se fosse desse jeito. Uma estratégia lazy (rodar apenas de tempos em tempos) também não ajuda muito, pois ocupa muito espaço em disco (quando o orkut foi criado, ele manteve vários milhares de usuário apenas com um computador comum como servidor).
O que é mais possível, então? Uma boa Heurística. Hoje mesmo eu notei que têm alguns profiles que eu entro e não aparece a sequência de usuários. Portanto, o que deve ser feito é estabelecer um limite na profundidade da busca, baseado nos seus amigos e nas comunidades em que você participa. Isso reduz de milhões de usuários para milhares de usuários. Mesmo assim ainda acho que é um esforço computacional muito grande e provavelmente deve ser rodado de forma lazy (especialmente se você lembrar que já está sendo usada uma heurística e nem sempre vai aparecer o caminho).
Posts Relacionados:
Acompanhe-nos por
RSS, por Email ou via Twitter.
Veja como ter um desconto no Dreamhost: um excelente servidor web.
Problemas Técnicos
Author: Jonas Abreu20 Jan
Nas últimas duas semanas o VidaGeek tem passado por alguns problemas técnicos. Isso está ocorrendo devido à atualização do WordPress que fizemos.
Alguns leitores viram mensagens de erros por causa de alguns plugins, um post faltando revisão foi publicado (Grafos no Orkut) mesmo estando agendado para segunda feira (hoje é domingo) e provavelmente todas as imagens que coloquei em meus posts foram perdidas porque o atualizador do wordpress removeu a pasta onde elas estavam.
Gostaria de pedir desculpas a todos os leitores por causa desses problemas. Espero que não se repitam no futuro.
Obrigado pela compreensão.
Posts Relacionados:
Acompanhe-nos por
RSS, por Email ou via Twitter.
Veja como ter um desconto no Dreamhost: um excelente servidor web.
TRUE & TRUE == FALSE ?
Author: Jonas Abreu18 Jan
Quando estamos programando, é muito comum precisarmos de um tipo booleano. Infelizmente o padrão Ansi C (isoc89) não possui um tipo primitivo para representar verdadeiro ou falso.
Qual a solução? Dentre várias, uma das mais perigosas e mais comum é essa:
typedef int bool;
#define TRUE 1
#define FALSE 0
Primeiro, como ela funciona:
Em C, como não existe boolean, qualquer inteiro diferente de 0 é considerado como verdadeiro e 0 é considerado falso. Portanto, nada mais lógico que pegar 0 e definir como falso e um outro número qualquer e definir como verdadeiro.
Qual o problema? Em 95% das aplicações que você normalmente faz, isso é uma solução perfeita, porque você sempre usa os operadores booleanos que encerram em curto-circuito (&& e ||).
A coisa muda totalmente de figura quando você usa os operadores bitwise (&, | e ^) para gerar condições booleanas. Isso é comum quando estamos usando funções que possuem efeitos colaterais (isso não é considerado uma prática muito boa, mas tem muita gente que usa isso ainda).
Imagine que você está usando uma função sua que produz efeitos colaterais e uma de uma biblioteca qualquer que também têm efeitos colaterais. As duas devolvem um inteiro diferente de 0 se bem sucedidas.
Como você é uma pessoa disciplinada, para garantir a consistência do seu sistema, quando você quer valores booleanos, você só atribui TRUE ou FALSE.
Se o código for esse, sem problemas:
if (sua_funcao() && funcao_da_lib())
faz_algo();
Mas isso é ruim, pois você precisa que as duas funções sejam executadas (mesmo se a sua falhar). O que você faz?
if (sua_funcao() & funcao_da_lib())
faz_algo();
Arranca um & de lá e passa 20 horas debuggando. Porquê? Simples. Por algum motivo estranho, o cara que escreveu a biblioteca que você está usando resolveu devolver 2 como verdadeiro. Olha que legal que fica se você substitui os valores devolvidos (em caso de sucesso) no lugar das funções:
if (1 & 2)
faz_algo();
Como dois não é impar, a função faz_algo() não será executada (causando uma grande dor de cabeça em você).
Mesmo você sendo o programador mais disciplinado da face da terra, não dá pra evitar problemas assim. Não dá pra ter controle sobre o código dos outros.
Para evitar esse tipo de problemas, eu costumo definir minhas constantes assim:
#include <limits.h>
typedef unsigned int bool;
#define TRUE UINT_MAX
#define FALSE 0
Isso protege contra todos os problemas? Não. Mas evita alguns que podem dar muita dor de cabeça. Isso porque tendo todos os bits setados como 1, quando usar o operador bitwise & ele só vai dar false se o outro valor não possuir nenhum bit setado para 1 (que é exatamente o que queremos).
Mas ainda bem que no padrão isoc99 existe o tipo bool. Vai evitar muitos problemas. Mas até ele ser realmente adotado ainda vai algum tempo.
Posts Relacionados:
Acompanhe-nos por
RSS, por Email ou via Twitter.
Veja como ter um desconto no Dreamhost: um excelente servidor web.
TDD para Ruby - Fibonacci
Author: convidados16 Jan
No livro Test-Driven Development By Example, Kent Beck mostra em um pequeno apêndice como criar a função que calcula o número de Fibonacci de forma recursiva através do Test-Driven Development(TDD, desenvolvimento direcionado por testes). Baseando-me neste exemplo, criei uma versão para Ruby.
Primeiro, gostariamos que fib(0) = 0. Para isso começamos a escrever o nosso teste:
#!/usr/bin/ruby
require ‘test/unit’
class TestFibonacci < Test::Unit::TestCase
def test_fib
assert_equal(0,Fibonacci.fib(0));
end
end
Rodando o teste temos, como esperado, um erro já que não criamos a classe Fibonacci. Devemos fazer agora o mínimo para que os testes passem. Isso inclui em adicionar a classe Fibonacci e criar uma implementação do método self.fib.
class Fibonacci
def self.fib(n)
return 0;
end
end
Rodando o teste descobrimos que está tudo bem. Podemos agora testar se fib(1) = 1, vamos modificar o teste anterior para incluir esta condição.:
def test_fib
assert_equal(0,Fibonacci.fib(0));
assert_equal(1,Fibonacci.fib(1));
end
Que obviamente não passará. Podemos mudar o self.fib para a seguinte versão:
def self.fib(n)
return 0 if(n == 0)
return 1
end
Os testes estão novamente passando, mas existe uma repetição entre eles, algo ruim de se fazer (use a metodologia DRY - Don’t Repeat Yourself). Vamos então refatorar o método test_fib:
def test_fib0
cases = [[0,0],[1,1]]
cases.each do
|c|
assert_equal(c[1],Fibonacci.fib(c[0]))
end
end
Temos agora os casos de teste compostos de pares (n,fib(n)). Podemos agora adicionar o par (2,1) e rodar os testes para ver que o método continua funcionando. Vamos então adicionar mais um teste, o par (3,2), portanto temos cases = [[0,0],[1,1],[2,1],[3,2]]. O teste não passa, podemos modificar o código rapidamente para resolver este problema.
def self.fib(n)
return 0 if(n == 0)
return 1 if(n <= 2)
return 2
end
Temos agora os testes passando e podemos generalizar para obter o resultado esperado. Ao invés de retornar 2, podemos retornar fib(n-1) + fib(n-2) (o passo completo seria 2 = 1 + 1 = fib(n-1) + 1 = fib(n-1) + fib(n-2) ). Abaixo está o código final:
#!/usr/bin/ruby
require ‘test/unit’
class TestFibonacci < Test::Unit::TestCase
def test_fib0
cases = [[0,0],[1,1],[2,1],[3,2]]
cases.each do
|c|
assert_equal(c[1],Fibonacci.fib(c[0]))
end
end
end
class Fibonacci
def self.fib(n)
return 0 if(n == 0)
return 1 if(n <= 2)
return fib(n-1) + fib(n-2)
end
end
Posts Relacionados:
Acompanhe-nos por
RSS, por Email ou via Twitter.
Veja como ter um desconto no Dreamhost: um excelente servidor web.
