Como reduzir o cálculo da média a subconjuntos de uma forma geral?

Question

Editar: Como parece que ninguém está lendo a pergunta original à qual está vinculado, deixe-me trazer uma sinopse dela aqui.

O problema original, conforme perguntado por outra pessoa, era que, dado um grande número de valores, onde a soma excederia o que um tipo de dados de Double seria válido, como se pode calcular a média desses valores.

Houve várias respostas que diziam para calcular em conjuntos, como pegar 50 e 50 números, e calcular a média dentro desses conjuntos, e então finalmente pegar a média de todos esses conjuntos e combiná-los para obter o valor médio final.

Minha posição era que, a menos que você possa garantir que todos esses valores podem ser divididos em uma série de conjuntos de tamanhos iguais, você não pode usar essa abordagem.Alguém me desafiou a fazer a pergunta aqui, para poder dar a resposta, então aqui está.

Basicamente, dado um número arbitrário de valores, onde:

• Eu sei o número de valores de antemão (mas, novamente, como sua resposta mudaria se você não soubesse?`)
• Não consigo reunir todos os números, nem soma-los (a soma será muito grande para um tipo de dados normal na sua linguagem de programação)

como posso calcular a média?

O restante da pergunta aqui descreve como e os problemas da abordagem para dividir em conjuntos de tamanhos iguais, mas eu realmente gostaria de saber como você pode fazer isso.

Observe que conheço matemática perfeitamente o suficiente para saber que, em termos de teoria matemática, calcular a soma de A[1..N]/N vai me dar a média, vamos supor que há razões para que não seja tão simples e que eu precise dividir a carga de trabalho e que o número de valores não seja necessariamente divisível por 3, 7, 50 , 1000 ou qualquer outra coisa.

Em outras palavras, a solução que procuro terá que ser geral.

---

A partir desta pergunta:

• Qual é uma boa solução para calcular uma média onde a soma de todos os valores excede os limites de um duplo?

minha posição era que dividir a carga de trabalho em conjuntos não é bom, a menos que você possa garantir que o tamanho desses conjuntos seja igual.

---

Editar:A pergunta original era sobre o limite superior que um determinado tipo de dados poderia conter e, como ele estava somando muitos números (a contagem dada como exemplo era 10 ^ 9), o tipo de dados não poderia conter a soma.Como esse era um problema na solução original, presumo (e esse é um pré-requisito para minha pergunta, desculpe por não ter percebido isso) que os números são grandes demais para fornecer respostas significativas.

Portanto, dividir diretamente pelo número total de valores está fora de questão.A razão original pela qual uma solução SUM/COUNT normal foi lançada foi que SUM iria estourar, mas vamos supor, para esta questão, que SET-SET/SET-SIZE irá estourar, ou algo assim.

A parte importante é que não posso simplesmente somar, não posso simplesmente dividir pelo número de valores totais.Se eu não puder fazer isso, minha abordagem funcionará ou não, e o que posso fazer para corrigir isso?

---

Deixe-me descrever o problema.

Vamos supor que você vá calcular a média dos números de 1 a 6, mas não pode (por qualquer motivo) fazer isso somando os números, contando os números e depois dividindo a soma pela contagem.Em outras palavras, você não pode simplesmente fazer (1+2+3+4+5+6)/6.

Em outras palavras, SUM(1..6)/COUNT(1..6) está fora.Não estamos considerando NULLs (como NULLs de banco de dados) aqui.

Várias das respostas a essa pergunta aludiam à capacidade de dividir os números calculados em conjuntos, digamos 3, 50 ou 1000 números, depois calcular algum número para isso e, finalmente, combinar esses valores para obter a média final.

Minha posição é que isso não é possível no caso geral, pois fará com que alguns números, os que aparecem no conjunto final, sejam mais ou menos valiosos do que todos os dos conjuntos anteriores, a menos que você possa dividir todos os números em partes iguais. conjuntos de tamanho.

Por exemplo, para calcular a média de 1 a 6, você pode dividi-la em conjuntos de 3 números como este:

/ 1   2   3 \   / 4   5   6 \
| - + - + - | + | - + - + - |
\ 3   3   3 /   \ 3   3   3 /  <-- 3 because 3 numbers in the set
 ----------      -----------
      2               2        <-- 2 because 2 equally sized groups

O que lhe dá isso:

      2               5
      -       +       - = 3.5
      2               2

(observação:(1+2+3+4+5+6)/6 = 3,5, então isso está correto aqui)

No entanto, o que quero dizer é que, uma vez que o número de valores não pode ser dividido em vários conjuntos de tamanhos iguais, esse método desmorona.Por exemplo, o que acontece com a sequência 1-7, que contém um número primo de valores.

Pode uma abordagem semelhante, que não vai resumir todos os valores e conte todos os valores, de uma só vez, funcionam?

Então, existe tal abordagem?Como calculo a média de um número arbitrário de valores em que o seguinte é verdadeiro:

1. Não consigo fazer uma abordagem normal de soma/contagem, por qualquer motivo
2. Eu sei o número de valores de antemão (e se não souber, isso mudará a resposta?)

Answer 1

Bem, suponha que você tenha adicionado três números e dividido por três, e depois adicionou dois números e dividido por dois. Você pode obter a média desses?

x = (a + b + c) / 3
y = (d + e) / 2
z = (f + g) / 2

E você quer

r = (a + b + c + d + e + f + g) / 7

Isso é igual a

r = (3 * (a + b + c) / 3 + 2 * (d + e) / 2 + 2 * (f + g) / 2) / 7
r = (3 * x + 2 * y + 2 * z) / 7

Ambas as linhas acima do excesso

r = (3.0 / 7.0) * x + (2.0 / 7.0) * y + (2.0 / 7.0) * z

O que garante que você não vai transbordar, pois estou multiplicando x, y e z por frações menos de uma.

Este é o ponto fundamental aqui. Nem estou dividindo todos os números de antemão pela contagem total, nem estou excedendo o transbordamento.

Então ... se você continuar adicionando a um acumulador, acompanhe quantos números adicionou e sempre teste se o próximo número causará um estouro, poderá obter médias parciais e calcular a média final.

E não, se você não conhece os valores de antemão, isso não muda de nada (desde que você possa contá -los à medida que os resumem).

Aqui está uma função Scala que faz isso. Não é Scala idiomático, para que possa ser mais facilmente compreendido:

def avg(input: List[Double]): Double = {
  var partialAverages: List[(Double, Int)] = Nil
  var inputLength = 0
  var currentSum = 0.0
  var currentCount = 0
  var numbers = input

  while (numbers.nonEmpty) {
    val number = numbers.head
    val rest = numbers.tail
    if (number > 0 && currentSum > 0 && Double.MaxValue - currentSum < number) {
      partialAverages = (currentSum / currentCount, currentCount) :: partialAverages
      currentSum = 0
      currentCount = 0
    } else if (number < 0 && currentSum < 0 && Double.MinValue - currentSum > number) {
      partialAverages = (currentSum / currentCount, currentCount) :: partialAverages
      currentSum = 0
      currentCount = 0
    }
    currentSum += number
    currentCount += 1
    inputLength += 1
    numbers = rest
  }
  partialAverages = (currentSum / currentCount, currentCount) :: partialAverages

  var result = 0.0
  while (partialAverages.nonEmpty) {
    val ((partialSum, partialCount) :: rest) = partialAverages
    result += partialSum * (partialCount.toDouble / inputLength)
    partialAverages = rest
  }

  result
}

EDIT: Não vai se multiplicar com 2 e 3, volte ao alcance de "não apoiador pelo tipo de dados?"

Não. Se você estava mergulhando às 7 no final, absolutamente. Mas aqui você está se dividindo em cada etapa da soma. Mesmo no seu caso real, os pesos (2/7 e 3/7) estaria na gama de números de gerenciamento (por exemplo 1/10 ~ 1/10000) que não faria uma grande diferença em comparação com o seu peso (ou seja, 1).

PS: Eu me pergunto por que estou trabalhando nessa resposta em vez de escrever a minha, onde posso ganhar meu representante :-)

Answer 2

Se você conhece o número de valores de antemão (digamos que é N), você apenas adiciona 1/N + 2/N + 3/N etc, supondo que você tinha valores 1, 2, 3. Você pode dividir isso em quantos cálculos quiser e apenas adicionar seus resultados. Isso pode levar a uma ligeira perda de precisão, mas isso não deve ser um problema, a menos que você também precise de um resultado super-preciso.

Se você não souber o número de itens com antecedência, pode ser mais criativo. Mas você pode, novamente, fazê -lo progressivamente. Diga que a lista é 1, 2, 3, 4. Começar com mean = 1. Então mean = mean*(1/2) + 2*(1/2). Então mean = mean*(2/3) + 3*(1/3). Então mean = mean*(3/4) + 4*(1/4) etc. É fácil generalizar, e você só precisa garantir que as quantidades entre colchetes sejam calculadas com antecedência, para evitar o transbordamento.

Obviamente, se você deseja extrema precisão (digamos, mais de 0,001% de precisão), pode ser necessário um pouco mais cuidadoso que isso, mas, caso contrário, você deve ficar bem.

Answer 3

Deixar X seja seu conjunto de amostras. Particioná -lo em dois conjuntos A e B de qualquer maneira que você goste. Definir delta = m_B - m_A Onde m_S indica a média de um conjunto S. Então

m_X = m_A + delta * |B| / |X|

Onde |S| indica a cardinalidade de um conjunto S. Agora você pode aplicá -lo repetidamente à partição e calcular a média.

Por que isso é verdade? Deixar s = 1 / |A| e t = 1 / |B| e u = 1 / |X| (por conveniência de notação) e deixe aSigma e bSigma denotar a soma dos elementos em A e B respectivamente para que:

  m_A + delta * |B| / |X|
= s * aSigma + u * |B| * (t * bSigma - s * aSigma)
= s * aSigma + u * (bSigma - |B| * s * aSigma)
= s * aSigma + u * bSigma - u * |B| * s * aSigma
= s * aSigma * (1 - u * |B|) + u * bSigma
= s * aSigma * (u * |X| - u * |B|) + u * bSigma
= s * u * aSigma * (|X| - |B|) + u * bSigma
= s * u * aSigma * |A| + u * bSigma
= u * aSigma + u * bSigma
= u * (aSigma + bSigma)
= u * (xSigma)
= xSigma / |X|
= m_X

A prova está completa.

A partir daqui, é óbvio como usá -lo para calcular recursivamente uma média (digamos, dividindo repetidamente um conjunto pela metade) ou como usá -lo para paralelizar o cálculo da média de um conjunto.

O conhecido algoritmo on-line para calcular a média é apenas um caso especial disso. Este é o algoritmo que se m é a média de {x_1, x_2, ... , x_n} então a média de {x_1, x_2, ..., x_n, x_(n+1)} é m + ((x_(n+1) - m)) / (n + 1). Então com X = {x_1, x_2, ..., x_(n+1)}, A = {x_(n+1)}, e B = {x_1, x_2, ..., x_n} Recuperamos o algoritmo on-line.

Answer 4

Pensando fora da caixa: Use a mediana em vez disso. É muito mais fácil de calcular - existem toneladas de algoritmos por aí (por exemplo, usando filas), muitas vezes você pode construir bons argumentos sobre o motivo pelo qual é mais significativo para conjuntos de dados (menos influenciados por valores extremos; etc) e você terá zero problemas com precisão numérica. Será rápido e eficiente. Além disso, para grandes conjuntos de dados (o que parece que você tem), a menos que as distribuições sejam verdadeiramente estranhas, os valores para a média e a mediana serão semelhantes.

Answer 5

Quando você dividiu os números em conjuntos, está apenas dividindo pelo número total ou estou perdendo alguma coisa?

Você escreveu como

/ 1   2   3 \   / 4   5   6 \
| - + - + - | + | - + - + - |
\ 3   3   3 /   \ 3   3   3 /
 ----------      -----------
      2               2

Mas isso é apenas

/ 1   2   3 \   / 4   5   6 \
| - + - + - | + | - + - + - |
\ 6   6   6 /   \ 6   6   6 /

Portanto, para os números de 1 a 7, um possível agrupamento é apenas

/ 1   2   3 \   / 4   5   6 \   / 7 \
| - + - + - | + | - + - + - | + | - |
\ 7   7   7 /   \ 7   7   7 /   \ 7 /

Answer 6

 

Average of x_1 .. x_N
    = (Sum(i=1,N,x_i)) / N
    = (Sum(i=1,M,x_i) + Sum(i=M+1,N,x_i)) / N
    = (Sum(i=1,M,x_i)) / N + (Sum(i=M+1,N,x_i)) / N

Isso pode ser aplicado repetidamente e é verdadeiro, independentemente de as sumaturas serem de tamanho igual. Então:

• Continue adicionando termos até os dois:
• • Adicionar outro vai transbordar (ou perder precisão)
• • Dividir por n não vai subir
• Divida a soma por n
• Adicione o resultado à média tão-far

Há um caso óbvio e estranho, que há alguns termos muito pequenos no final da sequência, de modo que você fica sem valores antes de satisfazer a condição "dividir por n não subirá". Nesse caso, basta descartar esses valores - se a contribuição deles para a média não puder ser representada no seu tipo flutuante, é em particular menor que a precisão da sua média. Portanto, não faz diferença para o resultado, se você incluir esses termos ou não.

Há também alguns casos menos óbvios relacionados à perda de precisão em sumões individuais. Por exemplo, qual é a média dos valores:

10^100, 1, -10^100

A matemática diz que é 1, mas a aritmética de ponto flutuante diz que depende de qual ordem você adiciona os termos e, em 4 das 6 possibilidades, é 0, porque (10^100) + 1 = 10^100. Mas acho que a não comutatividade da aritmética de ponto flutuante é um problema diferente e mais geral do que essa questão. Se a classificação da entrada está fora de questão, acho que há coisas que você pode fazer, onde você mantém muitos acumuladores de magnitudes diferentes e adicione cada novo valor a qualquer um deles que dará melhor precisão. Mas eu realmente não sei.

Answer 7

Aqui está outra abordagem. Você está 'recebendo' números um a um de alguma fonte, mas pode acompanhar a média em cada etapa.

Primeiro, vou escrever a fórmula para a média na etapa n+1:

mean[n+1] = mean[n] - (mean[n] - x[n+1]) / (n+1)

Com a condição inicial:

mean[0] = x[0]

(O índice começa em zero).

A primeira equação pode ser simplificada para:

mean[n+1] = n * mean[n] / (n+1) + x[n+1]/(n+1)

A idéia é que você acompanhe a média e, quando 'recebe' o próximo valor em sua sequência, descobre o deslocamento da média atual e divide -a igualmente entre o n+1 Amostras vistas até agora e ajuste o seu significado de acordo. Se seus números não tiverem muita variação, seu significado de corrida precisará ser ajustado muito ligeiramente com os novos números como n torna -se grande.

Obviamente, esse método funciona mesmo que você não saiba o número total de valores quando você inicia. Tem uma vantagem adicional de que você conhece o valor da média atual o tempo todo. Uma desvantagem que eu consigo pensar é o que provavelmente dá mais 'peso' aos números vistos no começo (não em um sentido matemático estrito, mas por causa de representações de pontos flutuantes).

Finalmente, todos esses cálculos devem chegar a 'erros' de ponto flutuante, se não for cuidadoso o suficiente. Ver Minha resposta para outra pergunta Para alguns dos problemas com os cálculos de ponto flutuante e como testar possíveis problemas.

Como teste, eu gerei N=100000 Normalmente distribuídos números aleatórios com zero e variação média 1. Em seguida, calculei a média deles por três métodos.

1. soma (números) / n, chame de m₁,
2. Meu método acima, chame de m₂,
3. Classifique os números e depois use meu método acima, chame -o m₃.

Aqui está o que eu encontrei: M₁- m₂ ∼ −4.6×10⁻¹⁷, m₁- m₃ ∼ −3×10⁻¹⁵, m₂- m₃ ∼ −3×10⁻¹⁵. Portanto, se seus números forem classificados, o erro pode não ser pequeno o suficiente para você. (Observe, no entanto, que mesmo o pior erro é 10⁻¹⁵ peças em 1 para 100000 números, por isso pode ser bom o suficiente.)

Answer 8

Algumas das soluções matemáticas aqui são muito boas.Aqui está uma solução técnica simples.

Use um tipo de dados maior.Isso se divide em duas possibilidades:

1. Use uma biblioteca de ponto flutuante de alta precisão.Alguém que precisa calcular a média de um bilhão de números provavelmente tem os recursos para comprar, ou a capacidade cerebral para escrever, uma biblioteca de ponto flutuante de 128 bits (ou mais).

   Eu entendo as desvantagens aqui.Certamente seria mais lento do que usar tipos intrínsecos.Você ainda pode transbordar/subfluir se o número de valores aumentar muito.Sim, sim.

2. Se seus valores forem inteiros ou puderem ser facilmente dimensionados para inteiros, mantenha sua soma em uma lista de inteiros.Quando você estourar, basta adicionar outro número inteiro.Esta é essencialmente uma implementação simplificada da primeira opção.Um simples (não testado) exemplo em C# segue

class BigMeanSet{
    List<uint> list = new List<uint>();

    public double GetAverage(IEnumerable<uint> values){
        list.Clear();
        list.Add(0);

        uint count = 0;

        foreach(uint value in values){
            Add(0, value);
            count++;
        }

        return DivideBy(count);
    }

    void Add(int listIndex, uint value){
        if((list[listIndex] += value) < value){ // then overflow has ocurred
            if(list.Count == listIndex + 1)
                list.Add(0);
            Add(listIndex + 1, 1);
        }
    }

    double DivideBy(uint count){
        const double shift = 4.0 * 1024 * 1024 * 1024;

        double rtn       = 0;
        long   remainder = 0;

        for(int i = list.Count - 1; i >= 0; i--){
            rtn *= shift;
            remainder <<= 32;
            rtn += Math.DivRem(remainder + list[i], count, out remainder);
        }

        rtn += remainder / (double)count;

        return rtn;
    }
}

Como eu disse, isso não foi testado – não tenho um bilhão de valores que realmente queira calcular a média – então provavelmente cometi um ou dois erros, especialmente no DivideBy função, mas deve demonstrar a ideia geral.

Isso deve fornecer tanta precisão quanto um double pode representar e deve funcionar para qualquer número de elementos de 32 bits, até 2³² - 1.Se forem necessários mais elementos, então o count variável precisará ser expandida e o DivideBy função aumentará em complexidade, mas deixarei isso como exercício para o leitor.

Em termos de eficiência, deve ser tão ou mais rápido do que qualquer outra técnica aqui, pois requer apenas uma iteração na lista uma vez, executa apenas uma operação de divisão (bem, um conjunto delas) e faz a maior parte do seu trabalho com inteiros .Porém, não o otimizei e tenho certeza de que poderia ser um pouco mais rápido ainda, se necessário.Abandonar a chamada de função recursiva e a indexação de lista seria um bom começo.Novamente, um exercício para o leitor.O código pretende ser fácil de entender.

Se alguém mais motivado do que eu no momento quiser verificar a exatidão do código e corrigir quaisquer problemas que possam existir, fique à vontade.

---

Agora testei esse código e fiz algumas pequenas correções (um par de parênteses faltando no List<uint> chamada do construtor e um divisor incorreto na divisão final do DivideBy função).

Eu testei primeiro executando-o em 1.000 conjuntos de comprimento aleatório (variando entre 1 e 1.000) preenchidos com números inteiros aleatórios (variando entre 0 e 2³² -1).Esses eram conjuntos para os quais eu poderia verificar a precisão de maneira fácil e rápida, executando também uma média canônica neles.

Então testei com 100^* séries grandes, com comprimento aleatório entre 10⁵ e 10⁹.Os limites inferior e superior dessas séries também foram escolhidos aleatoriamente, restringidos para que a série se ajustasse ao intervalo de um número inteiro de 32 bits.Para qualquer série, os resultados são facilmente verificáveis ​​como (lowerbound + upperbound) / 2.

_{^{*Ok, isso é uma pequena mentira.Abortei o teste de grandes séries após cerca de 20 ou 30 execuções bem-sucedidas.Uma série de comprimento 109 leva pouco menos de um minuto e meio para ser executado na minha máquina, então meia hora ou mais testando essa rotina foi suficiente para o meu gosto.}}

Para os interessados, meu código de teste está abaixo:

static IEnumerable<uint> GetSeries(uint lowerbound, uint upperbound){
    for(uint i = lowerbound; i <= upperbound; i++)
        yield return i;
}

static void Test(){
    Console.BufferHeight = 1200;
    Random rnd = new Random();

    for(int i = 0; i < 1000; i++){
        uint[] numbers = new uint[rnd.Next(1, 1000)];
        for(int j = 0; j < numbers.Length; j++)
            numbers[j] = (uint)rnd.Next();

        double sum = 0;
        foreach(uint n in numbers)
            sum += n;

        double avg = sum / numbers.Length;
        double ans = new BigMeanSet().GetAverage(numbers);

        Console.WriteLine("{0}: {1} - {2} = {3}", numbers.Length, avg, ans, avg - ans);

        if(avg != ans)
            Debugger.Break();
    }

    for(int i = 0; i < 100; i++){
        uint length     = (uint)rnd.Next(100000, 1000000001);
        uint lowerbound = (uint)rnd.Next(int.MaxValue - (int)length);
        uint upperbound = lowerbound + length;

        double avg = ((double)lowerbound + upperbound) / 2;
        double ans = new BigMeanSet().GetAverage(GetSeries(lowerbound, upperbound));

        Console.WriteLine("{0}: {1} - {2} = {3}", length, avg, ans, avg - ans);

        if(avg != ans)
            Debugger.Break();
    }
}