Sabe quando você chega na casa de um programador, olha pra mesa dele e vê algo assim:

Livros por todos os lados, pilhas de CDs, caixas de placas, fios quase ameçando sua segurança, etc. Sua primeira reação (se você mantém uma mesa “arrumada”) é aparentar que nem notou, afinal amizade é pra essas coisas, né?

Mas você com certeza vai sair de lá pensando que aquele é seu amigo mais desorganizado. Você não imagina o quanto está errado. Aquela é uma das formas mais otimizadas de se manter uma mesa quando você usa muitas coisas diferentes e está sempre acrescentando mais itens.

Agora que você pensa que eu estou louco e que você deve cancelar a assinatura do nosso feed, leia mais um pouco que você vai entender.

Existe um tipo de árvore binária balanceada que possui um comportamento muito interessante.

A Splay Tree, muito útil para caching, funciona da seguinte forma:

Sempre que você acessa um item, ela se reorganiza inteira e leva esse item para a raiz da árvore. Assim, se você acessar esse mesmo item na próxima chamada, ele vai ser acessado muito mais rápido. Mas isso não costuma acontecer, certo? Sem problema. Quando você fizer a próxima busca o item que estava na raiz desce e se torna filho da raiz. Agora a chance de você querer ele já é maior e ele continua perto da raiz, facilitando o acesso a ele.

Essa árvore tem por característica manter mais próximo à raiz os itens mais acessados. Os outros vão descendo vagarosamente até as folhas. A altura dela não é logarítmica como em outras árvores, mas no caso médio ela se comporta como as outras.

Voltando ao assunto, o mesmo acontece com a mesa do programador. Os itens que ele utiliza com mais freqüência ficam mais próximos de suas mãos, minimizando o tempo gasto para pegá-los.

Da próxima vez que encontrar alguém que tem uma mesa muito bagunçada, desconfie de que é um bom programador, ao invés de achar que não passa de um desleixado ;).

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.

Hoje eu estou começando um novo projeto. Nada mais é do que um simples tracker de tarefas (uma todo-list com um pouquinho mais de recursos) escrito em Rails. Estou fazendo isso porque tenho tido várias idéias sobre projetos, mas acabo esquecendo porque não tenho um bom lugar para guardá-las (acabam em uma folha no meio de algum caderno que eu nunca lembro onde está).

Isso é muito ruim. De repente posso ter esquecido a idéia que seria o próximo YouTube (acho que não…). De qualquer forma, organização é uma necessidade para qualquer projeto, por menor que seja.

Então este pequeno projeto também deve ser bem organizado. Gastei uns 15 minutos pensando o que eu precisaria fazer e já comecei a me perder. Resolvi entãoi aproveitar o que eu aprendi sobre XP no meu estágio e aplicar isso nesse projetinho.

Uma das coisas que eu mais gostei de XP foi da lousa. Nunca pensei que uma combinação de lousa com post-its pudesse ser tão produtiva. Mas foi aí que me surgiu um problema. Eu tinha post-its, cartões, canetas mas nenhuma lousa. Se eu saísse para comprar iria perder várias horas (duvido que eu fosse encontrar um lousa aqui em Ribeirão Pires). Bom, o que não se resolve permanentemente a gente resolve temporáriamente.

Esse é o resultado:

Minha janela do quarto está cumprindo muito bem o papel de lousa. O único problema é que era difícil de ver o que estava escrito. Então coloquei algumas folhas de papel atrás.

Pois é… acho que não tem nada que um pouco de criatividade não resolva. Alguém mais já encontrou alguma solução estranha como essa?

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.

Quando estudamos estruturas de dados, aprendemos que um Hash, no caso médio (ou no caso de um hashing perfeito) é mais rápido (possui menor complexidade) que uma árvore balanceada, como a árvore Rubro-Negra. A teoria nos prova isso. E na prática?

Rodei o seguinte programa para comparar os dois:

package net.vidageek.benchmark;

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class DumbHashTreeBenchmark {

	private static final int INCREMENTO = 500000;

	private static final int MAX_BEFORE_CRASH = 2000001;

	public static void main(String[] args) {
		for (int i = 0; i < MAX_BEFORE_CRASH; i += INCREMENTO) {
			Set hash = new HashSet();
			Set tree = new TreeSet();

			System.out.println("Teste: n = " + i + " Tempo Hash: "
					+ popula(hash, i) + " Tempo Árvore: " + popula(tree, i));

		}

	}

	private static long popula(Set set, int n) {
		long inicio, fim;
		inicio = System.currentTimeMillis();
		for (int i = 0; i < n; i++)
			set.add(i);
		fim = System.currentTimeMillis();
		return fim - inicio;
	}
}

O resultado disso parece bem estranho (o tempo está em milisegundos):

Porque que nos dois primeiros testes o TreeSet foi mais eficiente que o HashSet? Em teoria o HashSet deveria ser mais rápido, não é? Não.

Usar um Hash é muito eficiente sob certas condições:

1. A tabela de hashing é consideravelmente maior que a quantidade de itens a serem inseridos nela;
2. A função de hashing é boa.

Embora eu não tenha visto a implementação da função de hashing, tenho certeza de que ela é boa. Uma empresa do tamanho da Sun não arriscaria o nome com algo tão besta. Então o problema só pode ser a tabela de hashing.

Como não disse qual deveria ser o tamanho da tabela, ela foi criada com o valor padrão (16). Como eu tentei inserir uma quantidade muito superior ao tamanho da tabela, ela teve que ficar sendo realocada. Essa operação chama-se re-hashing e é possui custo muito alto, porque envolve alocação de uma nova tabela maior que a anterior e cálculo da função de hashing de todos os elementos dentro dela. Basicamente um novo HashSet é contruído a cada vez que a tabela fica com itens demais. O tempo que é perdido com essa operação da uma vantagem bem grande para o TreeSet que acaba tendo um desempenho melhor por falha do programador. Para mostrar isso fiz uma pequena modificação no main do programa anterior:

public static void main(String[] args) {
	for (int i = 0; i < MAX_BEFORE_CRASH; i += INCREMENTO) {
		Set hash = new HashSet(2*MAX_BEFORE_CRASH);
		Set tree = new TreeSet();

		System.out.println("Teste: n = " + i + " Tempo Hash: "
				+ popula(hash, i) + " Tempo Árvore: " + popula(tree, i));

	}
}

Vejam a diferença assustadora dos resultados:

Ainda daria pra fazer o HashSet se comportar de forma mais rápida, movendo a criação dele para fora do laço e esvaziando ele no fim de cada iteração.

Em uma máquina com menos disponibilidade de mémoria (a que eu usei para o teste possui 2GB) se um HashSet for usado como da primeira maneira, ele será muito pior que o TreeSet. Por isso é muito importante saber sob quais condições uma estrutura de dados é melhor do que outra.

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.