Оптимизация агрегата для конкатенации строк
Обновлять - для тех, кто настроен шутливо, вы можете предположить, что 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:Написал здесь свой ответ.
Причина, по которой я отложил это, заключается в том, что вы дали нам «Эй, как я сделал это быстрее», не сообщая нам кода; что привело к тому, что «я мог бы сделать дюжину разных вещей, чтобы ускорить это». Или: «Это умная головоломка, и я хочу, чтобы вы ее решили» - и то, и другое не подходит для Stack Overflow.
Ответы 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 мс и по-прежнему даст те же результаты.
Теперь, в следующий раз, возможно, вам стоит задать реальный вопрос, а не просто битье в грудь типа посмотри, какой я умный?
Не отвечу на вопрос, но я думаю, что стандартные шаблоны здесь используют StringBuilder или string.Join:
string.Join(", ",Enumerable.Range(0, size).Select(n => n.ToString()).ToArray())
Я только что рассчитал время, и похоже, что если (размер> 1000000) моя версия будет быстрее (конечно, с добавленным оператором using).
string.join должен быть string.Join
Вы "переопределяете" System.Linq.Aggregate своим собственным методом расширения в пространстве имен MakeAggregateGoFaster.
Возможно, вы специализируетесь на IEnumerable<string> и используете StringBuilder?
Может быть, взять Expression<Func<string, string, string>> вместо Func<string, string, string>, чтобы он мог анализировать дерево выражений и скомпилировать код, который использует StringBuilder вместо прямого вызова функции?
Просто догадываюсь.
Причина, по которой я спросил, была ли это головоломка, заключалась в том, что головоломке разрешается жертвовать надежностью в той или иной степени, если она соответствует букве поставленной задачи. Имея это в виду, вот что:
Решение 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();
}
Почему бы не использовать одну из других форм агрегирования?
Enumerable.Range(0, size ).Aggregate(new StringBuilder(),
(a, b) => a.Append(", " + b.ToString()),
(a) => a.Remove(0,2).ToString());
Вы можете указать любой тип для своего семени, выполнить любое форматирование или пользовательские вызовы, необходимые в первой лямбда-функции, а затем настроить тип вывода во второй лямбда-функции. Встроенные функции уже обеспечивают необходимую гибкость. Мои пробежки увеличились с 1444 мс до 6 мс.
Я не знаю почему, но мне пришлось добавить нулевую проверку для b в вашем примере, чтобы заставить его работать: .Aggregate(new StringBuilder(), (a, b) => a.Append("\n" + (b == null ? "" : b.ToString())), (a) => a.Remove(0, 2).ToString());
что ты спрашиваешь? вы написали MakeAggregateGoFaster и это загадка?