Inércia Sensorial

2007-07-26

Crivo de Eratóstenes em Python

Filed under: Python — inerte @ 12:56

Estou fazendo os desafios do Projeto Euler e nos dez primeiros já vi três com números primos. Meu primeiro algoritmo ingenuamente testava a primalidade de um número tentando dividí-lo por todos os números menores que ele.

Uma lista com 1.000 números primos dessa maneira gera em pouco menos de um segundo no meu computador. Já 2.000, mais de 9 segundos. E 10.001, como pedido por um dos desafios, eu nem tive paciência de esperar os cálculos acabarem. Minha primeira implementação foi a seguinte:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def primo(n):
    for i in xrange(2, n):
        if n % i == 0:
            return False
    return True
 
primo_lista = []
n = 1
while 1:
    if primo(n):
        primo_lista.append(n)
        if len(primo_lista) == 1000:
            break
    n = n + 1

Pocurando por métodos mais velozes achei dois, o Crivo de Eratóstenes e o Crivo de Atkin. O primeiro é mais simples, então decidi implementá-lo. O Crivo de Eratóstones é definido assim:

  1. Escreva uma lista dos números entre 2 e o maior número que você quer testar a primalidade. Vamos chamá-la de lista1;
  2. Escreva o número 2, o primeiro número primo, em outra lista que conterá os números primos encontrados. Vamos chamá-la de lista2;
  3. Remova o 2 e todos os múltiplos dele da lista1;
  4. O primeiro número que sobrar da lista1 é primo. Escreva ele na lista2;
  5. Remova essa número e todos os seus múltiplos da lista1. A remoção pode começar da raiz quadrada do número, já que múltiplos menores foram removidos em passos anteriores;
  6. Repita os passos de 4 a 6 até não restarem mais números na lista1;

A classe a seguir, escrita em Python, retorna uma lista com todos os números primos entre 2 e um número especificado (max_n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
max_n = 50
 
class CrivoDeEratostenes:
    def __init__(self, max_n):
        self.lista = range(2, max_n + 1)
        self.primo_lista = [2]
        self.crivo()
 
    def crivo(self):
        primo_n = self.lista[0]
        max_n = self.lista[-1] + 1
        self.lista.remove(primo_n)
        for n in self.lista:
            if n % primo_n == 0:
                self.lista.remove(n)
        if len(self.lista) > 0:
            self.primo_lista.append(self.lista[0])
            return self.crivo()
        else:
            return self.primo_lista
 
 
print CrivoDeEratostenes(max_n).primo_lista
 
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Pesquisando sobre Eratóstenes na Internet, descobri que ele foi um animal. O grego viveu dois séculos antes de Cristo e conseguiu calcular com 16% de erro a circunferência da Terra. Leu nos papiros de Biblioteca de Alexandria (aonde foi Diretor) que o sol iluminava o fundo de um poço na cidade de Siena (hoje Assuã) ao meio dia do dia mais longo (o solstício) no verão daquele cidade, em 21 de Junho. Ou seja, a luz fazia um ângulo reto com a Terra.

Mas no dia 21 de Junho, quando era meio dia em Siena, o Sol projetava sombras em Alexandria. Eratóstenes conclui então que a Terra era redonda. O ângulo das sombras deu 7º12′, quase 1/50 dos 360º de uma circunferência, então a distância entre Alexandria e Siena multiplicada por 50 seria a circunferência do planeta.

Mandou um pessoal percorrer essa distância e eles voltaram com 925km. E 50 vezes 925 é 46.250 km, enquanto a Terra tem 40.076 km.

Queria crescer de novo pra ser igual a ele 🙂

2007-05-17

Imprimir com javascript

Filed under: Javascript — inerte @ 14:53

Moleza. Basta chamar window.print(). Por exemplo, para mandar a página para impressão ao clicar em um botão bastaria:

1
<input type="button" value="Imprima essa página" onclick="window.print();" />

2007-05-15

Procura binária no PHP

Filed under: PHP — inerte @ 22:41

Uma coisa é certa, a função in_array do PHP é devagar, lerda demais.

Existe uma alternativa para pesquisar se o elemento está na matriz chamada “procura binária”, que aliás, tanto faz a linguagem que você usa, as idéias são as mesmas. O conceito é simples, ver se o item está no meio da matriz, se não estiver, cortar ela no meio, ver se está na metade, se não estiver, cortar a metade ao meio, ad infinitum, ou até que dure.

Imagine que você tenha de procurar o nome “Julio Nobrega” na lista telefônica. Ir de item em item e ver se cada um equivale ao termo é loucura. Oras, abra a lista bem no meio e veja o nome, se ele for Julio Nobrega, pronto. Se não for, o nome que está no meio, é maior ou menor que o nosso termo? Se for maior, parta na metade a lista e procure na primeira parte. Eliminamos 50% de onde vamos procurar num piscar de olhos. Repita isso, e o espaço de procura vai diminuindo até só sobrar o termo pesquisado. Muito melhor que um por um.

Lá vai a função:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function procura_binaria($elemento, $matriz)
{
    $baixo = 0;
    $alto = sizeof($matriz) - 1;
    while ($baixo <= $alto) { 
        $meio = floor(($baixo + $alto) / 2);
        if ($elemento == $matriz[$meio]) {
            return $matriz[$meio];
        } else {
            if ($elemento < $matriz[$meio]) {
                $alto = $meio - 1;
            } else {
                $baixo = $meio + 1;
            }
        }
    }
    return false; // Não achou!
}

Usar é moleza:

1
2
3
if (!pesquisa_binaria($termo, $matriz)) {
    echo 'Não achou!';
}

Tutorial de cron e crontab

Filed under: Programação — inerte @ 22:28

O crontab é o arquivo de configuração do cron, que executa comandos em determinados intervalos de tempo.

Digita na linha de comando para editá-lo com o editor de textos padrão da sua conta de usuário na máquina:

[code]crontab -e[/code]

Coloque um comando por linha. A estrutura é a seguinte:

[code]# Jogo da velha no começo da linha é comentário
# +—————- minuto (0 – 59)
# | +————- hora (0 – 23)
# | | +———- dia do mês (1 – 31)
# | | | +——- mês (1 – 12)
# | | | | +—- dia da semana (0 – 7) (Domingo=0 or 7)
# | | | | |
# * * * * * Comando para executar[/code]

Imaginemos que você queira rodar o comando “python2.4 /home/usuario/script.py” todo dia às duas da manhã:

[code]00 2 * * * python2.4 /home/usuario/script.py[/code]

Para especificar um intervalo em qualquer campo, utilize um traço, ou sinal de subtração (esse: “-“). Por exemplo, a configuração abaixo será executada todo dia da uma às dez da manhã de minuto em minuto:

[code]* 1-10 * * * python2.4 /home/usuario/script.py[/code]

Para especificar “ou”, utilize uma vírgula. Segue um exemplo para ser executado apenas às duas da manhã e da tarde, aos Domingos e Quarta-Feiras:

[code]* 2,14 * * sun,wed python2.4 /home/usuario/script.py[/code]

Se você quer rodar o script de cinco em cinco minutos no Sábado (note a divisão dos minutos):

[code]00-59/5 * * * 6 python2.4 /home/usuario/script.py[/code]

Por padrão, o crontab enviará um email à conta que o carrega se existe alguma saída no comando. Para cancelar o email do crontab, redirecione a saída para outro lugar. Por exemplo, para /dev/null

[code]00 2 * * * python2.4 /home/usuario/script.py >/dev/null 2>&1[/code]

Para redirecionar a um arquivo:

[code]00 2 * * * python2.4 /home/usuario/script.py >/home/usuario/arquivo.log[/code]

Para ver o seu crontab:

[code]crontab -l[/code]

Para apagar o crontab:

[code]crontab -r[/code]

Quaisquer dúvidas, comentem.

2007-04-28

O paradigma de programação afeta a performance de aplicativos Web?

Filed under: Programação — inerte @ 17:19

Rafael de Camillis, desenvolvedor do Garimpar, envou uma interessante pergunta à lista brasileira no Google Groups do Django:

Pessoal queria saber o que vcs acham, o que é melhor pra programação web: Procedural ou Orientação à Objeto.

Um site todo procedural tem a mesma performance de um site feito com Orientação a Objeto?

Minha resposta à pergunta dele estava ficando kilométrica e decidi colocar aqui no blog. Segue a dita cuja!

A performance é independente do paradigma usado para fazer o programa. O que acontece é que certas técnicas em certas linguagens de programação são mais eficientes dependendo dos requerimentos.

Por exemplo, a programação funcional é teoricamente ótima para processadores com mais de um núcleo, entretanto você provavelmente só verá ganhos enormes quando você estiver utilizando uma linguagem que faça esse lado funcional de maneira “pura“. É possível programar de maneira funcional em Lisp e Python, mas devido à características da linguagem, você não verá os mesmos ganhos que em Haskell ou Erlang.

C++, por exemplo, provavelmente vai ser uma das linguagens onde você vai conseguir maiores velocidades, independentemente do paradigma utilizado e contra quais linguagens. Procedural ou OOP, C++ bate Java em 99.99% das vezes, se feita direito.

Ah, mas então a pergunta é, dentro da mesma linguagem (vamos assumir Python), qual é mais rápido, Procedural ou OOP? Novamente, tudo depende 🙂 Em Python, tudo é um objeto, então qualquer coisa que saia de código a gente poderia dizer que já é OOP. Mas aí entra o estilo do programador, a competência dele. Felizmente, ou infelizmente, esse é o principal fator. Imaginemos que conseguíssemos chegar à solução que determinado algoritmo (perceba o escopo do problema, é micro, e não macro como _todo_ o desenvolvimento Web) é mais rápido quando feito de forma Procedural. Se déssemos o problema para ser solucionado por N programadores, divididos entre uso de técnicas procedural e OOP, a verdade é que a performance das soluções dependeria da competência das pessoas. Poderia muito bem sair o OOP como vencedor.

De qualquer jeito, deixe-me voltar ao foco 🙂 Os gargalos de performance em aplicativos web raramente estão na linguagem de programação utilizada (tirando aplicar aberrações como Cobol :), mas sim, na ordem:

1) Banco de dados;
2) Servidor de páginas;
3) Erros de programação;

Isso acontece pois é relativamente fácil resolver problemas de escalabilidade em aplicativos web. Quando a linguagem é lerda, geralmente basta jogar mais uma máquina com uma instância do servidor web para distribuir as requisições. Na verdade, esse lerdeza é geralmente irrisória se comparada às outras linguagens, e irrelevante levando em conta outras soluções. É possível decuplicar a performance fazendo cache das páginas dinâmicas. Duplicar dobrando a memória RAM do servidor. Triplicar separando o banco de dados do servidor web em uma máquina exclusiva.

Essa mensagem não pretende exemplificar quais procedimentos você poderia tomar para aumentar a performance nos três pontos que eu passei, mas a verdade é que umas das últimas de suas preocupações deve ser qual linguagem de programação utilizar para aplicativos web, e menos ainda qual paradigma ou técnica utilizar. Não se preocupe com isso, e ataque o problema de outra maneira.

Se alguém quiser, eu posso fazer um novo post dando uma visão geral sobre como melhorar a performance de aplicativos web.

2007-04-16

Estilo de listas com CSS

Filed under: CSS — inerte @ 01:09

As seguintes propriedades modificam estilos de listas usando Cascading Style Sheets:

  • list-style-image: imagem como marcador;
  • list-style-position: posição do marcador;
  • list-style-type: tipo de marcador;
  • list-style: abreviação para múltiplas propriedades;

Como preencher os valores das propriedades:

  • list-style-image
    1. none
    2. URL: url(diretorio/imagem.extensao)
  • list-style-position
    1. outside: marcador desalinhado do texto
    2. inside: marcador alinhado com texto
  • list-style-type
    1. none: sem marcador
    2. disc: círculo (bola pintada)
    3. circle: circunferência (bola vazia)
    4. square: quadrado pintadi
    5. lower-alpha: letra minúscula a, b, c, d, …
    6. upper-alpha: letra maiúscula A, B, C, D, …
    7. decimal: números 1, 2, 3, 4, …
    8. decimal-leading-zero
    9. lower-roman: romano minúsculo i, ii, iii, iv, …
    10. upper-roman: romano maiúsculo I, II, III, IV, …

2007-04-13

Declaração de CSS na página

Filed under: CSS — inerte @ 16:53

Eu costumo colocar todo o código de CSS em arquivos separados mas de vez em quando surge a necessidade de colocá-los no corpo da página, dentro do <head>. Para que eu nunca mais esqueça então, é assim:

[html]

[/html]

2006-11-24

Desfazer remove do svn

Filed under: Programação — inerte @ 16:47

Removeu por engano um arquivo de sua cópia de trabalho local pelo svn? Para voltar essa remoção, basta dar update no arquivo ou no diretório que o contém. A última versão do arquivo no repositório será trazida. Entretanto, as modificações locais terão sido perdidas…

2006-08-22

Texto aleatório com Javascript

Filed under: Javascript — inerte @ 16:25

Pequena função em javascript para retornar uma string com caracteres aleatórios:

1
2
3
4
5
6
7
8
9
10
function textoAleatorio(tamanho)
{
    var letras = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXTZabcdefghiklmnopqrstuvwxyz';
    var aleatorio = '';
    for (var i = 0; i < tamanho; i++) {
        var rnum = Math.floor(Math.random() * letras.length);
        aleatorio += letras.substring(rnum, rnum + 1);
    }
    return aleatorio;
}

Só passar como argumento da função o tamanho da string que você quer. As letras permitidas estão na variável letras. Mexa nela à vontade para remover as maiúsculas, ou remover as parecidas, afinal o pessoal se confunde com 0 e O, né mesmo?

MD5 do Dojo igual à função md5 do PHP

Filed under: Javascript — inerte @ 15:08

Estou gerando um formulário de autenticação que “encripta” (bem… faz um hash md5) a senha antes de enviar o formulário, para não transmití-la pela rede como texto plano. Não é um SSL de pobre, se você achou isso. Complementa a segurança do SSL, já que existem malwares que interceptam no navegador tudo o quê o usuário enviar.

De qualquer jeito, para gerar um hash MD5 no Dojo igual ao produzido pelo md5() do php, use o seguinte:

1
2
3
4
<script type="text/javascript">
dojo.require("dojo.crypto.MD5");
var hash = dojo.crypto.MD5.compute('string', dojo.crypto.outputTypes.Hex);
</script>

E agora, colocado em uma função:

1
2
3
4
5
6
<script type="text/javascript">
function phpmd5(string) {
    dojo.require("dojo.crypto.MD5");
    return dojo.crypto.MD5.compute(string, dojo.crypto.outputTypes.Hex);
}
</script>

Em um próximo post explico como usar em um formulário de autenticação.

« Newer PostsOlder Posts »

Powered by WordPress