Páginas

segunda-feira, 21 de novembro de 2011

Informações sobre desafios e competições de programação

E aí pessoal!

Seguindo um dos posts da Loiane sobre problemas de computação e matemática, deixo aqui o link para o repositório no Github com alguns algoritmos que usei para resolver uns problemas no SPOJ. Gostaria contribuir mais com o projeto, mas infelizmente estou com o tempo encurtado e essa parte exige um esforço maior (principalmente porque estou 'enferrujado').

Acho bastante interessante o estudo de algoritmos e matemática, não somente para o profissional de computação. Na minha opinião, é o fundamento de toda a computação: algoritmos e matemática sendo usados juntos para a resolução de problemas (muitas vezes complexos). Acho interessante o estudo de novas linguagens, paradigmas e modelos de arquitetura, mas, acima de tudo, algoritmos e matemática ainda deveriam vir em primeiro lugar na lista de prioridades de estudo de qualquer pessoa que tenha como objetivo o desenvolvimento de sistemas.

Abaixo deixo uma lista de competições de programação que conheço (a Loiane colocou mais alguns no blog dela. Estou colocando somente os que conheço e já participei):

  • TopCoder: mensalmente acontecem competições online (as chamadas SRMs - Single Round Matches), com um certo limite de tempo. Além disso, os competidores podem olhar o algoritmo dos outros competidores e desafiar com entradas diferentes. Os problemas são, em sua maioria, submetidos por competidores. Existem também outras modalidades, como as Marathon Matches (com problemas mais complexos e tempo mais longo para resolver) e as High School Matches (que são as SRMs com problemas um pouco mais fáceis). Esse site também contém um material (escrito por competidores) sobre como resolver os problemas;
  • SPOJ Brasil e SPOJ Internacional: problemas das maratonas de computação nacionais (as qualificativas para o ACM ICPC) e internacionais (geralmente warm-ups que acontecem antes do mundial) e alguns problemas da OBI (Olimpíada Brasileira de Informática);
  • Google Code Jam.
Vale ressaltar que a maioria desses sites (sei que o TopCoder e os SPOJs) tem foruns sobre dicas de como resolver os problemas.

Livros

Outros links interessantes
  • Algorithmist: site contendo explicações sobre algoritmos e alguns problemas resolvidos;
  • 'Notebooks' criados por brasileiros: site com 'notebooks' (pdf com algoritmos implementados) e mais dicas sobre os tipos de problemas que encontramos nas competições.

Se você quer entrar nessa área logo de cara mas tem certo receio de não saber muito bem a parte matemática, indico bastante o estudo de Matemática Discreta. Provavelmente é a parte matemática que mais se aplica à computação, apesar de ser muito fácil encontrar problemas que envolvem Geometria.

Mais algumas dicas

  • Não desista se a sua primeira submissão deu errado, principalmente se você está começando. Existem diversas categorias de problemas, desde erros ao formatar a entrada ou saída a tempo de limite excedido (TLE);
  • Pra quem tem muito erro de TLE, a resposta é bem simples (se você não está tanto problemas pra ler a entrada de dados): você provavelmente está resolvendo da forma errada. Algumas vezes técnicas como memoization ajudam a diminuir o tamanho da memória utilizada e a velocidade de re-computações (como é o caso do fatorial e dos números primos);
  • Algumas competições (como o SPOJ e o UVa) tem problemas que são facilmente quebrados pelo fato da entrada ser muito grande. Linguagens como Java e Python infelizmente sofrem um tanto com isso (em 2011 acredito que Java não sofra tanto, mas Python ainda tem alguns problemas). Na maratona de programação da ACM, a ICPC, é muito fácil ver quem fez código em Java ter problemas com as entradas. Uma das razões pelas quais comecei a usar C++ (ou melhor, C com a stdlib) foi justamente o problema das entradas. O TopCoder tem uma vantagem: você não usa a função main; você cria um método (exatamente como descrito na descrição do problema) e trabalha com os parâmetros dentro do método.

Volto a dizer: acredito fielmente que o estudo de paradigmas, linguagens e modelos de arquitetura são importantíssimos, assim como o estudo de matemática e computação para resolução de problemas.

Qualquer dúvida, postem! Vou enriquecendo o conteúdo do texto conforme for encontrando links interessantes.

Até a próxima!





sábado, 2 de julho de 2011

Lightweight EJB com OpenEJB

Olá!

Vou começar esse blog comentando sobre uma tecnologia que venho utilizando bastante: JEE. Mais especificamente a parte de EJBs. Vejo muitas pessoas falando que EJB não presta, que EJB é uma solução procurando por um problema, que é lento e tudo mais. Tudo bem, é a opinião de muita gente e algumas até apresentam argumentos muito válidos.

Só que eu vejo que existe, também, muito pré-conceito na comunidade de desenvolvedores. Vamos pegar, por exemplo, um desenvolvedor que está procurando uma tecnologia pra desenvolver um projeto de médio porte. Ele faz uma pesquisa, cai em alguns tópicos no GUJ e vê que o pessoal fala muito que EJB não presta. Quando pergunta o porquê de EJB não prestar, muita gente vem com vários argumentos. Alguns eu concordo, outros não. Um dos argumentos que concordo é o de que é demorado de desenvolver devido ao tempo de start do servidor. O start do JBoss 5 "default", por exemplo, demora 1 minuto (no mínimo) em uma máquina "mais ou menos". Isso é muito tempo quando se tem testes pra executar e alguns deles quebram. A quantidade de vezes que executamos os testes quando usamos TDD é enorme. Iniciar o servidor a cada 5 minutos não é uma opção porque perdemos muito tempo. Isso não acontece só com o JBoss: conforme a aplicação vai crescendo outros servidores de aplicação, como o Glassfish, chegam no mesmo problema.

Quando o sistema vai entrar em produção, iniciar o servidor de aplicação não é problema. Ele provavelmente vai ser iniciado 1, 2 vezes ao dia (pra não dizer na semana). O JBoss e o Glassfish são dois servidores muito bons quando isso é necessário: oferecem estabilidade, robustez e, se a empresa estiver disposta a pagar, um suporte muito bom.

O detalhe é que o desenvolvedor não precisa usar JBoss ou Glassfish ou algum outro super-application-server. Existem diversas opções por aí, como o MyContainer, que foi desenvolvido inteiramente pelo pessoal da Dextra. Um outro ótimo lightweight container é o OpenEJB. Uma das coisas mais legais desses lightweight containers é que você não precisa fazer o deploy, iniciar o servidor e executar os testes manualmente. O OpenEJB, por exemplo, permite você colocar o container dentro da aplicação (e não o contrário, como fazemos com outros: colocamos a aplicação dentro do container).

Pra melhor introduzir o OpenEJB, vou fazer um exemplo com testes.

Configurando o ambiente
Vamos configurar nosso ambiente. Primeiramente, vá até o site do OpenEJB e faça o download da última versão (estou usando a 3.1.4). Descompacte os arquivos em algum lugar na sua máquina.

Agora, vamos configurar as bibliotecas que precisamos pra rodar nosso container dentro da aplicação. Estou usando o Eclipse Indigo. No Eclipse, clique em Window, Preferences, Java, Build Path, User Libraries. Clique em New, coloque o nome de OpenEJB, clique em Add Jars, e selecione todos os jars que ficam dentro da pasta lib do OpenEJB. Depois disso, clique com o botão direito no seu projeto, Build Path, Configure Build Path. Na aba Libraries, clique em Add Library, User Library, marque a checkbox no OpenEJB e pronto. Configure o JUnit 4 também, pra fazermos alguns testes.

Aplicação
Agora, vamos à parte divertida: escrever o código da aplicação. A aplicação que pensei é bem simples: dado um texto, mostraremos a quantidade de vogais que esse texto tem. Então, por exemplo, o texto "teste um dois tres" apresentaria o seguinte:
a: 0
e: 3
i: 1
o: 1
u: 0

Não vou me preocupar com acentos e letras maiúsculas, já que o propósito desse tutorial é dar uma introdução ao OpenEJB embarcado.

Código
Vamos criar um método de teste:
DetalhamentoVogaisService service = serviceLocator.getDetalhamentoVogaisService();
Assert.assertTrue(service.getDetalhamento("").isEmpty());
Agora vamos criar a interface DetalhamentoVogaisService. Vamos anotar ela como Remote.
@Remote
public interface DetalhamentoVogaisService {

    public Map<String, Integer> getDetalhamento(String texto);

}

E agora vamos criar a implementação do nosso Service, nossa classe DetalhamentoVogaisSession. Vamos anotar ela como Stateless, porque não precisamos manter o estado por ora.
@Stateless
public class DetalhamentoVogaisSession implements DetalhamentoVogaisService {

    @Override
    public Map<String, Integer> getDetalhamento(String texto) {
        return new HashMap<String, Integer>;
    }

}

Nosso teste ainda não compila porque não temos nosso ServiceLocator. Por questões de simplicidade, vou criar um ServiceLocator bem limitado.
private boolean embedded;
private Context context;

public ServiceLocator(boolean embedded) {
    this.embedded = embedded;
    criarContext();
}

private void criarContext() {
    String nomeDaClasseFactory = embedded ? LocalInitialContextFactory.class.getName() : RemoteInitialContextFactory.class.getName();

    Properties properties = new Properties();
    properties.setProperty(Context.INITIAL_CONTEXT_FACTORY, nomeDaClasseFactory);

    if (embedded) {
        properties.setProperty(Context.PROVIDER_URL, "ejbd://localhost:4201");
    }

    try {
        context = new InitialContext(properties);
    } catch (NamingException e) {
        e.printStackTrace();
    }
}

public DetalhamentoVogaisService getDetalhamentoVogaisService() {
    return (DetalhamentoVogaisService) getServiceImpl(DetalhamentoVogaisSession.class.getName() + "Remote");
}

private Object getServiceImpl(String name) {
    try {
        return context.lookup(name + "Remote");
    } catch (NamingException e) {
        e.printStackTrace();
    }

    return null;
}
Teremos que mandar um parâmetro na hora de criar esse ServiceLocator. Como dito acima, o OpenEJB pode ser embarcado na aplicação, e é isso que vamos fazer. Se for necessário colocar o container em um servidor central, pra vários clientes acessarem os EJBs, teremos que modificar a criação do contexto no método criarContext. A única coisa que teríamos de modificar é o localhost (no caso, colocaríamos o IP da máquina que é o servidor).

Agora vamos embutir o container nos nossos testes. A única coisa que precisamos fazer é criar a instância do ServiceLocator nas configurações iniciais dos testes.
private ServiceLocator locator;

@Before
public void configurarLocator() {
    this.locator = new ServiceLocator(true);
}
Executando nossos testes, temos um erro: não foi possível encontrar o serviço. Isso acontece porque quando embarcamos o OpenEJB, precisamos usar um xml de configuração, de forma que o container saiba quais sessions ele deve usar. Na pasta META-INF, dentro da src, crie um XML chamado ejb-jar.xml, com o seguinte conteúdo:
Agora, executamos novamente nossos testes. Tudo passando ok, conforme queremos. Notemos mais atentamente à saída no Console do Eclipse. Aparecem algumas linhas de log do OpenEJB, referenciando o start do container. Isso é normal quando falamos em containers embutidos, porque o container vai ser inicializado na criação do contexto.
Apache OpenEJB 3.1.4 build: 20101112-03:32
http://openejb.apache.org/
INFO - openejb.home = dev/business-project
INFO - openejb.base = dev/business-project
INFO - Configuring Service(id=Default Security Service, type=SecurityService, provider-id=Default Security Service)
INFO - Configuring Service(id=Default Transaction Manager, type=TransactionManager, provider-id=Default Transaction Manager)
INFO - Found EjbModule in classpath: dev/business-project/build/classes
INFO - Beginning load: dev/business-project/build/classes
INFO - Configuring enterprise application: classpath.ear
INFO - Configuring Service(id=Default Stateless Container, type=Container, provider-id=Default Stateless Container)
INFO - Auto-creating a container for bean DetalhamentoVogaisSession: Container(type=STATELESS, id=Default Stateless Container)
INFO - Enterprise application "classpath.ear" loaded.
INFO - Assembling app: classpath.ear
INFO - Jndi(name=DetalhamentoVogaisSessionRemote) -> Ejb(deployment-id=DetalhamentoVogaisSession)
INFO - Created Ejb(deployment-id=DetalhamentoVogaisSession, ejb-name=DetalhamentoVogaisSession, container=Default Stateless Container)
INFO - Deployed Application(path=classpath.ear)

Dando uma refatorada básica na nossa classe de testes, deixamos ela assim:
public class DetalhamentoVogaisTests {

    private ServiceLocator locator;

    @Before
    public void configurarLocator() {
        this.locator = new ServiceLocator(true);
    }

    private DetalhamentoVogaisService getService() {
        return this.locator.getDetalhamentoVogaisService();
    }

    @Test
    public void testarComQuantidadeVazia() {
        Assert.assertTrue(getService().getDetalhamento("").isEmpty());
    }

}

Vamos criar dois casos de teste, dessa vez um pouco mais complexos que o anterior.
@Test
public void testarComTodasAsVogais() {
    Map<String, Integer> resultado = getService().getDetalhamento("aaeeioouu");
    Assert.assertEquals(resultado.get("a"), new Integer(2));
    Assert.assertEquals(resultado.get("e"), new Integer(2));
    Assert.assertEquals(resultado.get("i"), new Integer(1));
    Assert.assertEquals(resultado.get("o"), new Integer(2));
    Assert.assertEquals(resultado.get("u"), new Integer(2));
}

@Test
public void testarSemVogais() {
    Map<String, Integer> resultado = getService().getDetalhamento("bcdftgp");
    Assert.assertEquals(resultado.get("a"), new Integer(0));
    Assert.assertEquals(resultado.get("e"), new Integer(0));
    Assert.assertEquals(resultado.get("i"), new Integer(0));
    Assert.assertEquals(resultado.get("o"), new Integer(0));
    Assert.assertEquals(resultado.get("u"), new Integer(0));
}

Executando os testes vemos que temos erros. Portanto vamos arrumar nossa classe de negócio.
@Override
public Map<String, Integer> getDetalhamento(String texto) {
    Map<String, Integer> detalhes = new HashMap<String, Integer>();

    if (texto != null && texto.length() > 0) {
        detalhes.put("a", 0)
        detalhes.put("e", 0);
        detalhes.put("i", 0);
        detalhes.put("o", 0);
        detalhes.put("u", 0);

        for (char c : texto.toCharArray()) {
            if (isVogal(c)) {
                detalhes.put(String.valueOf(c), detalhes.get(String.valueOf(c)) + 1);
            }
        }
    }

    return detalhes;
}

private boolean isVogal(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
Executando os testes, vemos que temos uma green bar. Agora podemos refatorar nosso Session Bean.
@Override
public Map<String, Integer> getDetalhamento(String texto) {
    Map<String, Integer> detalhes = new HashMap<String, Integer>();

    if (texto != null && texto.length() > 0) {
        detalhes = inicializarDetalhesZerados(detalhes);

        for (char c : texto.toCharArray()) {
            if (isVogal(c)) {
                detalhes.put(String.valueOf(c), detalhes.get(String.valueOf(c)) + 1);
            }
        }
    }

    return detalhes
}

private Map<String, Integer> inicializarDetalhesZerados(Map<String, Integer> detalhes) {
    detalhes.put(Vogais.A.getString(), 0);
    detalhes.put(Vogais.E.getString(), 0);
    detalhes.put(Vogais.I.getString(), 0);
    detalhes.put(Vogais.O.getString(), 0);
    detalhes.put(Vogais.U.getString(), 0);

    return detalhes;
}

private boolean isVogal(char c) {
    return c == Vogais.A.getCaracter()
        || c == Vogais.E.getCaracter()
        || c == Vogais.I.getCaracter()
        || c == Vogais.O.getCaracter()
        || c == Vogais.U.getCaracter();
}
O Enum:
public enum Vogais {

    A("a", 'a'), E("e", 'e'), I("i", 'i'), O("o", 'o'), U("u", 'u');

    private String letra;
    private char caracter;

    Vogais(String letra, char caracter) {
        this.letra = letra;
        this.caracter = caracter;
    }

    public String getString() {
        return this.letra;
    }

    public char getCaracter() {
        return this.caracter;
    }

}
E os testes refatorados:
@Test
public void testarComTodasAsVogais() {
    Map<String, Integer> resultado = getService().getDetalhamento("aaeeioouu");
    Assert.assertEquals(resultado.get(Vogais.A.getString()), new Integer(2));
    Assert.assertEquals(resultado.get(Vogais.E.getString()), new Integer(2));
    Assert.assertEquals(resultado.get(Vogais.I.getString()), new Integer(1));
    Assert.assertEquals(resultado.get(Vogais.O.getString()), new Integer(2));
    Assert.assertEquals(resultado.get(Vogais.U.getString()), new Integer(2));
}

@Test
public void testarSemVogais() {
    Map<String, Integer> resultado = getService().getDetalhamento("bcdftgp");
    Assert.assertEquals(resultado.get(Vogais.A.getString()), new Integer(0));
    Assert.assertEquals(resultado.get(Vogais.E.getString()), new Integer(0));
    Assert.assertEquals(resultado.get(Vogais.I.getString()), new Integer(0));
    Assert.assertEquals(resultado.get(Vogais.O.getString()), new Integer(0));
    Assert.assertEquals(resultado.get(Vogais.U.getString()), new Integer(0));
}

Não me preocupei muito com a limpeza do código porque não é o intuito desse tutorial.

Rodando os testes novamente, vemos que tudo passa. E o melhor de tudo: na minha máquina (Core 2 Duo, 4 GB RAM, Ubuntu 11.04) levei 2 segundos! Com alguns outros containers, levaríamos 50 segundos, no mínimo!

Conclusão
Quero deixar bem claro que não sou contra o uso de JBoss ou Glassfish. Acho que a utilização desses dois é muito importante em uma aplicação que precisa de muita robustez, escalabilidade e performance. São ótimos servidores de aplicação (provavelmente os melhores do mercado). Nesse pequeno tutorial só quis mostrar as alternativas de containers EJBs que temos para desenvolvimento e testes, e desmistificar aquele pré-conceito de que EJBs precisam ser pesados e lentos.

Outro fato que quero deixar bem claro é que não estou falando aos desenvolvedores: larguem tudo o que vocês têm e venham usar EJB com OpenEJB. Existe outras alternativas por aí que são muito boas, como o Spring. O Spring é, inclusive, uma das minhas ferramentas preferidas! Mas isso já é conversa pra outro post :-)