quarta-feira, 13 de fevereiro de 2013

QuickSort funcional com C# – Uma só linha de código

No processo de aprendizagem de linguagens funcionais por vezes ficamos abismados com a simplicidade com que são abordados alguns algoritmos que tipicamente damos como complexos. Aqui há uns dias estava a resolver uns exercícios de Lisp quando dei por mim a observar a implementação de um QuickSort nesta linguagem:

(defun partition (fun array)
  (list (remove-if-not fun array) (remove-if fun array)))
(defun sort (array)
  (if (null array) nil
    (let ((part (partition (lambda (x) (< x (car array))) (cdr array))))
      (append (sort (car part)) (cons (car array) (sort (cadr part)))))))

(retirado do artigo na wikipedia)

Assim de repente isto tem um aspecto bem mais simples do que as implementações comuns em C#, Java ou qualquer outra linguagem orientada a objectos. No fundo, o conceito do algoritmo diz para escolher um elemento e juntar a lista ordenada de todos os menores com o elemento e com a lista ordenada de todos os maiores. Simples, não? Então e porque não fazer o mesmo em C#? É possível implementar um QuickSort apenas com uma linha de código? Uma primeira tentativa:

public static IEnumerable<int> LinqIntQuickSort(IEnumerable<int> x)
{
    return x.Count() <= 1
        ? x
        : LinqIntQuickSort(x.Skip(1).Where(z => z <= x.First()))
            .Concat(new List<int> { x.First() })
            .Concat(LinqIntQuickSort(x.Skip(1).Where(z => z > x.First())));
}

E não é que funciona? Ok, mas apenas com números. Generalizando obtemos algo do género:

 public static IEnumerable<T> LinqGenericQuickSort<T>(IEnumerable<T> x, Func<T, T, int> fnCompare)
{
    return x.Count() <= 1
        ? x
        : LinqGenericQuickSort(x.Skip(1)
                .Where(z => fnCompare(z, x.First()) <= 0), fnCompare)
            .Concat(new List<T> { x.First() })
            .Concat(LinqGenericQuickSort(x.Skip(1)
                .Where(z => fnCompare(z, x.First()) > 0), fnCompare));
}

Que, para a mesma lista de inteiros, pode ser chamado simplesmente assim:

sortedList = LinqGenericQuickSort(unsortedList, (x, y) => x - y);

Já agora, se quisermos apenas utilizar uma expressão lambda:

Func<IEnumerable<int>, Func<int, int, int>, IEnumerable<int>> fn = null;
fn = (l1, fnCompare) => l1.Count() <= 1
    ? l1
    : fn(l1.Skip(1).Where(z => fnCompare(z, l1.First()) <= 0), fnCompare)
        .Concat(new List<int> { l1.First() })
        .Concat(fn(l1.Skip(1).Where(z => fnCompare(z, l1.First()) > 0), fnCompare));

sortedList = fn(list, (x, y) => x - y);

Atenção que este exemplo apenas serve para demonstrar potencialidades do Linq e expressões lambda, é muito ineficiente quando comparado com as implementações tradicionais.

quinta-feira, 18 de agosto de 2011

Enumeração de listas com Tasks

Imaginemos que num código já existente temos um método que itera uma lista e que efectua uma qualquer operação com o seu conteúdo. Neste exemplo simplesmente imprime o próprio item:

        static void AsyncPrint<T>(List<T> list)
        {
            foreach (var i in list)
            {
                Console.WriteLine("-> :{0}", i);
            }
        }

Então alguém decide que a operação que é efectuada sobre cada item pode ser feita em paralelo e nem sequer é necessário aguardar pelo resultado. O código é alterado para:

        static void AsyncPrint1<T>(List<T> list)
        {
            foreach (var i in list)
            {
                Task.Factory.StartNew(() => { Console.WriteLine("-> :{0}", i); });
            }
        }

A questão que se coloca é: o resultado é o mesmo?
Ou melhor ainda se o programador que altera este código é fã de lambda expressions e reescreve desta forma:

        static void AsyncPrint2<T>(List<T> list)
        {
            list.ForEach((i) =>
            {
                Task.Factory.StartNew(() => { Console.WriteLine("-> :{0}", i); });
            });
        }

O output dos métodos AsyncPrint, AsyncPrint1 e AsyncPrint2 é semelhante? Não é? Como é possível? O que está a acontecer?
Ora, o método AsyncPrint2 obtém o mesmo resultado do AsyncPrint, mas em AsyncPrint1 obtemos um resultado diferente. Tipicamente, é impresso sempre o mesmo item ou alguns são impressos em duplicado e faltam outros. Porquê? Ao iniciar uma Task dentro da enumeração tradicional do foreach e como a acção concreta está definida num delegate (ou lambda expression) contido no método, a variável i que é acedida no corpo do delegate é uma closure que revela o seu valor no momento que é acedida. Quando a lista é iterada, é dada ordem de início de uma tarefa para o tratamento do item actual e avança-se para o próximo, mas a iteração da lista continua enquanto a Thread se mantiver em execução. Ou seja, não é garantido que a tarefa se inicie no momento da sua criação e muito provavelmente, quando esta se iniciar, a enumeração já avançou e o item actual já não é o mesmo.
No método AsyncPrint2 o comportamento é o esperado porque a variável i é um parâmetro de entrada do delegate que é invocado na implementação do método List<T>.forEach(), não é uma closure.
Então, como se pode fazer para manter a utilização da expressão clássica do foreach? Simples, basta que se deixe de utilizar a variável de iteração como closure:

        static void AsyncPrint3<T>(List<T> list)
        {
            foreach (var i in list)
            {
                var x = i;
                Task.Factory.StartNew(() => { Console.WriteLine("-> :{0}", x); });
            }
        }

Já agora, também se pode utilizar a Task Parallel Library, assim:

        static void AsyncPrint4<T>(List<T> list)
        {
            list.AsParallel().ForAll((i) =>
            {
                 Console.WriteLine("-> :{0}", i); 
            });
        }

No entanto, é necessário ter em atenção que aqui o comportamento será ligeiramente diferente: neste caso o método só termina quando a operação terminar em todos os itens da lista enquanto que nos exemplos anteriores isso não acontece.

Para aprender mais sobre closures recomendo este artigo do Jon Skeet: The Beauty of Closures

domingo, 1 de maio de 2011

Acesso ao contexto em linha

Para quem utiliza Entity Framework, o acesso aos dados é fornecido pelo contexto (gerado pelo Entity Data Model Designer). Ora, o contexto gerado pela ferramenta deriva de System.Data.Objects.ObjectContext que por sua vez implementa IDisposable. Dizem as boas práticas que um objecto que seja IDisposable deve ser usado da seguinte forma:

        public IEnumerable<Product> Products { get; set; }
        void Sample1()
        {
            using (var ctx = new NorthwindEntities())
            {
                Products = ctx.Products.Where(p => p.UnitPrice < 10);
            }
        }

Simples e eficaz. Mas, agora imaginemos que quero carregar a lista de produtos num outro objecto e até a posso colocar no construtor ou na inicialização directa:

        class SomeObject { public IEnumerable<Product> Products { get; set; } }

                                                                                               
        void Sample2()
        {
            using (var ctx = new NorthwindEntities())
            {
                SomeObject someObject1 = new SomeObject()
                {
                    Products = ctx.Products.Where(p => p.UnitPrice < 10)
                };
            }
            //someObject1 not available here...
        }

Então temos um problema: é que a utilização do objecto criado fica restrita ao corpo da estrutura using. É certo que se pode declarar o objecto fora da estrutura ou simplesmente expandir a estrutura, mas isso nem sempre é desejável. Para contornar esta situação costumo utilizar um pequeno método inspirado na inversão de controlo, assim:

    public partial class NorthwindEntities
    {
        public static T Execute<T>(Func<NorthwindEntities, T> f)
        {
            using (var ctx = new NorthwindEntities())
            {
                return f(ctx);
            }
        }
    }

Neste caso, coloquei o método na própria classe de contexto, mas pode ser colocado numa qualquer classe estática. A razão de o ter colocado directamente no contexto é que é dependente do próprio contexto devido à inicialização local do mesmo. Com esta pequena ajuda, a mesma consulta pode ser escrita assim:

        void Sample3()
        {
            Products = NorthwindEntities.Execute(ctx => ctx.Products.Where(p => p.UnitPrice < 10));
        }

Ou assim:

        void Sample4()
        {
            SomeObject someObject1 = new SomeObject()
            {
                Products = NorthwindEntities.Execute(ctx => ctx.Products.Where(p => p.UnitPrice < 10))
            };
            //someObject1 available here...
        }

Claro que este exemplo apenas tem utilização quando o contexto apenas é necessário para uma única consulta. Para mais do que uma consulta deverá sempre ser utilizado o padrão standard.

quarta-feira, 3 de fevereiro de 2010

Formação SCRUM Master

Nos dias 1 e 2 de estive na formação SCRUM Master com Mitch Lacey e Jeff Sutherland. Na minha luta contra algumas ideias feitas oriundas das metodologias tradicionais, tinha já alguma informação sobre a forma de organização do SCRUM e já não é a primeira vez que tento seguir alguns dos fundamentos.

A possibilidade de trocar impressões com alguém como o sr. Jeff Sutherland é algo de único. Além de ser um dos co-autores do SCRUM e um dos signatários do manifesto ágil, tem uma carreira impressionante que vai por exemplo desde piloto de caça na guerra do Vietnam a investigador de tratamentos contra o cancro. Vejam a página dele no linkedin!

Podem também ver este vídeo.

O Mitch Lacey (linkedin) é um comunicador nato com muita experiencia em aplicação de SCRUM em projectos reais.

Foram dois dias muito intensos para depois voltar ao mundo real...

sábado, 24 de outubro de 2009

You can’t control what you can’t measure

Não consegues controlar o que não consegues medir. Forte, não é? Esta afirmação é utilizada como um dos grandes chavões em todas as exposições onde se defende a aplicação exaustiva de métricas sobre processos de desenvolvimento de software. A maioria das pessoas que "põe a mão na massa" tem o sentimento de que pouco ou nada significam essas métricas e que são normalmente fabricadas simplesmente para acolher a norma A ou B de um qualquer processo de qualidade.

Mas voltemos ao inicio: esta frase é retirada do livro "Controling Software Projects: Management, Measurement and Estimation" escrito pelo Sr. Tom DeMarco em 1982. Este livro é uma referência e muitas das suas recomendações ou práticas são utilizadas em gestão de projectos de desenvolvimento de software. Então mas, e se de repente o Sr. DeMarco viesse dizer que, afinal, se calhar as coisas não são bem assim? Que a construção de software não pode ser comparada com as engenharias clássicas e que este tipo de controle exacerbado apenas serve para castrar toda e qualquer possibilidade de criar software inovador e com real valor acrescentado? UOOWWWW??!?!?

Pois é… Aconselho vivamente a leitura do artigo que está publicado no site do IEEE Computer Society. O pdf pode ser descarregado aqui.

Este artigo tem causado alguma polémica por esse mundo fora, basta ver por exemplo a quantidade de comentários ao este artigo de Jeff Atwood no seu fantástico blog Coding Horror.

quinta-feira, 5 de fevereiro de 2009

DevDays 2009

Nos próximos dias 18 e 19 de Fevereiro no campus do Taguspark. Evento para programadores, designers, arquitectos e todos aqueles que criam soluções em plataformas Microsoft.

Eu vou lá estar. Quem me quiser encontrar é só procurar junto das sessões sobre .Net e C# 4.0, Windows Azure, Team System e nos tópicos de arquitectura em geral. A inscrição são 100€, valor muito em conta para um evento de dois dias com almoço e lanches incluídos e a oportunidade de escutar de perto alguns gurus da actualidade. Vai a http://www.devdays09.com e inscreve-te. Vemo-nos por lá!

terça-feira, 3 de junho de 2008

Parallel Extensions June 2008 CTP

Está disponível para download a CTP 2008 da Parallel Extensions. Há já algum tempo que venho a utilizar a versão anterior de Dez07 (inclusive em algum código de produção) sem grandes problemas. Para quem não conhece, aconselho vivamente a experimentar. Esta API não nos trás nada que não fosse possível fazer antes, trás sim uma simplicidade fantástica em tirar partido de hardware multi-core.

Penso que estamos à beira de uma grande revolução no modo de pensar e estruturar algoritmos. Tal como educámos o nosso modo de pensar de um modo sequencial e estruturado para um modo orientado a objectos, é tempo de educarmos o nosso pensamento para muti-processo. Quando desenvolvemos um algoritmo temos de pensar logo à partida nas dependências e nos blocos que são ou não dependentes e que podem ou não ser executados de modo assíncrono. Tal como disse atrás não é nada de novo mas a implementação era mais complexa e na maior parte dos casos não havia necessidade de complicar. A democratização do hardware multi-processador / multi-core e a simplicidade que nos trás esta API torna esta tecnologia acessível a um leque muito maior de situações do dia-a-dia.