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

голоса
18

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

Я написал эту программу, чтобы построить длинную строку целых чисел от 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

За 100x быстрее.

Вопрос

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

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

Задан 10/12/2008 в 00:12
источник пользователем
На других языках...                            


5 ответов

голоса
40

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

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

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

Ответил 14/01/2009 в 18:18
источник пользователем

голоса
15

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

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

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

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

Ответил 10/12/2008 в 00:30
источник пользователем

голоса
5

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

string.join(", ",Enumerable.Range(0, size).Select(n => n.ToString()).ToArray())
Ответил 10/12/2008 в 00:16
источник пользователем

голоса
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();
}
Ответил 10/12/2008 в 00:35
источник пользователем

голоса
3

Ну, это будет зависеть исключительно от того, что код находится в пространстве имен 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();
        }
    }
}

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

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

Ответил 10/12/2008 в 00:15
источник пользователем

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