Оптимизация агрегирования для конкатенации строк

Обновить - для тех, кто имеет преувеличенное настроение, вы можете предположить, что Aggregate все равно производит нормальный результат, независимо от того, какая функция передана ему, в том числе в случае оптимизации.

Я написал эту программу для создания длинной строки целых чисел от 0 до 19999 по запятой.

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

Когда я запустил его, он говорит:

5116ms

Более пяти секунд, ужасно. Конечно, это потому, что вся строка копируется каждый раз вокруг цикла.

Но что, если сделать одно очень небольшое изменение, указанное комментарием?

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

Теперь, когда я запустил его, он говорит:

42ms

Более 100 раз быстрее.

Вопрос

Что в пространстве имен MakeAggregateGoFaster?

Обновление 2: Написал мой ответ здесь.

Ответ 1

Вы "переопределяете" System.Linq.Aggregate своим собственным методом расширения в пространстве имен MakeAggregateGoFaster.

Возможно, специализируется на IEnumerable<string> и использует StringBuilder?

Может быть, вместо Func<string, string, string> взять Expression<Func<string, string, string>>, чтобы он мог анализировать дерево выражений и компилировать код, который использует StringBuilder вместо прямого вызова функции?

Просто гадать.

Ответ 2

Почему бы не использовать одну из других форм агрегата?

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

Вы можете указать любой тип для вашего семени, выполнить любое форматирование или пользовательские вызовы в первой функции лямбда, а затем настроить тип вывода во второй лямбда-функции. Встроенные функции уже обеспечивают необходимую гибкость. Мои трассы шли от 1444 мс до 6 мс.

Ответ 3

Не отвечая на вопрос, но я думаю, что стандартные шаблоны здесь должны использовать StringBuilder или string.Join:

string.join(", ",Enumerable.Range(0, size).Select(n => n.ToString()).ToArray())

Ответ 4

Причина, по которой я спросил, была ли она головоломкой, заключалась в том, что головоломка позволяет в любой степени жертвовать робастностью, если она удовлетворяет букве указанной проблемы. Имея это в виду, здесь говорится:

Решение 1 (выполняется мгновенно, проблема не проверяется):

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

Решение 2 (работает так же быстро, как требуется, но игнорирует делегат полностью):

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

Ответ 5

Ну, это будет целиком зависеть от того, какой код находится в пространстве имен MageAggregateGoFaster, не так ли?

Это пространство имен не является частью среды выполнения .NET, поэтому вы связались с каким-то специальным кодом.

Лично я бы подумал, что что-то, что распознает конкатенацию строк или подобное, и создает список или аналогичный, затем выделяет один большой StringBuilder и использует Append.

Грязное решение будет:

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

грязный, потому что этот код, делая то, что вы говорите, испытываете с вашей программой, вообще не использует делегат функции. Однако это сократит время выполнения от 2800 мс до 11 мс на моем компьютере и все равно даст те же результаты.

Теперь, в следующий раз, возможно, вы должны задать реальный вопрос вместо того, чтобы просто выглядеть, насколько я умный, я типа избиения груди?