Avaliação do Visteon VSB-7705

O Visteon VSB-7705 é um tocador MP3 para carro, que permite a reprodução de CDs, cartões SD-MMC e dispositivos USB.

Aviso

Estou muito longe de ser um aficionado por "som automotivo". Para mim automóvel é um dos piores ambientes para querer se apreciar música, com grandes limitações acústicas, ruído externo constante e a necessidade de prestar atenção na direção e não na música. Confesso ainda que só fui colocar o "som" no carro um anos após a compra.

Um Breve Histórico

No meu carro anterior eu usava um toca-fitas (!). O ponto positivo do meu aparelho antigo é ter uma entrada auxiliar na frente, o que me permitia ligar um reprodutor de CD portátil, com suporte para MP3. Era esta configuração que usava, o MP3 praticamente eliminava a necessidade de trocar de CD durante uma viajem e as falhas de reprodução devido aos onipresentes buracos das ruas e estradas brasileiras.

Infelizmente o aparelho pifou e portanto eu precisava comprar outro para o carro novo.

O Atrativo do VSB-7705

O que me atraiu para o VSB-7705 foi o suporte a cartão SD, uma vez que já uso este tipo de cartão na máquina fotográfica e já tenho um leitor conectado ao meu micro. O formato SD coloca em um pequeno espaço capacidades bem razoáveis por preços idem.

No VSB-7705 o cartão SD fica completamente embutido durante o uso, não ficando nenhuma saliência para fora que possa levar um tranco acidental danificando o cartão e/ou o aparelho. Além disso, o cartão cabe facilmente no estojo da frente destacável.

A Instalação

O meu carro é um Citroen C3 e a instalação foi moleza. Os conectores do carro e do aparelho eram totalmente compatíveis, dispensando gambiarras. Um ponto a mais para o VSB-7705 e que ele já vem com um adaptador para antena e com conectores com fios para facilitar a intalação em veículos com conectores diferentes (ou sem conectores).

Outro ponto de destaque é que o manual apresenta indicações claras e completas dos sinais presentes nos conectores.

O VSB-7705 não foi o primeiro aparelho com SD que eu encontrei, mas li vários comentários de usuários da outra marca reclamando de chiados. No meu caso a qualidade de som me pareceu excelente. O único "defeito" é uma ligeira pausa (1 segundo ou menos) entre uma música e outra (em MP3), o que pode atrapalhar fãs do rock progressivo onde é comum uma faixa continuar direto na seguinte.

Os Recursos

O VSB-7705 tem uma grande quantidade de recursos, mas devo admitir que usei poucos deles até agora.

Como é mais ou menos padrão, a frente é destacável e basculhante. O encaixe não me inspira muita confiança, mas até agora não tive problemas. O display alfanumérico apresenta uma boa quantidade de informações dos arquivos MP3 e tem boa legibilidade. O display tem ainda indicação gráfica do volume. A frente tem também uma quantidade absurda de botões, cada um com um LED decorativo.

Segundo o manual, são suportados formatos MP3, WMA e OGG, os dois primeiros com várias taxas de transferência e frequência de amostragem. Não são suportados arquivo protegidos (DRM). Até agora usei somente MP3 e ele tocou tudo sem problemas.

A conexão direta de um pen-drive na entrada USB não é muito prática, pois o pen-drive fica totalmente exposto para fora. Felizmente o aparelho vem com um cabo adaptador.

O aparelho suporta CD / CD-R e CD-RW, tanto com audio como com arquivos MP3, WMA e OGG.

Para SD e USB existem funções de gerenciamento de arquivo para procurar e apagar arquivo.
Um recurso curioso é a gravação em SD ou pen-drive a partir do rádio, CD ou da entrada auxiliar (que requer um cabo adicional não fornecido).

Tem, é claro rádio AM/FM. As poucas vezes que escutei rádio (FM) o som me pareceu perfeito. Por enquanto ainda nem me dei ao trabalho de colocar as estações que gosto nas memórias.

Para completar, vem um controle remoto IR, o que me parece um acessório meio inútil.

Concluindo

Estou totalmente satisfeito com o VSB-7705. O cartão SD me parece ser a midia perfeita para quem quer ter um som solid-state no carro. O aparelho tem um preço razoável e pode ser encontrado em 12 vezes no cartão nas "boas casas do ramo".

Atualização 28/02/10

Parece que a minha sorte acabou, o display começou a piscar.

Atualização 30/11/10

Acho que agora ele se foi. Há cerca de um mês começou a falhar um dos canais, achei que era mau contato mas estou desconfiando do aparelho. Semana passada o painel parou de funcionar, ao colocar ligava sozinho com o último ajuste. Um reset fez somente perder o último ajuste. Colocando um SD o painel funciona, porém após alguns minutos desliga e religa sozinho. Já encomendei um novo aparelho (de outra marca, é claro).

Links diversos

Normalmente não gosto de fazer post somente com links, mas a escrita dos posts mais "sérios" está indo muito devagar e tropecei com alguns links que podem interessar aos leitores.

Assistindo vídeos do YouTube Off-Line
Existem algumas dezenas de opções para isto, no momento estou usando http://www.techcrunch.com/get-youtube-movie/ para baixar em formato FLV, que pode ser tocado pelo VideoLan.

Aulas de Violão e Guitarra
Um uso para os links acima é para baixar os vídeos de justinguitar. Um adicional é que a pronúncia british dele é muito boa, o que pode ser um apoio para quem está aprendendo inglês.

Para os fãs do Open Office
Um lembrete que nem tudo é perfeito: a longa história de um desenvolvedor que criou um add-on para o Calc e o descaso da Sun, que culminou por decidir re-desenvolver o módulo internamente para ficar com os direitos (é, software livre também tem direitos autorais).

Para quem quer dar risadas
Um lista dos oito artigos mais inúteis na Wikipedia e seis perguntas que o último volume do Harry Potter tem que responder (e que de foram respondidas, embora a quinta de forma muito oblíqua). Aviso: não adequado para crianças inocentes!

E por falar em crianças inocentes..
Não é só no Brasil que algumas pessoas estão bravas com a Google a respeito da dificuldade em tirar material impróprio do Orkut.

13a Competição Anual de Ficção Interativa

Aviso aos fãs de aventuras: já estão disponíveis para download os jogos da 13a Competição Anual de Ficção Interativa. São mais de duas dúzias de jogos. Lembrar somente que são jogos curtos e em grande parte escritos por amadores.

Ajude a divulgar a lista brasileira de equipamentos e serviços compatíveis com Linux

...e concorra a MP4 e MP3 players, mochilas Targus, períodos de VoIP grátis e até a ventiladores USB - além de contribuir automaticamente para doações para a Wikipedia e o Wordpress! O BR-Linux coletou mais de 12.000 registros de compatibilidade de equipamentos e serviços (webcams, scanners, notebooks, ...) na sua Pesquisa Nacional de Compatibilidade 2007, e agora convida a comunidade a ajudar a divulgar o resultado. Veja as regras da promoção no BR-Linux e ajude a divulgar - quanto mais divulgação, maior será a doação do BR-Linux à Wikipedia e ao Wordpress.


A idéia inicial era colocar junto deste post o resultado de um teste simples de impressão com a Samsung SCX-4200, mas não deu certo na primeira tentativa (tentei imprimir bootando um Live-CD do Ubuntu) e o prazo da promoção está acabando. Fica a promessa de investigar melhor como usar a impressora (e o scanner) da SCX-4200 e depois postar o que descobrir.

Será que o Excel 2007 Desaprendeu a Aritmética?

Esta semana foi descoberto um problema vexatório no Excel 2007, que apresenta um resultado completamente errado para uma conta simples. Esta descoberta tem gerado manchetes do tipo "Excel 2007 não sabe multiplicar", mas o que realmente se passa?

O Bug

O exemplo mais comum do problema consiste em entrar em um célula com a expressão "=77,1*850" (quem estiver com o Windows configurado para o padrão americano deve entrar com '.' no lugar da ','). O resultado apresentado é 100.000 ao invés do valor correto 65.535.

Como Isto Ocorre?

Da mesma forma que a maioria das planilhas e aplicativos que manipulam números, o Excel trabalha internamente com os números em um formato padronizado, o IEEE 754. Este formato é o mais comumente usado e é suportado diretamente pelos processadores atualmente em uso nos PCs.

Este formato é do tipo ponto flutuante, no qual o número é armazenado em duas partes: a mantissa (que é o número em si) e o expoente (que indica onde está a separação entre a parte inteira e fracionária). Uma das vantagens deste formato é suportar uma faixa grande de números em uma capacidade baixa de armazenamento. Por exemplo, vamos supor que vamos armazenar números decimais em três dígitos. Se usarmos um ponto fixo após o primeiro dígito, podemos trabalhar com números entre 0,00 e 9,99. Se considerarmos os dois primeiros dígitos são a mantissa e o terceiro é o expoente, podemos trabalhar com números entre 0,00 e 990.000.000. Uma desvantagem óbvia é que quando somamos números muito diferentes perdemos precisão.

Um outro ponto importante é que neste tipo de notação podemos armazenar somente um subconjunto dos números reais. No meu exemplo podemos armazenar 0,01 e 0,02 mas nenhum dos infinitos números entre eles.

Para complicar o entendimento, na notação IEEE 754 trabalhamos com potências de 2 e portanto temos um 'ponto binário' ao invés de 'ponto decimal'. Como consequência números 'triviais' na notação decimal não podem ser representados na notação binária e vice versa.

O que tem isto a ver com o bug? A primeira coisa é que 77,1 não possui representação exata no formato IEEE 754. Ao multiplicar este valor por 850 obtemos um valor que não é exatamente igual a 65.535 (mas extremamente próximo).

Ao contrário do indicado pelas manchetes, o Excel faz a conta direitinho (quem faz a conta é a CPU não o Excel). Aonde ele 'se borra' é na hora de apresentar o resultado na tela. Ou seja, ao converter a representação binária do resultado para caracteres.

É Grave?

Segundo a Microsoft, o erro na apresentação ocorre somente para 12 combinações das quase 10^19 possíveis. É claro que as operações que levam a estas combinações são também quase infinitas e independem dos números e operações envolvidos. Considerando o tempo que o Excel está no mercado, dá para ver como os casos reais são raros.

Como o erro está na apresentação e não no cálculo, se o valor for usado em outros cálculos o resultado final provavelmente vai ser apresentado corretamente. Quando a Microsoft liberar uma correção, bastará carregar a planilha para o resultado correto ser apresentado, não existe nada a corrigir na planilha em si.

Portanto o problema é mais grave para a imagem da Microsoft que para os seus clientes.

Mas Como Saiu Com Este Bug?

A pergunta chave é: como testar para pegar um bug destes?

Uma vez que o erro está na apresentação, testes automatizados que verifiquem o resultado em si e não o valor apresentado na tela não vão pegar o erro.

O lugar mais provável seria no teste unitário da rotina que converte o número da representação interna para o string apresentado. Considerando a quantidade quase infinita de casos a testar e o minúsculo número de casos problemáticos, fica fácil perceber que é difícil um teste não dirigido pegar este problema. As informações disponíveis são insuficientes para saber se o problema acontece em algum caso limite, por exemplo onde o algorítimo precisa escolher entre dois caminhos ou onde alguma variável pode sofrer overflow ou underflow. Em caso afirmativo, provavelmente faltou um caso de teste que verificasse o funcionamente correto nos dois lados do limite.

Referências

Fiquei sabendo do problema no Joel On Software. Joel que, não por acaso, foi gerente de projeto do Excel (no milênio passado).

A descrição do problema pelos projetistas do Excel pode ser vista aqui.

PC Assembler: A Odisséia

Como comentei no post anterior, ao escrever o post sobre a minha nova impressora eu tive a idéia de postar o texto do livro PC Assembler. Parecia fácil, mas foi uma verdadeira odisséia!

Procurando a Midia

Eu estava certo de ter uma cópia no HD. Não achei. Bem, com certeza está um dos muitos CDs de backup. Também não. Nos disquetes? Nada.

Hora de enfrentar o pó da última gaveta do armário de roupas, onde escondi algumas lembranças para escapar do lixo. E achei o disco aí ao lado. Alguns vão reconhecer que é um disquete de 5 1/4", mas poucos vão perceber que tem o corte de desproteção contra gravação nos dois lados. Para quem não entende de arqueologia, este é um disquete de Apple ][.

Parenteses: o mundo em geral pode idolatrar o Steve Jobs mas para os engenheiros Steve Wozniac é o cara. Uma das suas maiores criações foi a interface de disco do Apple ][, que permitiu a comercialização da unidade de disco por um preço extremamente baixo para a época (mesmo com a margem imensa colocada pelo Jobs). Embora a unidade seja para disquetes de face simples, o fato dela não usar o furo de índice (o furo pequeno redondo à direita do centro), permitia usar o segundo lado fazendo o corte na lateral e colocando o disco de ponta cabeça.

O Micro

Na época que eu escrevi o livro, meu computador principal era um Unitron apII TI. Alguns anos depois, evoluí para um TK3000//e da Microdigital que corresponde ao Apple //e. Foi este segundo equipamento que fui buscar na casa do meu pai para ler o disquete. Na foto ao lado, ele já foi devidamente limpo (?).

Uma das várias idéias que o Apple ][ popularizou (e a IBM seguiu) foi o uso de slots para placas de expansão. Como pode ser visto na foto ao lado, o meu micro tem uma quantidade grande de placas.

Separada das demais, na esquerda, está a placa "80 colunas" (o default do Apple ][ é apresentar na tela 40 caracteres por linha). No slot 1 a interface para impressora paralela. No slot 4 um clone do Softcard Z80, um dos primeiros hardwares de sucesso da Microsoft (essencial pois o disco está em formato CPM/80). No slot 6 a mencionada interface de disco, Por último, no slot 7, a minha expansão de memória de 128 KBytes (uma extravagância, que eu usava como RamDisk).

Para completar, o meu primeiro monitor: uma TV muito mal adaptada (fiz a adaptação de forma provisória quando cheguei em casa com o Unitron, funcionou e ficou deste jeito até hoje). No lado direito, duas unidades de disco.

Hora de cruzar os dedos, colocar um disco de CP/M e ver o que acontece. Ao lado está o resultado, aquele "A>" lembra alguma coisa? Exceto por um monte de maus contatos (principalmente no teclado), está tudo funcionando!

Obs.: Para o caso de alguém estar prestando a atenção, a tela está com 40 colunas, devido a um mau-contato na placa "80 colunas". Neste momento a placa Z80 estava no slot 3 (esquecimento meu). Quando a placa "80 colunas" passou a funcionar a Z80 parou. Perdi pelo menos uma hora, até lembrar que a placa Z80 devia ir no slot 4 para não conflitar com a "80 colunas".

Recuperando os Dados

Ok, eu consigo ler os disquetes antigos, e agora? É hora de transferir os dados pela serial. A placa ao lado é uma ICA (Interface de Comunicação Assíncrona), lembrança dos tempos da Humana Informática e dos posts nas BBSs, comunicando a 300 bps ou nos esquisitos 1200/75 bps.

Com a placa no slot 2, é hora de usar o meu programa de comunicação (reparar no copyright na tela ao lado). O programa trabalha no capenga Xmodem Checksum, o que exige um pouco de esforço do Hyperterminal (que insiste em tentar primeiro o Xmodem CRC e só passa para o Checksum depois de um l_o_n_g_o tempo). Após alguns arquivos a paciência acabou e preferí alterar um dos meus inúmeros utilitários de PC para suportar o Xmodem Checksum.

Mas, Espere: Isto Não É Tudo!

Ao final tenho 20 arquivo recebidos no PC (como no CP/M são apenas 56K de Ram, o texto era quebrada em pedaços de no máximo 20K para evitar que o editor ficasse acessando o disco o tempo todo). A tela ao lado mostra (em hexa) o início de um deles (clique para ampliar). Que codificação é essa? Os textos foram gerados com o WordStar, que era um editor WYSIWYG... se você está escrevendo em inglês numa impressora não gráfica. À medida que o texto é editado, o WordStar automaticamente distribui espaços para justificar o texto dentro das margens. Para isto ele usa o bit 7 dos caracteres para marcar o final das palavras e os espaços, hifens e quebras de linha introduzidos. O que realmente estraga tudo é que para gerar as acentuações eu digitava sequências "caracter backspace acento" (felizmente tanto o Unitron como o TK3000 tinham teclados programáveis, o que me permitia digitar estas sequências de uma forma mais automática).

Reparar também no ".he xxxx". A formatação para impressora era um passo separado, as linhas começando com '.' são comandos para definir cabeçalho, rodapé, pular página, etc. Para conseguir obter um TXT com o conteúdo foi preciso fazer um programa para limpar tudo isto.

Lembrando, o resultado final pode ser baixado daqui.

01/08/13: O texto, em formato de eBook pode ser baixado  do SkyDrive através do ícone no alto à direita ("Arquivos do Blog") ou pelos ícones abaixo:

PC Assember Volume I

Ao escrever o post sobre a minha nova impressora, me veio à lembrança o motivo para a compra da minha primeira impressora: eu estava escrevendo um livro.

Um Breve Histórico

Nos idos de 1985, eu era um alegre proprietário de um TK-82C. Em um encontro de usuários, conheci o Nelson Santos que trabalhava como editor na Editora Campus. A idéia inicial, o livro "Jogos em Linguagem de Máquina para a Linha Sinclair" não foi em frente e o Nelson perguntou se eu tinha alguma idéia para um outro livro. Mencionei que estava trabalhando com o PC IBM e que talvez existisse interesse em um livro sovre programação assembly para ele. Assim nasceu o livro PC Assembler, que deu origem a mais outros três livros ("Usando o BIOS", "Usando o DOS" e "Gráficos e Sons").

O Conteúdo

O livro descreve a programação em Assembly no 8086/8088 (naquilo que hoje em dia se chama de "real mode 16 bits"). A maior parte é uma descrição detalhada de cada uma das instruções disponíveis.

As Vendas

No total foram impressos 6253 livros e vendidos 6066 exemplares, em quatro edições. o gráfico abaixo mostra a evolução das vendas semetrais, do segundo semestre de 86 até o primeiro semestre de 93, quando a Editora Campus decidiu não mais reeditar a obra e me devolveu os direitos de publicação.


Para minha total surpresa, o livro foi até considerado um "best-seller":


O Texto

Existe uma longa história sobre a recuperação deste texto, o que será assunto do próximo post.

Estou disponibilizando o texto do livro aqui. Aviso que (por enquanto?) está em formato texto (TXT) pré formatado e falta a listagem do programa exemplo.

30/06/2010: Finalmente o texto completo e devidamente formatado está no blog: veja aqui.

Lista: Onze Utilitários "Free"

Segue um levantamento (incompleto) dos utilitários "free" que utilizo no meu dia-a-dia (no Windows). Alguns são "free as in free beer" (grátis) e outros são "free as in free speach" (livres). Alguns são manjados outros talvez não tanto. É provável que existam alternativas melhores, vários deles foram adotados mais por acaso do que por uma comparação sistemática. O único critério relevante é que podem ser usados gratuitamente.

• Mozilla Firefox: adotei quando a Microsoft tinha perdido o interesse no IE e os hackers do mal faziam a festa. Continua sendo meu navegador principal, embora ache que o IE7 tenha algumas vantagens (como na parte de impressão e uma nova aba sempre a um único click de distância). Nos add-ons uso o DownThemAll! (impressionante como o download default do Firefox e do IE são limitados) e o Html Validator (por enquanto mais como curiosidade, já que praticamente não desenvolvo para Web). Livre.
  
• NSIS: fazer um instalador só perde para escrever o manual na lista de tarefas ingratas do desenvolvedor típico. O NSIS é um gerador de instaladores muito esperto. Na sua forma bruta é mais voltado para quem gosta de escrever scripts que para a turma do "arrasta e clica" (ou pior ainda, "next, next, finish"). Está na lista uma série de posts sobre ele. Livre.
  
• Sonique: já não lembro mais porque comecei a usar este media player, mas ele está sempre lá na área de notificação (vulgo "system tray"). Eu cheguei até a fazer um plugin de visualização (inútil pois sempre deixo ele minimizado). De qualquer forma, um media player é uma ferramente indispensável para a maioria dos programadores, garantindo uma barreira sonora contra as interrupções externas. Grátis e abandonado.
  
• ToDoList: o maior gerador de tráfego no feed do CodeProject, com versões novas a todo instante. Eu só criei coragem para testar após a propaganda do Caloni. Ainda estou me acostumando, minha tradição era fazer a lista em papel para ter o gostinho de riscar as tarefas concluídas. Livre.
  
• WinMerge: outra ferramenta básica do desenvolvedor é um comparador de arquivos. Livre.
• Frhed: todo programador baixo nível gosta de editar arquivos binário e este é um muito bom. Livre.
• BareTail: uma das coisas mais úteis para depuração no *nix é p "tail -f". Para quem não conhece, o tail é um utilitário que mostra as últimas linhas de um arquivo. A opção -f faz com que sejam mostradas as últimas linhas à medida em que elas são acrescentadas no final. Perfeito para ver log de coisas ocorrendo em "tempo real". O BareTail é excelente, exceto pelo splash screen na versão grátis. Está na lista tentar fazer um utilitário destes. Grátis.
• SciTE: a ferramenta mais básica de todas: um editor de programas. A internet está cheia de opções e este realmente foi escolhido ao acaso. E depois que você acostuma com um editor, resiste a mudar. Livre.
• DOSBox: embora mais voltado para jogos antigos, uso também este emulador de DOS para rodar um compilador arcáico que se não gosta do XP. Livre.
• Doxygen: o lugar da documentação do código fonte é no fonte! A partir de comentários formatados de forma não muito especial, o Doxygen gera a documentação em formato HTML, CHM e PDF. Livre.
• PDF995: um driver de impressora que gera arquivos PDF. Os anúncios da versão grátis são chatos, mas acho a qualidade do PDF melhor que a gerada pelo OpenOffice (que não coloquei na lista pois uso raramente)
  

Sintam-se à vontade para explicar nos comentários como este programas são muito piores que outros que eu nem conheço!

Livro de Agosto: State of Fear

Michael Crichton é o conhecido autor de Jurassic Park e um dos criadores da serie ER. Dentre os seus livros, apreciei muito The Andromeda Strain, Jurassic Park, Rising Sun e Airframe. Outros livros não me agradaram tanto: The Terminal Man, Congo, Sphere, Disclosure, Timeline e Prey.

No caso de State of Fear, fiquei com o pé atrás pelas críticas não muito boas e pela fama de ser um livro que nega o aquecimento global. Talvez por isto o livro tenha parado nas pechinchas da Amazon, por um terço do preço de capa. Isto me animou a comprar e tentar deixar de lado o preconceito inicial.

O Livro

O livro é um techno thriler muito bom, daqueles que prende o leitor. Embora um personagem fique frequentemente pregando as teorias do autor, isto não chega a comprometer o rítmo. Tem algumas cenas de ação exageramente forçadas e um trecho um pouco chocante envolvendo antropofagia, mas os filmes de ação da sessão da tarde tem coisa pior.

Como um bonus, as menções a computador não são do tipo que reviram o estômago de quem trabalha com tecnologia.

A posição de Michael Crichton quanto ao Aquecimento Global

O livro possui no final uma Mensagem do Autor, onde ele lista a suas posições. Quem preferir pode ver uma entrevista recente, onde ele reforça os mesmos pontos, que resumo abaixo:

• as temperatura médias subiram no último século.
• é discutível quais as causas deste aquecimento e quanto se deve à ação do homem e especificamente à emissão de dióxido de carbônio. A opinião pessoal de Michael Crichton é que o dióxido de carbônio é um fator menor.
• previsões de aquecimento futuro são baseadas em modelos computacionais. Michael Crichton considera que isto vale pouco mais que um chute e oferece o seu: 0,812436 C nos próximos cem anos.
• previsões de catástrofes estão sendo usadas para justificar gastos imensos em programas urgentes.
• ele está certo que existe certeza demais no mundo.
• todos tem uma agenda. Exceto ele.

Para reforçar tudo isto, existem inúmeras notas de rodapé e várias páginas de referência.

Dois sites (encontrados meio ao acaso) para ver algumas reações a esta posição:

• Real Climate
• ~C4Chaos
  

O Veridito

State of Fear é um bom livro como diversão. Pode-se (e deve-se) questionar as posições do autor. Por outro lado, é preocupante a facilidade com que as pessoas desprezam o livro e a posição do autor simplesmente por serem contra o "senso comum".

Algorítmos de Ordenação - parte VIII

Para fechar a série de posts, um exemplo um pouco mais completo.

O programa Ordena é um utilitário de ordenação, comandado pela linha de comando (o que é bem apropriado, visto que a operação de ordenação é algo inerentemente "batch" e não interativa). Como características importantes, destaco:

• Escrito em C ANSI para maior portabilidade (testei no Windows com o Visual C 6 e no GCC 3.2. sob Linux).
• Ordenação de arquivos texto, com chaves alfanuméricas: o programa ordena linhas finalizadas por CR LF (LF no Linux). Para reduzir a movimentação na memória, ordena os registros indiretamente através de um vetor de ponteiros.
• Suporte a múltiplas chaves: como comentei na introdução, basta comparar as chaves uma a uma até achar a primeira que tenha diferença.
• Ordena arquivos maiores que a memória: o arquivo é ordenado em blocos, que depois são combinados (merge). O tamanho do bloco pode ser definido na linha de comando (útil para exercitar esta parte do programa).
• Suporta os algorítmos BubbleSort, HeapSort, QuickSort e ShellSort.

Os fontes estão comentados de forma compatível com o Doxygen, o que permite gerar documentação em formatos HTML e CHM.

O programa pode ser baixo daqui.

Algoritmos de Ordenação - Atualização

Como comentei na introdução, escrevi os artigos e o primeiro programa de demonstração dos algorítmos de ordenação há muito tempo atrás. No caso do programa eu apenas dei uma acertada nos comentários antes de publicar.

Ao fazer o segundo programa de demonstração, tive a desagradável surpresa de encontrar dois bugs:

• no Bubble Sort, em um ponto eu me confundi quanto ao índice inicial dos dados a ordenar.
• no QuickSort, o algorítmo (adaptado do Knuth) assumia que valores especiais eram colocados antes e depois dos dados para "segurar" os índices nas pontas. E eu não coloco estes valores.

A versão revisada está aqui.

Desenvolvendo Software para Sistemas Embarcados

Um dos motivos dos posts estarem ficando espaçados são alguns problemas que tenho enfrentado no desenvolvimento de software para um par de sistemas embarcados. São dispositivos baseados em micro-controladores e além, das dificuldades normais de software, existe sempre a possibilidade de um problema no hardware (no projeto ou na montagem).

Embora não possa entrar nos detalhes (para não comprometer a confidencialidade do meu cliente), existem alguns pontos que dá para compartilhar com a minha dupla de leitores habituais.

Circuito de Baixo Consumo

Os dispositivos para os quais estou escrevendo software são alimentados a bateria não recarregável e o consumo precisa ser bastante baixo para garantir uma duração de meses a anos.

São necessários vários cuidados para reduzir o consumo. Por exemplo, é comum a presença nos circuitos de vários resistores ligados entre um pino do micro-controlador e terra ou a alimentação (como os famosos pull-down e pull-up para garantir o nível do sinal quando ninguém mais está colocando um sinal no circuito), estes resistores precisam ter valor elevado e, sempre que possível, o micro-controlador deve colocar no pino o mesmo sinal que na outra ponta do resistor.

Os micro-controladores costumam possuir diversos modos de operação, permitindo desligar parte do circuito interno para economizar bateria. No caso do micro-controlador usado em um dos dispositivos, o modo mais econômico desliga tudo exceto a memória. Para chegar à autonomia de anos é preciso manter o micro-controlador dormindo a maior parte do tempo. Se, por exemplo, em cada segundo executar por 5 ms com consumo de 10 mA e ficar dormindo o resto do tempo com consumo de 1 uA (microAmpere), uma bateria alcalina de 1000mAh vai durar mais de 2 anos.

O único jeito de acordar este micro-controlador é gerando um sinal de reset através de um circuito externo (no caso um timer de baixíssimo consumo e alguns sensores). Desta forma o reset passa a ser parte normal da operação, o que torna o software um pouco estranho. Como conseqüência, é preciso distinguir o reset de acordar do reset real (o power-on). Como a memória Ram é mantida mesmo com o processador parado, isto não é muito complicado.

O problema é como forçar um power-on. Como o consumo do micro-controlador dormindo é baixíssimo, a energia contida nos capacitores do circuito é suficiente para manter a Ram por muito tempo. A simples conexão da minha serial de debug consegue manter o circuito funcionando.

Pinos em Aberto

Falando em resistores de pull-up e pull-down, tive um par de problemas sérios num outro projeto onde alguns destes resistores foram esquecidos na montagem.

Neste caso o nível destes pinos fica indefinido. Pior ainda, ele acaba sendo influênciado pelos sinais próximos. Em um dos casos era um teclado em matriz, onde você coloca um sinal nas linhas, lê o resultado nas colunas e descobre quais teclas estão apertadas. Uma das colunas estava sem o resistor e a leitura quando não tinha tecla apertada acabava dependendo do que estava sendo colocado nas linhas. Sem entender direito o que estava acontecendo, eu acabei alterando a minha rotina de varredura até achar uma forma na qual (por acaso) eu conseguia ler sempre o valor correto na coluna.

Depurando Sem Serial

No segundo dispositivo é usado um micro-controlador muito simples e de baixo custo. Tão simples, que nem UART tem. Para fazer comunicação serial, é preciso ficar subindo e descendo por software o sinal de um pino para cada bit (com o timing correto). Para complicar, a memória de programação lotou rapidamente. O micro-controlador tem capacidade de depuração in-circuit, porém o código gerado para debug era grande demais. O que sobrou para debug foi um led e um pino livre do processador.

A minha principal ferramenta de debug foi um osciloscópio. O modelo disponibilizado pelo cliente não possui tela, ele é usado conectado a um PC, o que permite gravar imagens das formas de onda. No início foi meio estranho, mas este tipo de depuração tem a vantagem de permitir ver graficamente o andamento do software ao longo do tempo. Como o osciloscópio tem dois canais, dá para ver a relação entre acontecimentos assíncronos. E é claro que dá para medir com precisão o tempo entre eventos.

Existe mais entre o VCC e o Terra que se possa imaginar

Quando estamos programando em baixo nível, pensamos muito em binário: é 0 ou 1. No hardware, entretanto, existe muita coisa entre o 0 e 1 (e às vezes até fora dele).

Um dos bugs mais complicados foi a perda esporádica da Ram no reset, no dispositivo onde isto não devia ocorrer. Esporádica quer dizer: às vezes ocorre seguidamente em um minuto e em outras fica horas sem ocorrer. Perda quer dizer que algum bit na Ram virava.

Após vários dias penando, apelei para o osciloscópio e observei o sinal ao lado no reset. À primeira vista, parece normal, porém a curva de subida me pareceu muito longa. Conversando com o projetista do hardware descobri que um capacitor estava acidentalmente com valor errado (um erro de digitação); arrancando o infeliz o sinal passou a subir "instantaneamente" e o problema subiu.

Aparentemente a subida gradual do sinal ocasionalmente confundia o processador. Algo parecido com a execução paranormal de código.

Minha nova impressora: Samsung SCX-4200

Atualmente as impressoras são um periférico bastante comum, custando uma pequena parcela do preço de um microcomputador.

Nos anos 80, quando comprei os meus primeiros micros, a coisa não era bem asim. Minha primeira impressora, comprada nos meados dos anos 80, foi uma Grafix 80 F/T, uma impressora matricial copiada da Epson.

Não apenas cara, era lenta e barulhenta. Mesmo equipada posteriormente com "kit near letter quality" (uma troca de firmware para dar mais de uma passada em cada linha deslocando ligeiramente os pontos), a qualidade de impressão era bastante baixa. A acentuação era obtida imprimindo o acento por sobre a letra (uma vírgula no caso do c cedilha). Cheguei a fazer um programa para escrever texto usando o modo gráfico para obter uma qualidade melhor, porém era terrivelmente lento.

No final dos anos 80 começaram a surgir as impressoras laser, mas o custo estava fora do alcance das pessoas físicas (e até de empresas pequenas).

A grande virada foi o surgimento da impressora de jato de tinta. Minha segunda impressora foi um HP Deskjet 500 comprada em 93.

Embora ainda fosse cara e monocromática, fornecia qualidade e velocidade bem razoáveis. Rapidamente os antigos fabricantes de impressora passaram para o negócio de vender tinta e vender as impressora a preços extremamente baixos.

Minhas impressoras seguintes, Epson, foram brindes da assinatura de jornal.

Por outro lado, à medida em que o preço caia, caia também a durabilidade. Tanto a Grafix como a Deskjet 500 duraram cerca de 10 anos. Já as Epson ficaram longe da metade disso, apesar de muito menos usadas. As impressoras a jato de tinta atuais são também praticamente descartáveis, o preço de um conserto é de pelo menos metade do de uma impressora nova e o resultado não costuma ser bom.

Com a quebra das Epsons, foi hora de procurar uma nova opção. Cansado também do meu velho e lento scanner, resolvi dar uma olhada nas multifuncionais. Inicialmente estava pensando em uma jato de tinta da Epson, mas a Samsung SCX-4200 acabou me fascinando. Por um preço bem razoável (R$ 549, em 10x no cartão) deu para realizar o velho sonho de ter uma impressora laser. É claro que isto significa deixar de lado as cores.

O custo do tonner é outra preocupação. O preço de um original é maior que metade de impressora (genéricos e remanufaturados saem mais em conta). Por outro lado, o toner que vem na impressora deve durar 1000 páginas e um de reposição 3000 páginas, Pelo meu consumo atual de papel só vou precisar comprar tonner daqui a uns 2 anos, o que é mais ou menos o que dura uma jato de tinta.

Avaliação da Samsung SCX-4200

	A SCX-4200 é uma impressora multifuncional de tamanho médio e com aspecto tradicional, semelhante a uma fotocopiadora.
Uma vantagem em relação às impressoras de jato de tinta mais baratas é que o papel fica em uma gaveta. Além de ter uma boa capacidade (250 folhas), isto evita o papel ficar curvado e sujo.
	Como é costume nas multifuncionais, um painel permite o uso como copiadora independente do microcomputador

Apesar da pausa inicial para aquecimento (cerca de 30 segundos), a impressão é muito boa e rápida. Nas primeiras vezes é até estranho, pois a folha impressa não fica toda para fora da impressora, ficando a sensação de que a impressora ainda não terminou.

O scanner também é bem mais rápido que o meu antigo (que conectava na paralela e segurava o micro nos longos minutos para transferir a imagem).

Em resumo, estou (até o momento) muito satisfeito com este equipamento.

Algorítmos de Ordenação - parte VII

Vamos ver neste post o primeiro exemplo, que é um programa Windows para demonstração dos algorítmos.

A Interface Com o Operador

Para visualizar as chaves sendo ordenadas usei bolinhas coloridas que representam os números de 0 a 99. A cor varia conforme a chave do vermelho até o azul.

Um conjunto de radio buttons é usado para selecionar o algorítmo. Botões permitem embaralhar as chaves, executar a ordenação ao o final e executar a ordenação passo a passo. Outros dois botões permitem ver o diálogo Sobre e encerrar o programa.

Um listbox é usado para apresentar algumas mensagens de acompanhamento durante a ordenação.




O Código

Como originalmente eu pretendia enviar este programa para um site americano, os comentários e os nomes de variáveis e rotinas estavam em inglês. Refiz os comentários em português, mas mantive variáveis e rotinas com nomes em inglês, espero que isto não atrapalhe muito o entendimento.

A maior parte do código tem a ver com programação Windows. A tela do programa nada mais é que uma caixa de diálogo, com as chaves sendo desenhadas "na raça" (vide a rotina DrawKeys).

A decisão de permitir executar passo a passo complicou um pouco o programa. A rotina de ordenação é rodada em um thread separado do resto do programa. A cada passo a rotina de ordenação gera uma mensagem para avisar que concluiu o passo e aguarda a interface com o usuário (UI) sinalizar em um evento que a ordenação pode prosseguir. Isto foi aproveitado para segurar a execução (usando um timer do Windows), para dar um efeito visual melhor.

O conceito de passo não é muito rigoroso e varia bastante de um algorítmo para outro, portanto as velocidades de execução não são muito representativas.

As ordenações em si estão nas rotinas BubbleSort, ShellSort, HeapSort e QuickSort. Não foi feito esforço em otimizar o código; no caso do QuickSort é usado o elemento à esquerda como elemento de partição.

O projeto para o Microsoft VC 6, os fontes e o executável podem ser baixados daqui.

Na última parte vamos ver um programa de ordenação de arquivos, para execução por linha de comando sob Windows ou Linux. Isto é, supondo que eu ache tempo e consiga fazer. Até lá!

Blogando às cegas

Desde a semana passada não consigo acessar diretamente o blogspot do trabalho. Como pode ser visto no link abaixo, o problema é razoavelmente generalizado nos usuários Speedy:

http://www.googlediscovery.com/2007/08/04/blogspot-esta-fora-do-ar-para-usuarios-speedy/

Ao que tudo indica o problema ocorre para determinadas combinações de IP nas duas pontas (o IP do Speedy no trabalho é fixo e tenho problemas também com o site www.advantech.com que tem IP parecido com o blogspot). Usando um proxy anônimo (daqueles que esconde o seu IP), tudo funciona.

Vamos ver quanto tempo demora para o problema ser solucionado.

As Piores Desculpas na Informática

A lista abaixo é uma tradução/adaptação da que está aqui, o autor original é desconhecido.

• Aqui funciona!
• Não precisa se preocupar, pois ninguém nunca vai fazer isto...
• Os usuários gostam do jeito que está.
• Meu software não tem bugs!
• Isto vai ser corrigido na próxima versão.
• Vai estar pronto na segunda feira, falta só gerar o instalador.
• A internet comeu.
• Basta aumentar um pouco a Ram e o desempenho fica bom.
• Você não pode fazer isto por motivos de segurança.
• As consultas à base de dados estão lentas porque está normalizada demais.

Livros de Julho

Apesar da correria no trabalho, consegui ler dois livros em julho.

Harry Potter and The Deathly Hallows - J. K. Rowling

Graças à eficiência da Livraria Cultura, recebi o livro na manhã do dia 21 (dia mundial de lançamento). A conclusão da série do Harry Potter é um livro daqueles que você não consegue largar, concluí a leitura no próprio fim de semana (outro fator adicional era evitar ficar sabendo o final antecipadamente).

Ao contrário do livro final de A Series of Unfortunate Events, DH não deixa nada vago. É evidente o esforço da autora em esclarecer os místerios pendentes, quase todos os personagens que passaram nos outros livros ganham pelo menos uma menção ao longo do último volume. Como esperado, vários personagens morrem. Diversas teorias dos fãs se confirmaram e diversas outras não. Com tudo isto se chega a um final plenamente satisfatório. A crítica maior é sobre o depois do confronto final entre Harry e Voldemort, espero não estar entregando muito ao dizer que como muito fãs considero a autora exageradamente otimista. Mesmo assim, um livro imperdível.

Para quem ainda tiver dúvidas sobre o destino dos personagens após o último capítulo, a autora tem dado mais detalhes em entrevistas.

O livro (em inglês) pode ser encontrado facilmente em livrarias.

A For Andromeda - Fred Hoyle e John Elliot

Fred Hoyle foi um famoso astrônomo e autor do clássico The Black Cloud. Já comentei um outro livro dele, The Fifth Planet. A história deste livro foi escita em 1961 para uma série da BBC e tem vários elementos em comum The Black Cloud. Um rádio telescópio capta uma transmissão vinda de Andromedra, que se descobre ser o projeto de um computador e um programa para ser rodado nele. Construído o computador e executado o programa, ele se revela ser uma espécie de inteligência artificial.

Embora vários aspectos sejam anacrônicos (como a preocupação com a guerra fria), o livro é muito interessante e a idéia de se transmitir inteligência e vida através de sinais de rádio é no mínimo intrigante.

Infelizmente este livro está atualmente esgotado, a Amazon possui apenas exemplares oriundos de sebos.

Algorítmos de Ordenação - Parte VI

HeapSort

Este é o meu algorítmo preferido, apesar de ser pouco utilizado. O seu ponto chave é que tanto o tempo médio como o pior caso são proporcionais a N log(N).

Na prática, o tempo do HeapSort varia muito pouco com os dados sendo ordenados. Isto significa que se ele for rápido suficiente com um amostra de tamanho N, ele será rápido quaisquer que forem os dados de tamanho N que você jogar nele,

A idéia por trás do HeapSort é a mesma do torcedor do time eliminado num torneio "mata-mata". Olhando na figura abaixo, é claro que o time Amarelo é o campeão, mas quem é o segundo melhor? Não é preciso fazer um novo torneio completo, os candidatos são somente quem perdeu para o campeão (Marrom, Azul e Verde). O truque no HeapSort é usar uma estrutura de árvore para "lembrar" o resultado das comparações anteriores.

No HeapSort uma estrutura de árvore binária é obtida sem utilizar memória adicional guardando os dados de forma que

• o pai da chave no índice k está no índice k/2
• os filhos da chave no índice k estão nos índices 2*k e 2*k+1

Quando os filhos são sempre menores ou iguais aos pais, a estrutura é chamada de heap. A figura abaixo mostra um exemplo.

O HeapSort tem dois passos. No primeiro, transformamos os dados de entrada em um heap. Isto é feito partindo do topo e descendo a árvore movendo para cima os filhos que forem maiores que os seus pais. No final do primeiro passo, a primeira posição contém a maior chave. Entramos então no segundo passo, onde trocamos a primeira chave com a que está na última posição (colocando-a assim na sua posição final) e ajeitamos o heap para que a primeira posição contenha a maior chave das restantes. Este procedimento é repetido até que todas as chaves estejam na sua posição final.

O HeapSort não é particularmente rápido para N pequeno, mas para N grande é muito bom. O QuickSort é mais rápido na maioria das vezes, mas existe sempre o pior caso espreitando na esquina.

O HeapSort não requer memória adicional e não é estável.

Na próxima parte: o primeiro exemplo.

Algorítmos de Ordenação - Parte V

QuickSort - Ordenação por troca de partições

Este algorítmo foi inventado por C. A. R. Hoare em 1962 e é provavelmente o mais popular algorítmo de ordenação. Ele é rápido, mas também um pouco manhoso.

A idéia básica do algorítmo é selecionarmos uma das chaves (o elemento de partição) e re-arranjamos os dados para que as chaves à esquerda do elemento de partição sejam anteriores a ela (mas não necessariamente em ordem) e as chaves à direita sejam posteriores. Repetimos o processo para as duas partições e assim por diante, até que as partições tenham um único elemento; neste ponto todos os dados estão ordenados.

Por exemplo, vamos supor que nossas chaves são [6909 6508 6407 6412 6512] e escolhemos o 6508 como elemento de partição. Um possível particionamente é [6407 6412] 6508 [6909 6512].

Uma maneira simples de particionar N chaves K₁, K₂ ... K_n é selecionar a primeira delas como elemento de partição e percorrer as chaves a partir das duas pontas, trocando de lado os elementos quando necessário. Para isto usamos dois índices, um partindo da segunda chave (i) e o outro partindo da última (j). Avançamos i até acharmos uma chave maior que K₁ (que portando deve ir para a direita) e recuamos j até acharmos uma chave menor que K₁ (que deve ir para a esquerda). Neste ponto, temos duas chaves que estão em lados errados; nós as trocamos de lugar. Quando i alcançar j, trocamos de lugar K_j com K₁, encerrando a partição.

A figura abaixo mostra uma ordenação pelo QuickSort.

O QuickSort em ação

O QuickSort tem uma natureza recursiva: após o particionamento nós usamos o mesmo algorítmo para ordenar as duas partições. Existem várias razões para não codificar o QuickSort como uma rotina recursiva:

• Chamadas a rotinas tem um overhead alto: os parâmetros precisam ser colocados na pilha do processador, um novo stack frame precisa ser criado para os parâmetros locais, etc.
• Chamadas a rotinas podem consumir uma quantidade razoável de espaço na pilha; esta quantidade não está totalmente sob o nosso controle.
• Se a pilha ficar cheia, provavelmente não conseguiremos encerrar o programa de uma forma limpa.

O que devemos fazer é codificar o QuickSort de uma forma iterativa ao invés de recursiva, gerenciando nós mesmos a pilha. A questão chave é: qual o tamanho desta pilha? Na prática, esta pilha é bem pequena, desde que coloquemos nela primeiro a partição maior e depois a menor. Desta forma, na iteração seguinte começamos com a partição menor, que por sua vez gerará um número menor de subpartições. No pior caso, a cada vez as partições serão quebradas em duas subpartições de igual tamanho, portanto o tamanho da partição é dividido continuamente por dois (mais precisamente, o tamanho diminui um pouco mais, pois o elemento de partição não entra em nenhuma das duas subpartições). Portanto, com uma pilha com k elementos podemos ordenar 2^k chaves. Ou, olhando pelo outro lado, para ordenar N chaves precisamos de uma pilha com log₂(N) elementos. Por exemplo, para ordenar um milhão de chaves basta uma pilha com 20 elementos! Cada elemento na pilha contém apenas dois inteiros (os índices do início e fim da partição a ordenar), portanto não ocupam muito espaço.

O tempo médio do QuickSort é proporciona a N log(N). Infelizmente, o pior caso é proporcional a N². Não apenas isto, escolhendo o elemento de partição da forma que descrevemos, o pior caso é quando as chaves já estão ordenadas! Neste caso, cada passo reduz o tamanho da partição de apenas uma chave (já que todas as outras serão maiores que ela). Muitas sugestões foram dadas sobre como tornar o pior caso mais improvável. Basicamente, devemos escolher melhor o nosso elemento de partição. Algumas maneiras típicas são:

• escolher aleatoreamente
• escolher a mediana dos elementos no inicio, fim e meio da partição
• escolher a mediana de uma amostra das chaves

Todos estes aperfeiçoamentos aumentam o processamento, portanto o tempo médio irá aumentar. O pior caso continua sendo proporcional a N², porém será mais difícil ele acontecer na prática.

Outro aperfeiçoamento que pode ser feito no QuickSort (e em outros) é usar um algorítimo mais simples (como a inserção direta) quando o número de elementos na partição for menor que um limite. Como já vimos, algorítimos mais simples costumam ser mais rápidos para N pequenos.

O QuickSort não é estável.

Na próxima parte vamos examinar o meu algorítmo preferido. Em seguida, nas duas partes finais, vamos finalmente ver código!

Algorítmos de Ordenação - Parte IV

Neste post vamos ver um algorítmo de ordenação um pouco esquisito e menos conhecido.

Ordenação por Incrementos Decrescentes - Shell Sort

Este algorítmo foi inventado por Donald L. Shell, e se baseia na idéia de que podemos ordenar mais rápido se começarmos movendo as chaves distâncias maiores, para que eles cheguem mais rapidamente nas posições finais.

Para usar o Shell Sort, você precisa ter ou gerar uma lista de incrementos decrescentes, onde o último é um. Iniciamos a ordenação ordenando os elementos espaçados pelo primeiro (e maior) incremento. Em seguida, ordenamos os elementos espaçados do segundo incremente e assim por diante. No último passo ordenamos os elementos espaçados de 1, ou seja, todos os elementos. Nos primeiros passos estamos ordenando conjuntos com poucas chaves mas bem diferentes, no final estamos ordenando conjuntos com muitas chaves mas quase totalmente ordenadas. Por este motivo podemos usar a inserção direta para a ordenação de cada conjunto.

Confuso? Vamos a um exemplo, ordenando 8 números usando os incrementos 4, 2 e 1. Vamos ter portanto 3 passos: no primeiro ordenamos 4 conjuntos de 2 chaves, no segundo 2 conjuntos de 4 chaves e no último um único conjunto com as 8 chaves. A figura abaixo mostra os dados originais e o resultado de cada passo.

Exemplo de ordenação por Incrementos Descrescentes

A análise do desempenho deste algorítmo é muito complexa. A escolha dos incrementos é um ponto chave, mas não é simples determinar qual seria uma boa escolha. Knuth sugere como razoável a série 1, 4, 14, 40, 121, etc, na qual cada número é igual a três vezes o anterior mais um. A série deve parar dois números antes de ultrapassar o número de itens a ordenar. Por exemplo, para ordenar 100 itens usaríamos 1, 4 e 13. Usando estes tempos, o tempo médio é proporcionala N^1.25 e pior caso proporcional a N^1.5. Memória adicional pode ser necessária para guardar os incrementos (se os calcularmos antecipadamente), a série sugerida possui log₃(N) incrementos. O Shell Sort não é estável.

Na próxima parte desta série vamos ver o algoritmo mais conhecido de ordenação (pelo menos no nome) - o Quicksort.

06/08/07: Acertados os subscripts e superscripts.

Divagações sobre Efetividade, Eficiência e Eficácia

Este texto surgiu da promoção do blog Efetividade.net, que está premiando artigos para comemorar o seu primeiro ano de vida. Ao contrário de outros textos que estão participando, este meu artigo não traz dicas ou soluções, apenas muito questionamento.

O que é Efetividade?

Há muito tempo atrás, se ouvia que eficiência era fazer bem alguma coisa e eficácia era fazer bem a coisa certa. E a onde entra a efetividade? Uma rápida consulta à wikipedia me faz crer que a efetividade é atualmente usada como equivalente ao que eu conhecia como eficácia. A eficácia foi rebaixada a fazer a coisa certa enquanto que a eficiência continua relacionada a fazer bem (com bom aproveitamento dos recursos).

Por trás de toda estas palavras e definições está uma grande questão: determinar o que é A Coisa Certa. A necessidade destas múltiplas palavras se deve principalmente a termos situações frequentes em que alguém (ou algo) fez tudo certo (por uma definição) e o resultado foi errado. Ou vice-versa (compare a seleção brasileira na copa de 82 com o time do Dunga na Copa América).

Métricas é uma Solução?

Métricas são sempre apresentadas como uma solução, muitas vezes até como algo essencial. Embora eu acredite na necessidade e na utilidade de métricas, cada vez questiono mais a crença da métrica como solução.

Estou lendo (bem devegar, há muito tempo) um livro chamado "Measuring and Managing Performance in Organizations", de Robert D. Austin (indicação do Joel On Software). Resumindo a teoria apresentada, usamos métricas para incentivar pessoas a fazerem A Coisa Certa. Entretanto, as pessoas vão procurar otimizar as métricas (até o ponto em que isto não compense frente aos incentivos) e acabar por se distanciar dA Coisa Certa (o que o autor chama de Dysfunction). Se você remunera o vendedor pelo volume do faturamento, ele concede descontos demais; se você o remunera por margem, ele atende mal clientes importantes por outros motivos (volume, boa referência para o mercado, etc); se você cria a "formula perfeita", provavelmente ela é tão complicada que o vendedor não vai se dar ao trabalho de entender e vai fazer o que quiser enquanto estiver obtendo uma remuneração satisfatória.

O Curto, o Médio e o Longo Prazo

No início do curso de Engenharia, um professor disse que a essência da Engenharia era achar o compromisso correto. Isto vale para a maioria das coisas. É frequente termos que optar entre uma solução rápida e barata que resolve o problema agora, mas vai trazer problemas mais para frente, e uma solução mais complexa e cara que achamos que vai ser mais tranquila no futuro. Qual destas soluções é mais efetiva?

Uma situação do meu dia a dia é quando me pego fazendo algo repetitivo. Será que é melhor fazer um programa (ou script) para automatizar isto? Em alguns casos continuo até hoje fazendo coisas manualmente. Em outros eu investi algum tempo e fiz uma solução automática que me traz um sorriso nos lábios toda vez que uso. Porém existem casos em que perdi muito tempo fazendo um destes programas auxiliares que está encostado sem uso em algum canto do meu HD.

As Interrupções

É inegável que o meu rendimento (e a qualidade do trabalho) aumenta quando me concentro em uma única coisa. Por outro lado, isto aumenta o tempo de resposta para as outras, o que irrita quem está esperando por elas. Aliás, o simples fato de achar que os outros vão ficar irritados acaba me irritando.

O mundo atual quer o instantâneo. Você pede para a pessoa enviar solicitações por e-mail e a pessoa liga dali a 5 minutos para perguntar se você recebeu o e-mail. Se você não atende o telefone, ligam no celular ou ligam para quem está no lado. No final, será que ser interrompido constantemente é mais efetivo que tentar bloquear o mundo por algumas horas?

Um dos artigos interessantes concorrendo na promoção do Efetividade.net é o Frango Tosco. Um ponto que me preocupou: a preparação demora cerca de 75 minutos, dividida em 6 passos sinalizados pelo apito do microondas. Para mim isto não funcionaria, estas seis interrupções me deixariam louco (sem contar que eu provavelmente ia xeretar entre elas, só para me certificar que está tudo correto).

Concluindo

Como avisei no início, este artigo não traz soluções. Não tenho a resposta para as perguntas que fiz e nunca estou plenamente satisfeito com as opções que fiz. A única coisa positiva que posso dizer é que me sinto mais satisfeito questionando as opções do que seguindo cegamente uma lista de regras.

Algorítmos de Ordenação - Parte III

Estes primeiros algorítmos são bastante óbvios, embora não apresentem bom desempenho.

Straight Insertion Sort (Ordenação por Inserção Direta)

Este é um dos mais simples algorítmos de ordenação e funciona como um jogador de cartas organizando a sua mão. Durante a execução deste algorítmo, as primeiras chaves estão ordenadas (no início esta parte esta vazia, no final todas as chaves foram ordenadas). Pegamos a primeira chave ainda não ordenada e achamos o seu lugar nas já ordenadas e a inserimos aí. Repetimos isto até que todas as chaves estejam ordenadas (ver a Figura 1) Este algorítmo pode levar a muitas movimentações de chaves, principalmente se elas estiverem em ordem inversa no início. Ele é bastante simplas de codificar, não requer memória adicional e é estável. É evidente que os tempos médio e máximo são proporcionais a N².

Figura 1 - Ordenando por Straight Insertion

Bubble Sort (Ordenação por Bolhas)

A idéia aqui é semelhante à inserção direta, mas, ao invés de fazermos várias comparações e depois inserir a chave atual no lugar correto, trocamos imediatamente de lugar a chave atual com a anterior se descobrimos que uma deve vir antes da outra. Desta forma os valores menores sobem para o topo da lista, como bolhas na água (ver a Figura 2). Como o Straight Insertion, é muito simples, não requer memória adicional, é estável e os tempos médio e máximo são proporcionais a N².

Figura 2 - Ordenando com o Bubble Sort (passo final)

Na próxima parte vamos ver um algorítmo menos comum, o Shell Sort.

Algorítmos de Ordenação - Parte II

Como Comparar Algorítmos de Ordenação

Alguns critérios normalmente usados para comparar algorítmos de ordenação são:

• Velocidade de execução
• Necessidade de Memória Adicional
• Estabilidade

Velocidade de Execução

Este é normalmente o critério mais importante. Não se pode, entretanto, esquecer que a velocidade vai depender de vários fatores.

É intuitivo que quanto mais itens temos para ordenar, mais tempo vai demorar. A forma como o tempo aumenta com o aumento dos itens varia conforme o algorítmo.

Considere o sequinte algorítmo simples: examinamos os N itens, um a um, e separamos o primeiro; repetimos o processo para os N-1 intens restantes e assim por diante. A ordenação levará N+(N-1)+(N-2)+...+1 passos. Esta soma resulta em N²/2 passos, daí dizermos que este algorítmo leva um tempo proporcional a N² para ordenar N itens. Veremos nos próximos artigos que um bom algorítmo reduz isto para N*log(N) passos. Na maioria dos casos, quanto melhor o algorítmo, mais complexos serão os passos e portanto eles serão mais demorados. Mesmo assim, para um N grande log(N) é muito menor que N.

Por exemplo, vamos supor que temos um programa que demora N² microsegundos para ordenar N itens e outro que leva 100*N*log(N) microsegundos (em outras palavras, cada passo do segundo programa demora 100 vezes mais que cada passo do primeiro).

Para ordenar 10 itens, o primeiro algorítmo demora 100 microsegundos e o segundo 1000 microsegundos. Ordenando 100 itens, os tempos sobem para 10000 e 20000 microsegundos. Para 1000 itens, o primeiro levará 1000000 de microsegundos (mais de 16 minutos), enquanto que o segundo levará apenas 300000 (5 minutos).

Não é o caso do algorítmos simples apresentado acima, mas o tempo para os algorítmos mais sofisticados vai depender dos dados serem ordenados. Isto nos obriga a falar em tempo médio e em tempo do pior caso. Por exemplo, veremos que o Quicksort possui um tempo médio proporcional a N*log(N) e um tempo do pior caso proporcional a N². Isto significa, que o Quicksort é normalmente muito rápido, porém às vezes é muito lento!

A velocidade depende também das características do computador. A ordenação envolve principalmente comparar e mover chaves. Computadores diferentes podem levar tempos relativos diferentes para estas duas operações. Por exemplo, suponha que as chaves sejam valores em ponto flutuante. Pode existir uma grande diferença nas velocidades de comparação entre um computador com unidade de ponto flutuante e um computador que necessite fazer uma chamada de biblioteca. Neste segundo computador pode fazer sentido minimizar as comparações, mesmo que isto signifique mais movimentações. O resumo da história é que um algorítmo que funcione bem num computador pode não se dar tão bem em outro.

Necessidade de Memória Adicional

Alguns algorítmos são capazes de ordenar os dados nas posições em que eles estão armazenados, usando memória adicional apenas para trocar de posição duas chaves. Outros necessitam de memória adicional proporcional ao tamanho dos dados sendo ordenados. Os algorítmos descritos nesta série necesitam de nenhuma ou muito pouca memória adicional.

Estabilidade

Dizemos que um algorítmo é estável se ele manter chaves iguais na mesma ordem em que elas estão na entrada. Dizendo de outra maneira, se nós aplicarmos o algorítmo a dados já ordenados, a saída será idêntica à entrada. É sempre possível converter um algorítmo instável em um estável usando a posição original da chave como o último critério de ordenação. Por exemplo, se estamos usando ponteiros para ordenar as chaves, comparamos os ponteiros se as chaves são iguais.

No próximo artigo da série vamos ver os primeiros algorítmos de ordenação.

Algorítmos de Ordenação - Parte I

Nesta série vamos ver alguns conceitos básicos de ordenação e ver como alguns algorítmos tradicionais funcionam.

Introdução

Comecei a escrever a primeira versão deste texto em inglês, em 2000, mas nunca cheguei a concluir. Para quem tiver curiosidade, aqui está a versão do texto que encostei em 2002.

Ordenar coisas é uma tarefa comum na programação. É também um daqueles tipos de tarefas onde o algorítmo utilizado faz uma grande diferença. Os exemplos que vão acompanhar esta série, além de conterem implementações dos algorítmos descritos, vai ajudar a ver como eles funcionam e comparar o desempenho deles.

Ordenação também é o tipo de tarefa que clama por uma boa análise matemática. Você não vai encontrar isto aqui! A "bíblia" da ordenação, na minha opinião, é o livro "The Art of Computer Programming, Vol 3 - Sorting and Searching" de Donald E. Knuth. Foi com este livro que aprendi o que apresento aqui. Alguns podem achar o estilo do Dr Knuth ultrapassado (implicando com os exemplos em linguagem assembler de um computador hipotético), mas dificilmente se acha um texto tão completo como o dele.

Por último, muitas linguagens possuem em sua biblioteca padrão funções genéricas de ordenação e muitos preferem simplesmente as usar sem conhecer como funcionam. Como veremos, existem vários pontos interessantes sobre a ordenação e nem sempre a escolha de um algorítmo é simples. Mesmo que você nunca precise escrever a sua própria função de ordenação, muito pode ser aprendido estudando estes algorítmos.

O Que é Ordenar?

Basicamente, estamos falando em colocar coisas em uma certa ordem. Nós temos itens (ou registros) a serem ordenados. Cada item está associado a uma uma chave. Nosso objetivo é re-arranjar os itens de forma que eles fiquem em ordem crescente (ou decrescente) de chave.

Nesta série vamos nos concentrar em ordenar um vetor de chaves numéricas (inteiras) que estão na memória. As idéias apresentadas podem ser facilmente expandidas:

• Podemos usar os mesmos algorítimos com qualquer tipo de chaves. Tudo que precisamos é uma forma de comparar as chaves e uma maneira de movê-las. Por exemplo, podemos ter chaves alfanuméricas e ordená-las sem considerando maiúsculas e minúsculas como equivalentes (de forma que 'aBc' seja igual a 'AbC' ou 'ABC')
• Podemos ter múltiplas chaves. Se as primeiras chaves são iguais, nós comparamos as segundas e assim por diante até acharmos uma diferença ou testarmos todas as chaves. Se as chaves forem alfanuméricas, podemos fazer isto simplesmente as concatenando. Se misturarmos chaves de tipo diferente, nossa comparação pode usar o operador && do C (ou construção equivalente de outra linguagem) para testar as chaves na ordem correta.
• Ao mesmo tempo em que ordenamos as chaves, ordenamos os registros. Se os registros forem pequenos, simplesmente os movemos junto com as chaves. Se os registros forem grandes, nós guardamos ponteiros para os registros junto com as chaves. Durante a ordenação, movemos junto as chaves e os ponteiros. Ao final seguimos os ponteiros para obter os registros na ordem certa (veja Figura 1).
• Se as chaves não cabem na memória, fazemos a ordenação por partes, gravando as partes em arquivos temporários. Ao final fazemos um merge das partes (ver Figura 2).

Figura 1 - Usando ponteiros para não mover os registros

Figura 2 - Dividindo o arquivo em partes, ordenando e fazendo o merge

Republicando artigos meus da Sharepedia

Estou colocando abaixo links para download dos artigos que eu tinha colocado na finada Sharepedia. A qualidade dos artigos é bem variável, peço desculpas antecipadamente pela pretenção da série "Guia dos Mestres"...

Animal

Um exemplo simples (bobo ?) de uso de árvore binária: um jogo de adivinhação de animais. A árvore consiste em vária perguntas do tipo Sim / Não, onde as folhas são animais. O programa vai percorrendo a árvore (fazendo as perguntas e obtendo as respostas). Ao chegar em uma folha, pergunta se este é o animal que o jogador pensou. Se não for, pergunta qual o animal e pede uma pergunta para distinguí-lo da resposta errada. A árvoré é então atualizada com a nova pergunta e o novo animal.

Arquivo

Avisa se esqueceu disco na unidade

CDAlert é um pequeno utilitário que testa se existe disco removível quando é feito shutdown. Ilustra como descobrir as unidades existentes e seus tipos, através da API Win32.

Arquivo

Aviso (Recado tipo Post-It)

Este é um programinha simples para colocar uma mensagem na tela. A mensagem pode ser colocada na linha de comando, chamando o programa sem parâmetro é apresentado um dialogo para digitacao da mensagem. A janela com a mensagem fica por cima das demais janelas e pode ser arrastada. Para fechá-la, basta dar um double click. Ilustra algumas técnicas menos comuns de programação Windows direto com a API.

Arquivo

Desenhando em Diálogo

O objetivo deste artigo é apresentar uma forma de desenhar gráficos em uma caixa de diálogo, utilizando diretamente a API do Windows. O artigo inclui um programa exemplo que mostra um relógio de ponteiros em um diálogo.

Arquivo

Como fazer um Editor Simples

Este exemplo ilustra três formas de criar um editor simples: usando um Edit Box, usando um Rich Edit controle e "na raça". O código está em C e usa apenas o Win32 SDK .

Arquivo

Launch - demo do uso de CreateProcess

Este programa mostra como usar a função CreateProcess da API do Windows para disparar uma aplicação.

Arquivo

Lista Ligada - O Guia dos Mestres

Este artigo explica a teoria e a prática das Listas Ligadas, com atenção particular à implementação em C e C++.

Arquivo

Exemplo de Uso de ListView

Exemplo de uso de ListView com imagens, usando C + API. Nova versão implementa ordenação pelo cabeçalho das colunas. Destaque para os infames dados usados no exemplo!

Arquivo

Screen Savers - "O Gua dos Mestres"

Uma descrição bem detalhada de como funciona e como fazer screen savers. Inclui dois exemplos, um usando a biblioteca Scrnsave.lib e o outro chamando direto as API do Windows.

Arquivo

Simulação de um Computador

Um exemplo (simples) de como simular um computador. O simulador apresenta na tela os registradores e a memória de um computador hipotético. Programas podem ser entrados em linguagem de máquina ou em assembler. Interessante para quem quer aprender um pouco sobre linguagem de máquina, sobre a simulação de computadores ou mesmo sobre programação Windows.

Arquivo

Threads & Sockets: exemplo de uso

Este código mostra como usar threads e sockets para fazer uma comunicação cliente/servidor.

Arquivo