Otimizando Aggregate para concatenação de string

votos
18

Atualização - para aqueles de um quadro jocoso de espírito, você pode assumir que agregam ainda produz o resultado normal qualquer função é passado para ele, inclusive no caso de ser otimizado.

Eu escrevi este programa para construir uma longa seqüência de números inteiros de 0 a 19999 separados por vírgulas.

using System;
using System.Linq;
using System.Diagnostics;

namespace ConsoleApplication5
{
    class Program
    {
        static void Main(string[] args)
        {
            const int size = 20000;

            Stopwatch stopwatch = new Stopwatch();

            stopwatch.Start();
            Enumerable.Range(0, size).Select(n => n.ToString()).Aggregate((a, b) => a + ,  + b);
            stopwatch.Stop();

            Console.WriteLine(stopwatch.ElapsedMilliseconds + ms);
        }
    }
}

Quando eu executá-lo, ele diz:

5116ms

Durante cinco segundos, terrível. É claro que é porque a seqüência inteira está sendo copiado cada vez em torno do laço.

Mas o que se fazer uma mudança muito pequena indicado pelo comentário?

using System;
using System.Linq;
using System.Diagnostics;

namespace ConsoleApplication5
{
    using MakeAggregateGoFaster;  // <---- inserted this

    class Program
    {
        static void Main(string[] args)
        {
            const int size = 20000;

            Stopwatch stopwatch = new Stopwatch();

            stopwatch.Start();
            Enumerable.Range(0, size).Select(n => n.ToString()).Aggregate((a, b) => a + ,  + b);
            stopwatch.Stop();

            Console.WriteLine(stopwatch.ElapsedMilliseconds + ms);
        }
    }
}

Agora, quando eu executá-lo, ele diz:

42ms

Ao longo de 100x mais rápido.

Questão

O que está no namespace MakeAggregateGoFaster?

Update 2: Escrevi a minha resposta aqui .

Publicado 10/12/2008 em 00:12
fonte usuário
Em outras línguas...                            


5 respostas

votos
40

Por que não usar uma das outras formas de agregado?

Enumerable.Range(0, size ).Aggregate(new StringBuilder(),
        (a, b) => a.Append(", " + b.ToString()),
        (a) => a.Remove(0,2).ToString());

Você pode especificar qualquer tipo para a sua semente, executar qualquer chamadas de formatação ou personalizados são necessários na primeira função lambda e personalizar o tipo de saída na segunda função lambda. O construído em recursos já fornecem a flexibilidade que você precisa. Minhas corridas foi de 1444ms para 6ms.

Respondeu 14/01/2009 em 18:18
fonte usuário

votos
15

Você está 'substituir' System.Linq.Aggregate com seu próprio método de extensão em MakeAggregateGoFaster namespace.

Talvez especializada em IEnumerable<string>e fazendo uso de um StringBuilder?

Talvez tomar um Expression<Func<string, string, string>>em vez de um Func<string, string, string>modo que pode analisar a árvore de expressão e compilar um código que usa StringBuilder em vez de chamar a função diretamente?

Apenas adivinhando.

Respondeu 10/12/2008 em 00:30
fonte usuário

votos
5

Não responder à pergunta, mas acho que os padrões normais aqui são para usar StringBuilder ou String.Join:

string.join(", ",Enumerable.Range(0, size).Select(n => n.ToString()).ToArray())
Respondeu 10/12/2008 em 00:16
fonte usuário

votos
4

A razão que eu perguntei se era um quebra-cabeça foi porque um quebra-cabeça é permitido sacrificar robustez em graus variados, desde que satisfaça a letra do problema exposto. Com isso em mente, aqui vai:

Solução 1 (funciona instantaneamente, problema não valida):

public static string Aggregate(this IEnumerable<string> l, Func<string, string, string> f) {
     return "";
}

Solução 2 (funciona quase tão rápido quanto o problema exige, mas ignora o delegado completamente):

public static string Aggregate(this IEnumerable<string> l, Func<string, string, string> f) {
    StringBuilder sb = new StringBuilder();
    foreach (string item in l)
        sb.Append(", ").Append(item);
    return sb.Remove(0,2).ToString();
}
Respondeu 10/12/2008 em 00:35
fonte usuário

votos
3

Bem, isso depende inteiramente o que o código está no namespace MageAggregateGoFaster agora não é?

Este namespace não é parte do .NET runtime, então você ligada em algum código personalizado.

Pessoalmente eu gostaria de pensar que algo que reconhece concatenação ou similar, e constrói uma lista, ou similar, em seguida, aloca uma grande StringBuilder e usa Anexar.

A solução suja seria:

namespace MakeAggregateGoFaster
{
    public static class Extensions
    {
        public static String Aggregate(this IEnumerable<String> source, Func<String, String, String> fn)
        {
            StringBuilder sb = new StringBuilder();
            foreach (String s in source)
            {
                if (sb.Length > 0)
                    sb.Append(", ");
                sb.Append(s);
            }

            return sb.ToString();
        }
    }
}

sujo porque este código, ao fazer o que você diz que você experimentar com seu programa, não usa o delegado função em tudo. Será, no entanto, reduzir o tempo de execução de todo 2800ms para 11ms no meu computador, e ainda produzir os mesmos resultados.

Agora, da próxima vez, talvez você deve fazer uma pergunta real em vez de apenas olhar o quão inteligente eu sou tipo de batendo no peito?

Respondeu 10/12/2008 em 00:15
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more