Optimización del agregado para la concatenación de cadenas

votos
18

Actualización : para aquellos con un estado de ánimo divertido, puede suponer que Aggregate aún produce el resultado normal independientemente de la función que se le pase, incluso en el caso que se está optimizando.

Escribí este programa para construir una larga cadena de enteros de 0 a 19999 separados por comas.

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);
        }
    }
}

Cuando lo ejecuto, dice:

5116ms

Más de cinco segundos, terrible. Por supuesto, es porque toda la cadena se está copiando cada vez que pasa el ciclo.

Pero, ¿qué pasa si se hace un cambio muy pequeño indicado por el comentario?

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);
        }
    }
}

Ahora cuando lo ejecuto, dice:

42ms

Más de 100 veces más rápido.

Pregunta

¿Qué hay en el espacio de nombres MakeAggregateGoFaster?

Actualización 2: escribí mi respuesta aquí .

Publicado el 10/12/2008 a las 00:12
fuente por usuario
En otros idiomas...                            


5 respuestas

votos
40

¿Por qué no usar una de las otras formas de Agregado?

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

Puede especificar cualquier tipo para su semilla, realizar el formateo o las llamadas personalizadas necesarias en la primera función lambda y luego personalizar el tipo de salida en la segunda función lambda. Las funciones integradas ya proporcionan la flexibilidad que necesita. Mis carreras pasaron de 1444ms a 6ms.

Respondida el 14/01/2009 a las 18:18
fuente por usuario

votos
15

Está 'sustituyendo' a System.Linq.Aggregate con su propio método de extensión en el espacio de nombres MakeAggregateGoFaster.

Quizás especializado IEnumerable<string>y haciendo uso de un StringBuilder?

¿Tal vez tomar un en Expression<Func<string, string, string>>lugar de uno Func<string, string, string>para que pueda analizar el árbol de expresiones y compilar algún código que use StringBuilder en lugar de llamar directamente a la función?

Solo adivinando.

Respondida el 10/12/2008 a las 00:30
fuente por usuario

votos
5

No respondiendo la pregunta, pero creo que los patrones estándar aquí son para usar StringBuilder o string.Join:

string.join(", ",Enumerable.Range(0, size).Select(n => n.ToString()).ToArray())
Respondida el 10/12/2008 a las 00:16
fuente por usuario

votos
4

La razón por la que pregunté si se trataba de un acertijo era porque se permite que un acertijo sacrifique la solidez en diversos grados, siempre que satisfaga la letra del problema establecido. Con eso en mente, aquí va:

Solución 1 (se ejecuta instantáneamente, el problema no valida):

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

Solución 2 (se ejecuta tan rápido como el problema lo requiera, pero ignora por completo al delegado):

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();
}
Respondida el 10/12/2008 a las 00:35
fuente por usuario

votos
3

Bueno, eso dependería completamente de qué código está en el espacio de nombres MageAggregateGoFaster, ¿no es así?

Este espacio de nombres no es parte del tiempo de ejecución de .NET, por lo que ha vinculado algún código personalizado.

Personalmente, creo que algo que reconoce la concatenación de cadenas o similar, y crea una lista, o similar, luego asigna un gran StringBuilder y usa Append.

Una solución sucia sería:

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();
        }
    }
}

sucio porque este código, mientras hace lo que dice que experimenta con su programa, no usa la función delegar en absoluto. Sin embargo, reducirá el tiempo de ejecución de alrededor de 2800ms a 11ms en mi computadora, y aún producirá los mismos resultados.

Ahora, la próxima vez, tal vez deberías hacer una pregunta real en lugar de solo mirar lo inteligente que soy el tipo de paliza en el pecho.

Respondida el 10/12/2008 a las 00:15
fuente por usuario

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