segunda-feira, 14 de junho de 2010

A lei de Benford

Muitos conjuntos de dados apresentam uma propriedade interessante: os primeiros dígitos não aparecem todos com a mesma freqüência.

A lei de Benford prevê que os dígitos mais baixos apareçam com maior freqüência.

Esta lei funciona especialmente bem com números que crescem exponencialmente como preços e salários. O crescimento exponencial torna os dígitos mais altos mais raros, porque eles somem rapidamente. Se um produto tem um preço inicial 100, ele vai ficar valendo entre 100 e 199 o dobro do tempo que ficará valendo entre 200 e 299. Isto porque a inflação e os juros são cumulativos e, portanto, crescem exponencialmente.

Então, armado com este novo conhecimento, decidi avaliar minha base de preços.

select
substr(preco, 1, 1),
trunc((count(1)/29528)*100,2)
from produtos
group by substr(preco, 1, 1)
order by 2 desc

Em primeiro lugar, contei os registros para simplificar a consulta e fazer o cálculo mais rapidamente. Já dá para deduzir que tenho 29.528 registros. Os dados são do mundo real; eu não gerei números aleatoriamente.

A tabela abaixo mostra a distribuição dos primeiros dígitos:

DígitoFFe
133,65%30,1%
217,49%17,6%
312,93%12,5%
49,49%9,7%
58,71%7,9%
66,26%6,7%
74,83%5,8%
83,9%5,1%
92,7%4,6%

F é a freqüência encontrada e Fe é a freqüência esperada. Como se pode ver, a previsão chegou muito perto da realidade.

Essa lei, além de ser curiosa, é útil para apontar dados problemáticos na contabilidade forense. Distribuições muito estranhas podem colocar em evidência tentativas de esconder maracutaias financeiras.

quinta-feira, 10 de junho de 2010

Hey Hey 16K

Já vi algumas músicas com referências a tecnologia, mas este é o primeiro que vejo dedicado aos micros de 8 bits e com BASIC na letra.


É um Flash de uns 2MB, então carrega rápido. Para ajudar a cantar, ele já vai mostrando a letra.

Divirta-se!

sexta-feira, 4 de junho de 2010

O coeficiente de Gini em SQL

O coeficiente de Gini é uma medida de desigualdade usado na economia para avaliar a distribuição de renda de diferentes sociedades.

Ele é um número entre 0 e 1, sendo 1 a desigualdade completa (uma única pessoa tem toda a riqueza) e 0 a igualdade total (todos ganham a mesma coisa). O número também é interpretado como a metade da diferença média normalizada. Ou seja, se a média é R$1.000 e o coeficiente de Gini for 0,6, então a diferença média entre rendas vai ser R$1.000*0,6*2=R$1.200. Ou seja, neste caso, a diferença média é maior que a média; esta seria uma sociedade bastante desigual. Países considerados avançados, como os da Escandinávia têm coeficientes entre 0,2 e 0,3. Países como Brasil, Uruguai, Estados Unidos e China, têm coeficientes entre 0,4 e 0,5. Atualmente, o país mais desigual do mundo é a Namíbia, com 0,707.

Na falta de dados sobre renda, usei uma lista de produtos. Mesmo assim, vou supor estar usando uma tabela PESSOAS com as seguintes colunas:
  • ID - um identificador único para casa pessoa;
  • SALARIO - o salário.

Usando a definição supracitada, escrevi o seguinte no Oracle:

select (diff/media)/2 from (
select avg(abs(p1.salario-p2.salario)) diff
from pessoas p1, pessoas p2
where p1.id<>p2.id
),(
select avg(salario) media
from pessoas
)

Temos dois cross-joins. O primeiro é terrível, porque multiplica todos os registros da tabela por ela mesma para calular as diferenças. Como eu tinha 14.354 registros, o cross-join resultante disso tinha 206.022.962 linhas. Nada bom. Se eu quisesse calcular o coeficiente de Gini do Brasil, teria que usar uma tabela de uns 190 milhões de registros e isso não ia funcionar. O segundo é inócuo, porque o último select produz apenas uma linha.

Por sorte, um economista chamado Angus Deanton encontrou uma maneira melhor de calcular isto. Na fórmula abaixo, N é o número total de indivíduos, u é a média dos rendimentos, X é o rendimento de cada um e P é a classificação de cada um (sendo 1 o mais rico e N o mais pobre).


Isso é muito mais eficiente, porque agora não é mais preciso comparar cada um a todos os demais.

A consulta resultante usa a função analítica ROW_NUMBER() para classificar os salários:

select ((n+1)/(n-1))-(2/(n*(n-1)*media))*sum(pc*salario) from (
select salario, row_number() over (order by salario desc) pc
from pessoas
), (
select avg(salario) media, count(1) n
from pessoas
) group by n, media

A tabela abaixo compara os resultados:

SELECTTempoResultado
167,94s0,55617007994480478319584630635542608397
20,03s0,5561700799448047831958463063554260839701

O segundo, além de ser 2.264 vezes mais rápido, ainda produziu mais duas casas de precisão que, por outro lado, não têm nenhuma utilidade.

segunda-feira, 31 de maio de 2010

O oráculo e o camelo

Tive que carregar uma base de dados com o conteúdo de dois DVDs cheios de informações. Os dados estavam separados em arquivos texto que por sua vez estavam dentro vários níveis de pastas.

A primeira tentativa foi usar um script em Perl. A solução funcionou, mas não foi rápida o suficiente para o curto espaço de tempo disponível (como sempre, o prazo era exíguo). Rápido mesmo foi usar o SQL Loader.

Mesmo assim, vou descrever a solução em Perl. Ela não é tão rápida, mas ela é mais flexível.

Em primeiro lugar, usei o módulo Find para buscar os arquivos. O módulo é dos básicos, então sempre está disponível.

Uma linha basta para disparar uma busca em uma hierarquia de pastas:

find(\&process_file, $ARGV[0]);

Essa linha dispara a busca com o valor do primeiro argumento dado ao script. Esse argumento deve conter o caminho de uma pasta. Para cada arquivo que o find() encontrar, ele invocará a função process_file().

Antes de apresentar a process_file(), vou mostrar a estrutura de dados que faz o relacionamento entre os nomes dos arquivos, seus formatos e os respectivos inserts.

my $tables={
'PRODUTOS' => {
format => 'A4A20A10',
insert => q{insert into produtos (codigo, descricao, valor)
values (?,?,?/100)}
},
'PESSOAS' => {
format => 'A11A60A8',
insert => q{insert into pessoas (cpf, nome, data_nascimento)
values (?,?,to_date(?, 'DDMMYYYY'))}
}
};

A referência $table aponta para um hash; cada chave do hash representa uma tabela cujo nome coincide com o nome do arquivo; associado a cada nome de tabela está um formato e um insert. Uso referências como poderia usar hashes diretamente.

A função process_file(), então, determina se existe um mapeamento para cada arquivo encontrado e invoca a função load() quando existir.

sub process_file {
my $filename=$File::Find::name;
my $name=$_;

if($name=~/(\w+)\.txt/) {
if(exists $tables->{$1}) {
load($filename, $1);
}
}
}

Os nomes dos arquivos têm os mesmos nomes das tabelas e o sufixo "txt". Usando uma expressão regular, determino se o arquivo tem o sufixo desejado e uso a primeira parte do nome ($1) para encontrar o mapeamento.

Para extrair os dados dos arquivos, uso a função unpack(). Esta função recebe um string que descreve uma linha e a linha propriamente dita. Usando a descrição, ela divide a linha e produz um array com os campos. Então, para percorrer um arquivo texto com 3 colunas de 10 caracteres cada, bastaria fazer o seguinte:

while(<FILE>) {
my @cols=unpack("A10A10A10");
}

O segundo parâmetro é implícito (<FILE> coloca a linha lida em $_ e unpack() o usa como parâmetro implícito).

Para gravar os dados, uso o DBI, que é o módulo de acesso a bases de dados. O exemplo abaixo mostra como abrir uma conexão, preparar um comando e executá-lo.

$db = DBI->connect( "dbi:Oracle:host=HOST;sid=SID", "SCHEMA", "PASSSWD" )
|| die( $DBI::errstr . "\n" );
$st=$db->prepare('INSERT INTO PRODUTOS (CODIGO, NOME, VALOR) VALUES(?,?,?)');
$st->execute('0123', 'BOLA', 49.95);

Juntando o unpack() com o DBI, o resultado é:

sub load {
my ($filename, $table)=@_;
my $format=$tables->{$table}->{format};
my $insert=$tables->{$table}->{insert};

open(my $fh, "<$filename");
my $st=$db->prepare($insert);
while(<$fh>) {
my @row=unpack($format, $_);
$st->execute(@row);
}
$db->commit();
close($fh);
}

A função unpack() produz um array e o método execute() recebe um array. Não podia ser mais fácil. Executo um commit() por arquivo, mas poderia muito bem executar um único commit no fim de tudo.

E, finalmente, juntando todas as partes tem-se:

#!/usr/bin/perl
use DBI;
use File::Find;

my $db = DBI->connect( "dbi:Oracle:host=HOST;sid=SID", "SCHEMA", "PASSSWD" )
|| die( $DBI::errstr . "\n" );
$db->{AutoCommit} = 0;
$db->{RaiseError} = 1;

my $tables={
'PRODUTOS' => {
format => 'A4A20A10',
insert => q{insert into produtos (codigo, descricao, valor)
values (?,?,?/100)}
},
'PESSOAS' => {
format => 'A11A60A8',
insert => q{insert into pessoas (cpf, nome, data_nascimento)
values (?,?,to_date(?, 'DDMMYYYY'))}
}
};

sub load {
my ($filename, $table)=@_;
my $format=$tables->{$table}->{format};
my $insert=$tables->{$table}->{insert};

open(my $fh, "<$filename");
my $st=$db->prepare($insert);
while(<$fh>) {
my @row=unpack($format, $_);
$st->execute(@row);
}
$db->commit();
close($fh);
}

sub process_file {
my $filename=$File::Find::name;
my $name=$_;

if($name=~/(\w+)\.txt/) {
if(exists $tables->{$1}) {
load($filename, $1);
}
}
}

find(\&process_file, $ARGV[0]);

sábado, 22 de maio de 2010

Império dos 8 bits II

A Europa parece ter sido o centro do Império de 8 bits porque a maior parte de seus países fabricou máquinas desse tipo. Um fato interessante é que todos os países socialistas tiveram suas próprias máquinas, exceto a Albânia.


No ocidente, há algumas faltas surpreendentes, como a Suíça e a Noruega. Ambos são países ricos e tecnologicamente avançados. Mesmo assim, não parecem ter se interessado pelos micros.

Portugal, Grécia e Irlanda estão hoje no centro dos problemas financeiros da Europa e na década de 1980 eram os mais pobres do ocidente. Não é estranho que não tenham tido seus próprios computadores.

O Reino Unido era o centro mais ativo. No auge, teve 600 fabricantes. Pode-se contar nos dedos os modelos dos outros países. A França foi a única a fazer frente aos ingleses, talvez por rivalidade. Enquanto os ingleses atacavam em todas as frentes (e ganhavam muito dinheiro com jogos), os sisudos franceses pareciam estar mais interessados no mercado corporativo.

Os países do leste fabricaram muitos clones do Apple II e do ZX Spectrum, embora alguns modelos tenham sido realmente interessantes. Os Pravetz foram muito usados em colégios da Bulgária e neles foi desenvolvido o vírus Dark Avenger, que atacava os Apple II. O Jet da Romênia (fabricados pela Electromagnetica) usava a carcaça de um telefone e as teclas eram identificadas com papéis escritos à mão. Os alemães orientais levaram muito a sério a concorrência com o ocidente e chegaram a produzir memórias de 1 megabit.

Os russos usavam os micros principalmente nos centros de pesquisa, mas em 1983 publicaram o projeto do Micro-80 na revista Radio. Foi o primeiro computador DIY e baseava-se no processador 8080 da Intel. Seguiram-no vários projetos publicados em revistas soviéticas.

Um pouco mais atrasados, os países do leste continuaram a produzir micros de 8 bits até o início dos anos 1990. Foi a queda do muro de Berlim que decretou o fim dessa tecnologia na Europa.

quarta-feira, 19 de maio de 2010

Inflação operacional

Meu micro estava há um bom tempo teimando em não desligar completamente. Ele até desligava os discos, mas continuava com a ventilação funcionando. Como última tentativa, resolvi atualizar a BIOS. Funcionou, mas um detalhe importante apareceu.

A imagem da BIOS tem 512KB. Isso é exatamente o tamanho da ROM que continha o sistema operacional RISC OS do Archimedes. Este era um sistema operacional multi-tarefa com interface gráfica, conforme ilustra a figura abaixo.


Então, o que há 20 anos seria o suficiente para um sistema operacional bastante avançado, hoje mal serve para ligar e deligar a máquina.

terça-feira, 18 de maio de 2010

Formatação eficiente no Java

Uma das maiores fontes de erros e ineficiência que costumo encontrar em sistemas Web escritos em Java é o mau uso das classes de formatação da package java.text.

A documentação avisa que as classes não podem ser usadas concorrentemente. Mas quem lê a documentação? Outro problema é a instanciação excessiva. Tenho a impressão de que ela não ocorre por precaução, mas por indiferença.

Em sistemas Web, principalmente os de alto tráfego, alguns detalhes podem fazer muita diferença. Se instanciar um objeto não custa muito, removê-lo é muito demorado. Num teste simples, descobri que reutilizar uma instância é quatro vezes mais rápido que criar uma nova. E uma instância reutilizada não precisa ser recolhida pelo coletor de lixo.

A solução está na classe ThreadLocal do pacote java.lang. Nem é preciso importar a package! Para a formatação, costumo criar uma classe utilitária da seguinte forma:

import java.text.SimpleDateFormat;
import java.util.Date;

public class Formato {

private static final ThreadLocal formatoData =
new ThreadLocal() {
@Override
protected SimpleDateFormat initialValue() {
SimpleDateFormat df = new SimpleDateFormat("dd/MM/yyyy");
return df;
}
};

public static SimpleDateFormat getFormatoData() {
return formatoData.get();
}

public static Date data(String value) {
return getFormatoData().parse(value);
}

public static String data(Date value) {
return getFormatoData().format(value);
}

}

Uso nomes bem concisos para os métodos para tornar o código mais simples. O significado fica bastante claro pelo uso:

String hoje=Formato.data(new Date());

Assim, fica garantido que para cada linha de execução haverá apenas uma instância para cada formatação. E todas as operações são feitas usando essa mesma instância. Os servidores de aplicação costumam reaproveitar as threads e então, uma vez criado, cada objeto terá uma longa vida. Além disso, não tem sentido ter muitas linhas de execução por processador. Tipicamente, usam-se 4 ou 8. Se houver mais que isso, o processador vai ficar mais tempo trocando de contexto que fazendo algo útil.

Para executar outras transformações, basta adicionar subclasses de ThreadLocal e os respectivos métodos, conforme o exemplo. Será necessária uma instância para cada tipo de conversão.