Algoritmo agregado LINQ explicado

722

Isso pode parecer ridículo, mas não consegui encontrar uma explicação realmente boa sobre Aggregate .

Bom significa curto, descritivo, abrangente, com um exemplo pequeno e claro.

Alexander Beletsky
fonte

Respostas:

1015

A definição mais fácil de entender de Aggregate é que ela executa uma operação em cada elemento da lista, levando em consideração as operações anteriores. Ou seja, ele executa a ação no primeiro e no segundo elemento e leva o resultado adiante. Em seguida, opera no resultado anterior e no terceiro elemento e leva adiante. etc.

Exemplo 1. Somando números

var nums = new[]{1,2,3,4};
var sum = nums.Aggregate( (a,b) => a + b);
Console.WriteLine(sum); // output: 10 (1+2+3+4)

Isso adiciona 1e 2faz 3. Em seguida, adiciona 3(resultado do anterior) e 3(próximo elemento em sequência) a fazer 6. Então adiciona 6e 4faz 10.

Exemplo 2. Crie um CSV a partir de uma matriz de strings

var chars = new []{"a","b","c", "d"};
var csv = chars.Aggregate( (a,b) => a + ',' + b);
Console.WriteLine(csv); // Output a,b,c,d

Isso funciona da mesma maneira. Concatene auma vírgula e bfaça a,b. Em seguida, concatena a,b com uma vírgula e cfazer a,b,c. e assim por diante.

Exemplo 3. Multiplicando números usando uma semente

Para completar, há uma sobrecarga de Aggregateque tem um valor de semente.

var multipliers = new []{10,20,30,40};
var multiplied = multipliers.Aggregate(5, (a,b) => a * b);
Console.WriteLine(multiplied); //Output 1200000 ((((5*10)*20)*30)*40)

Muito parecido com os exemplos acima, isso começa com um valor de 5e o multiplica pelo primeiro elemento da sequência que 10fornece um resultado de 50. Este resultado é transportado e multiplicado pelo próximo número na sequência 20para obter um resultado de 1000. Isso continua pelos 2 elementos restantes da sequência.

Exemplos ao vivo: http://rextester.com/ZXZ64749
Documentos: http://msdn.microsoft.com/en-us/library/bb548651.aspx


Termo aditivo

O exemplo 2, acima, usa concatenação de cadeias para criar uma lista de valores separados por vírgula. Esta é uma maneira simplista de explicar o uso de Aggregatequal era a intenção desta resposta. No entanto, se usar esta técnica para criar uma grande quantidade de dados separados por vírgula, seria mais apropriado usar ae StringBuilderisso é totalmente compatível com o Aggregateuso da sobrecarga propagada para iniciar o StringBuilder.

var chars = new []{"a","b","c", "d"};
var csv = chars.Aggregate(new StringBuilder(), (a,b) => {
    if(a.Length>0)
        a.Append(",");
    a.Append(b);
    return a;
});
Console.WriteLine(csv);

Exemplo atualizado: http://rextester.com/YZCVXV6464

Jamiec
fonte
11
Outra explicação para a primeira descrição é que a função que você fornece sempre combina os dois primeiros membros até que a matriz seja reduzida a um elemento. Assim [1,2,3,4]será [3,3,4], em seguida, [6,4]e, finalmente [10]. Mas, em vez de retornar uma matriz de um único valor, você obtém o próprio valor.
David Raab
2
Posso interromper / sair antecipadamente de uma função agregada? Por exemplo, chars.Aggregate ((a, b) => {if (a == 'a') quebra todo o agregado, retornando a + ',' + b})
Jeff Tian
13
@ Jeffffian - eu sugeriria encadear um TakeWhileentão Aggregatee isso é o beatuty de extensões Enumerable - elas são facilmente encadeadas. Então você acaba com TakeWhile(a => a == 'a').Aggregate(....). Veja este exemplo: rextester.com/WPRA60543
Jamiec
2
Como uma nota de rodapé no adendo, todo o bloco pode ser facilmente substituído por var csv = string.Join(",", chars)(sem necessidade de agregadores ou construtores de string) - mas sim, eu sei que o ponto da resposta era dar um exemplo de uso de agregados para que seja legal. Mas eu ainda queria mencionar que não é recomendado para cordas acaba de entrar, já existe um método dedicado para isso ....
T_d
2
Outro uso comum (até agora o único Eu vi mesmo no código de produção) é obter mínimo ou máximo de itens comovar biggestAccount = Accounts.Aggregate((a1, a2) => a1.Amount >= a2.Amount ? a1 : a2);
Franck
133

Depende parcialmente de qual sobrecarga você está falando, mas a idéia básica é:

  • Comece com uma semente como o "valor atual"
  • Iterar sobre a sequência. Para cada valor na sequência:
    • Aplique uma função especificada pelo usuário para se transformar (currentValue, sequenceValue)em(nextValue)
    • Conjunto currentValue = nextValue
  • Retornar a final currentValue

Você pode achar útil o Aggregatepost na minha série Edulinq - ele inclui uma descrição mais detalhada (incluindo as várias sobrecargas) e implementações.

Um exemplo simples é usar Aggregatecomo alternativa a Count:

// 0 is the seed, and for each item, we effectively increment the current value.
// In this case we can ignore "item" itself.
int count = sequence.Aggregate(0, (current, item) => current + 1);

Ou talvez somando todos os comprimentos de cadeias em uma sequência de cadeias:

int total = sequence.Aggregate(0, (current, item) => current + item.Length);

Pessoalmente, raramente acho Aggregateútil - os métodos de agregação "personalizados" geralmente são bons o suficiente para mim.

Jon Skeet
fonte
6
@ Jon Existem variações assíncronas do agregado que dividem os itens em uma árvore para que o trabalho possa ser dividido entre os núcleos? Parece que o design do método é consistente com os conceitos de "reduzir" ou "dobrar", mas não sei se realmente está fazendo isso sob o capô, ou simplesmente percorrendo a lista de itens.
#
@ Jon: o edulink mencionado acima não está funcionando, você pode me redirecionar para o link certo. E você pode ser mais específico sobre o termo funções de agregação "personalizadas" que você usou em sua resposta.
Koushik
1
@ Koushik: Corrigi o link no post. Por funções de agregação "personalizadas", quero dizer coisas como Max / Min / Count / Sum.
Jon Skeet
62

O agregado super curto funciona como uma dobra em Haskell / ML / F #.

Um pouco mais .Max (), .Min (), .Sum (), .Average () todos iteram sobre os elementos em uma sequência e os agregam usando a respectiva função agregada. .Aggregate () é um agregador generalizado, pois permite ao desenvolvedor especificar o estado inicial (também conhecido como seed) e a função agregada.

Eu sei que você pediu uma breve explicação, mas achei que os outros deram algumas respostas curtas. Achei que talvez você se interessasse por uma mais longa.

Versão longa com código Uma maneira de ilustrar o que pode ser mostrado como você implementa o Desvio Padrão de Amostra uma vez usando o foreach e outra vez o .Aggregate. Nota: Não priorizei o desempenho aqui, por isso itero várias vezes desnecessariamente na coleção

Primeiro, uma função auxiliar usada para criar uma soma de distâncias quadráticas:

static double SumOfQuadraticDistance (double average, int value, double state)
{
    var diff = (value - average);
    return state + diff * diff;
}

Em seguida, faça uma amostra do desvio padrão usando o ForEach:

static double SampleStandardDeviation_ForEach (
    this IEnumerable<int> ints)
{
    var length = ints.Count ();
    if (length < 2)
    {
        return 0.0;
    }

    const double seed = 0.0;
    var average = ints.Average ();

    var state = seed;
    foreach (var value in ints)
    {
        state = SumOfQuadraticDistance (average, value, state);
    }
    var sumOfQuadraticDistance = state;

    return Math.Sqrt (sumOfQuadraticDistance / (length - 1));
}

Em seguida, uma vez usando .Aggregate:

static double SampleStandardDeviation_Aggregate (
    this IEnumerable<int> ints)
{
    var length = ints.Count ();
    if (length < 2)
    {
        return 0.0;
    }

    const double seed = 0.0;
    var average = ints.Average ();

    var sumOfQuadraticDistance = ints
        .Aggregate (
            seed,
            (state, value) => SumOfQuadraticDistance (average, value, state)
            );

    return Math.Sqrt (sumOfQuadraticDistance / (length - 1));
}

Observe que essas funções são idênticas, exceto por como calcula sumOfQuadraticDistance:

var state = seed;
foreach (var value in ints)
{
    state = SumOfQuadraticDistance (average, value, state);
}
var sumOfQuadraticDistance = state;

Versus:

var sumOfQuadraticDistance = ints
    .Aggregate (
        seed,
        (state, value) => SumOfQuadraticDistance (average, value, state)
        );

Então, o que .Aggregate faz é que ele encapsula esse padrão agregador e eu espero que a implementação de .Aggregate seja algo parecido com isto:

public static TAggregate Aggregate<TAggregate, TValue> (
    this IEnumerable<TValue> values,
    TAggregate seed,
    Func<TAggregate, TValue, TAggregate> aggregator
    )
{
    var state = seed;

    foreach (var value in values)
    {
        state = aggregator (state, value);
    }

    return state;
}

O uso das funções de desvio padrão seria algo como isto:

var ints = new[] {3, 1, 4, 1, 5, 9, 2, 6, 5, 4};
var average = ints.Average ();
var sampleStandardDeviation = ints.SampleStandardDeviation_Aggregate ();
var sampleStandardDeviation2 = ints.SampleStandardDeviation_ForEach ();

Console.WriteLine (average);
Console.WriteLine (sampleStandardDeviation);
Console.WriteLine (sampleStandardDeviation2);

Na minha humilde opinião

Então. Agregado ajuda a legibilidade? Em geral, eu amo o LINQ porque acho que .Onde, .Select, .OrderBy e assim por diante ajudam bastante a legibilidade (se você evitar. O agregado precisa estar no Linq por motivos de integridade, mas, pessoalmente, não estou tão convencido de que o.

Apenas mais um metaprogramador
fonte
+1 Excelente! Mas os métodos de extensão SampleStandardDeviation_Aggregate()e SampleStandardDeviation_ForEach()não pode ser private(por padrão na ausência de um qualificador de acesso), então deve ter sido acumulados por um ou outro publicou internal, parece-me
Fulproof
FYI: Se bem me lembro, os métodos de extensão em minha amostra faziam parte da mesma classe que os usava ==> trabalhos particulares neste caso.
Apenas outro metaprogramador
39

Uma imagem vale mais que mil palavras

Lembrete:
Func<X, Y, R>é uma função com duas entradas do tipo Xe Y, que retorna um resultado do tipo R.

Enumerable.Aggregate tem três sobrecargas:


Sobrecarga 1:

A Aggregate<A>(IEnumerable<A> a, Func<A, A, A> f)

Agregado1

Exemplo:

new[]{1,2,3,4}.Aggregate((x, y) => x + y);  // 10


Essa sobrecarga é simples, mas possui as seguintes limitações:

  • a sequência deve conter pelo menos um elemento,
    caso contrário , a função lançará um InvalidOperationException.
  • elementos e resultado devem ser do mesmo tipo.



Sobrecarga 2:

B Aggregate<A, B>(IEnumerable<A> a, B bIn, Func<B, A, B> f)

Agregado2

Exemplo:

var hayStack = new[] {"straw", "needle", "straw", "straw", "needle"};
var nNeedles = hayStack.Aggregate(0, (n, e) => e == "needle" ? n+1 : n);  // 2


Essa sobrecarga é mais geral:

  • um valor inicial deve ser fornecido ( bIn).
  • a coleção pode estar vazia,
    nesse caso, a função produzirá o valor de semente como resultado.
  • elementos e resultado podem ter tipos diferentes.



Sobrecarga 3:

C Aggregate<A,B,C>(IEnumerable<A> a, B bIn, Func<B,A,B> f, Func<B,C> f2)


A terceira sobrecarga não é muito útil para IMO.
O mesmo pode ser escrito de forma mais sucinta usando a sobrecarga 2 seguida por uma função que transforma seu resultado.


As ilustrações são adaptadas deste excelente post no blog .

3dGrabber
fonte
Essa seria uma ótima resposta ... sobre uma pergunta sobre Haskel. Mas não há sobrecarga de Aggegate.net que leva a Func<T, T, T>.
Jamiec
4
Sim existe . Você o usa em sua própria resposta!
3dGrabber
1
Voto positivo porque você descreve cuidadosamente o que acontece quando a sequência está vazia. Seja N o número de elementos na fonte. Observamos que a sobrecarga que não leva a seedaplica a função acumuladora N -1 vezes; enquanto as outras sobrecargas (que não levam a seed) aplicar a função de acumulador N vezes.
Jeppe Stig Nielsen
17

O agregado é basicamente usado para agrupar ou resumir dados.

De acordo com o MSDN "Função agregada Aplica uma função acumuladora em uma sequência".

Exemplo 1: Adicione todos os números em uma matriz.

int[] numbers = new int[] { 1,2,3,4,5 };
int aggregatedValue = numbers.Aggregate((total, nextValue) => total + nextValue);

* important: O valor agregado inicial por padrão é o elemento 1 na sequência da coleção. ou seja: o valor inicial total da variável será 1 por padrão.

explicação da variável

total: manterá o valor total (valor agregado) retornado pela função.

nextValue: é o próximo valor na sequência da matriz. Este valor é então adicionado ao valor agregado, ou seja, total.

Exemplo 2: adicione todos os itens em uma matriz. Defina também o valor inicial do acumulador para começar a adicionar a partir de 10.

int[] numbers = new int[] { 1,2,3,4,5 };
int aggregatedValue = numbers.Aggregate(10, (total, nextValue) => total + nextValue);

explicação dos argumentos:

o primeiro argumento é o inicial (valor inicial, ou seja, valor inicial) que será usado para iniciar a adição com o próximo valor na matriz.

o segundo argumento é uma função que é uma função que leva 2 int.

1.total: será o mesmo que antes do valor total (valor agregado) retornado pela função após o cálculo.

2.nextValue:: é o próximo valor na sequência da matriz. Este valor é então adicionado ao valor agregado, ou seja, total.

A depuração desse código também fornecerá uma melhor compreensão de como o trabalho agregado.

maxspan
fonte
7

Aprendi muito com a resposta de Jamiec .

Se a única necessidade é gerar uma sequência CSV, você pode tentar isso.

var csv3 = string.Join(",",chars);

Aqui está um teste com 1 milhão de strings

0.28 seconds = Aggregate w/ String Builder 
0.30 seconds = String.Join 

O código fonte está aqui

Rm558
fonte
Quando executei o mesmo código no dotnetfiddle.net, conforme fornecido no link, recebi "Erro fatal: o limite de uso de memória foi excedido" para "string.Join", mas o Aggregate sempre funcionou conforme o esperado. Então eu acredito que isso não é recomendado o uso String.Join
Manish Jain
Estranho? Quando comentei o primeiro cronômetro, que era para o agregado; então não estou recebendo nenhum "Erro fatal: o limite de uso de memória foi excedido". Por favor explique! Link: dotnetfiddle.net/6YyumS
Manish Jain
dotnetfiddle.net tem um limite de memória ao atingir a parada de execução. se você mover o código agregado antes do código String.Join, poderá receber um erro ao agregar.
Rm558
7

Além de todas as ótimas respostas aqui, eu também o usei para guiar um item por uma série de etapas de transformação.

Se uma transformação for implementada como a Func<T,T>, você poderá adicionar várias transformações a List<Func<T,T>>e usar Aggregatepara percorrer uma instância de Tcada etapa.

Um exemplo mais concreto

Você deseja obter um stringvalor e orientá-lo por uma série de transformações de texto que podem ser construídas programaticamente.

var transformationPipeLine = new List<Func<string, string>>();
transformationPipeLine.Add((input) => input.Trim());
transformationPipeLine.Add((input) => input.Substring(1));
transformationPipeLine.Add((input) => input.Substring(0, input.Length - 1));
transformationPipeLine.Add((input) => input.ToUpper());

var text = "    cat   ";
var output = transformationPipeLine.Aggregate(text, (input, transform)=> transform(input));
Console.WriteLine(output);

Isso criará uma cadeia de transformações: Remova os espaços iniciais e finais -> remova o primeiro caractere -> remova o último caractere -> converta para maiúsculas. As etapas dessa cadeia podem ser adicionadas, removidas ou reordenadas conforme necessário, para criar qualquer tipo de pipeline de transformação necessário.

O resultado final desse pipeline específico é o que " cat "se torna "A".


Isso pode se tornar muito poderoso quando você perceber que Tpode ser qualquer coisa . Isso pode ser usado para transformações de imagem, como filtros, usando BitMapcomo exemplo;

Bradley Uffner
fonte
4

Definição

O método agregado é um método de extensão para coleções genéricas. O método agregado aplica uma função a cada item de uma coleção. Não apenas aplica uma função, mas leva seu resultado como valor inicial para a próxima iteração. Portanto, como resultado, obteremos um valor calculado (min, max, avg ou outro valor estatístico) de uma coleção.

Portanto, o método agregado é uma forma de implementação segura de uma função recursiva.

Seguro , porque a recursão irá percorrer cada item de uma coleção e não podemos obter nenhuma suspensão de loop infinito por condição de saída incorreta. Recursivo , porque o resultado da função atual é usado como parâmetro para a próxima chamada de função.

Sintaxe:

collection.Aggregate(seed, func, resultSelector);
  • semente - valor inicial por padrão;
  • func - nossa função recursiva. Pode ser uma expressão lambda, um representante Func ou um tipo de função TF (T result, T nextValue);
  • resultSelector - pode ser uma função como func ou uma expressão para calcular, transformar, alterar, converter o resultado final.

Como funciona:

var nums = new[]{1, 2};
var result = nums.Aggregate(1, (result, n) => result + n); //result = (1 + 1) + 2 = 4
var result2 = nums.Aggregate(0, (result, n) => result + n, response => (decimal)response/2.0); //result2 = ((0 + 1) + 2)*1.0/2.0 = 3*1.0/2.0 = 3.0/2.0 = 1.5

Uso prático:

  1. Encontre o fatorial a partir de um número n:

int n = 7;
var numbers = Enumerable.Range(1, n);
var factorial = numbers.Aggregate((result, x) => result * x);

que está fazendo a mesma coisa que esta função:

public static int Factorial(int n)
{
   if (n < 1) return 1;

   return n * Factorial(n - 1);
}
  1. Aggregate () é um dos métodos de extensão LINQ mais poderosos, como Select () e Where (). Podemos usá-lo para substituir Sum (), Min (). Funcionalidade Max (), Avg () ou para alterá-la implementando o contexto de adição:
    var numbers = new[]{3, 2, 6, 4, 9, 5, 7};
    var avg = numbers.Aggregate(0.0, (result, x) => result + x, response => (double)response/(double)numbers.Count());
    var min = numbers.Aggregate((result, x) => (result < x)? result: x);
  1. Uso mais complexo dos métodos de extensão:
    var path = @“c:\path-to-folder”;

    string[] txtFiles = Directory.GetFiles(path).Where(f => f.EndsWith(“.txt”)).ToArray<string>();
    var output = txtFiles.Select(f => File.ReadAllText(f, Encoding.Default)).Aggregate<string>((result, content) => result + content);

    File.WriteAllText(path + summary.txt”, output, Encoding.Default);

    Console.WriteLine(“Text files merged into: {0}”, output); //or other log info
YuriUn
fonte
Muito boa primeira resposta. Bem feito! Vergonha é uma pergunta tão velho ou você tem muita upvotes
Jamiec
1

Esta é uma explicação sobre o uso Aggregateem uma API do Fluent, como a Classificação Linq.

var list = new List<Student>();
var sorted = list
    .OrderBy(s => s.LastName)
    .ThenBy(s => s.FirstName)
    .ThenBy(s => s.Age)
    .ThenBy(s => s.Grading)
    .ThenBy(s => s.TotalCourses);

e vamos ver que queremos implementar uma função de classificação que utilize um conjunto de campos, isso é muito fácil de usar, em Aggregatevez de um loop for, como este:

public static IOrderedEnumerable<Student> MySort(
    this List<Student> list,
    params Func<Student, object>[] fields)
{
    var firstField = fields.First();
    var otherFields = fields.Skip(1);

    var init = list.OrderBy(firstField);
    return otherFields.Skip(1).Aggregate(init, (resultList, current) => resultList.ThenBy(current));
}

E podemos usá-lo assim:

var sorted = list.MySort(
    s => s.LastName,
    s => s.FirstName,
    s => s.Age,
    s => s.Grading,
    s => s.TotalCourses);
Jaider
fonte
1

Todo mundo deu sua explicação. Minha explicação é assim.

O método agregado aplica uma função a cada item de uma coleção. Por exemplo, vamos ter a coleção {6, 2, 8, 3} e a função Add (operator +) que ele faz (((6 + 2) +8) +3) e retorna 19

var numbers = new List<int> { 6, 2, 8, 3 };
int sum = numbers.Aggregate(func: (result, item) => result + item);
// sum: (((6+2)+8)+3) = 19

Neste exemplo, é passado o método chamado Add em vez da expressão lambda.

var numbers = new List<int> { 6, 2, 8, 3 };
int sum = numbers.Aggregate(func: Add);
// sum: (((6+2)+8)+3) = 19

private static int Add(int x, int y) { return x + y; }
bizimunda
fonte
0

Uma definição curta e essencial pode ser essa: o método de extensão Linq Aggregate permite declarar um tipo de função recursiva aplicada aos elementos de uma lista, cujos operandos são dois: os elementos na ordem em que estão presentes na lista, um elemento de cada vez e o resultado da iteração recursiva anterior ou nada, se ainda não for recursão.

Dessa maneira, você pode calcular o fatorial dos números ou concatenar cadeias.

Ciro Corvino
fonte
0

Agregado usado para somar colunas em uma matriz inteira multidimensional

        int[][] nonMagicSquare =
        {
            new int[] {  3,  1,  7,  8 },
            new int[] {  2,  4, 16,  5 },
            new int[] { 11,  6, 12, 15 },
            new int[] {  9, 13, 10, 14 }
        };

        IEnumerable<int> rowSums = nonMagicSquare
            .Select(row => row.Sum());
        IEnumerable<int> colSums = nonMagicSquare
            .Aggregate(
                (priorSums, currentRow) =>
                    priorSums.Select((priorSum, index) => priorSum + currentRow[index]).ToArray()
                );

Selecionar com índice é usado na função Agregada para somar as colunas correspondentes e retornar uma nova matriz; {3 + 2 = 5, 1 + 4 = 5, 7 + 16 = 23, 8 + 5 = 13}.

        Console.WriteLine("rowSums: " + string.Join(", ", rowSums)); // rowSums: 19, 27, 44, 46
        Console.WriteLine("colSums: " + string.Join(", ", colSums)); // colSums: 25, 24, 45, 42

Mas contar o número de trues em uma matriz booleana é mais difícil, pois o tipo acumulado (int) difere do tipo de origem (bool); aqui é necessária uma semente para usar a segunda sobrecarga.

        bool[][] booleanTable =
        {
            new bool[] { true, true, true, false },
            new bool[] { false, false, false, true },
            new bool[] { true, false, false, true },
            new bool[] { true, true, false, false }
        };

        IEnumerable<int> rowCounts = booleanTable
            .Select(row => row.Select(value => value ? 1 : 0).Sum());
        IEnumerable<int> seed = new int[booleanTable.First().Length];
        IEnumerable<int> colCounts = booleanTable
            .Aggregate(seed,
                (priorSums, currentRow) =>
                    priorSums.Select((priorSum, index) => priorSum + (currentRow[index] ? 1 : 0)).ToArray()
                );

        Console.WriteLine("rowCounts: " + string.Join(", ", rowCounts)); // rowCounts: 3, 1, 2, 2
        Console.WriteLine("colCounts: " + string.Join(", ", colCounts)); // colCounts: 3, 2, 1, 2
Dan M
fonte