Comment réduire le calcul de la moyenne des sous-ensembles d'une manière générale?

https://stackoverflow.com/questions/1931359

20-09-2019
|

Question

Edit:. Comme il semble que personne ne lit la question initiale des liens vers ce, permettez-moi de mettre en récapitulant ici

Le problème d'origine, comme demandé par quelqu'un d'autre, était que, étant donné un grand nombre de valeurs, la somme dépasserait ce type de données de Double détiendrait, comment peut-on calculer la moyenne de ces valeurs.

Il y avait plusieurs réponses qui ont dit à calculer dans les jeux, comme prendre 50 et 50 numéros, et le calcul de la moyenne à l'intérieur de ces ensembles, puis enfin prendre la moyenne de tous ces ensembles et combiner ceux pour obtenir la valeur moyenne finale.

Ma position était que si vous pouvez garantir que toutes ces valeurs peuvent être divisées en plusieurs, vous ne pouvez pas utiliser cette approche ensembles de taille égale . Quelqu'un m'a osé poser la question ici, afin de fournir la réponse, si elle est ici.

En fait, étant donné un nombre arbitraire de valeurs, où:

Je sais que le nombre de valeurs d'avance (mais encore une fois, comment votre changement de réponse si vous ne l'avez pas? `)
Je ne peux pas rassembler tous les chiffres, et je ne puis les résumer (la somme sera trop grand pour un type de données normale dans votre langage de programmation)

comment puis-je calculer la moyenne?

Le reste de la question ici décrit comment, et les problèmes avec l'approche de diviser en ensembles de taille égale, mais je voudrais vraiment juste savoir comment vous pouvez le faire.

Notez que je sais très bien assez de mathématiques pour savoir qu'en termes de théorie des mathématiques, le calcul de la somme de A[1..N]/N me donnera la moyenne, supposons qu'il ya des raisons pour lesquelles il est pas aussi simple, et je dois diviser la charge de travail, et que le nombre de valeurs ne va pas nécessairement être divisible par 3, 7, 50, 1000 ou autre.

En d'autres termes, la solution que je suis après devra être général.

A partir de cette question:

Qu'est-ce qu'une bonne solution pour calculer une moyenne où la somme de toutes les valeurs dépasse les limites d'un double

ma position était que la division de la charge de travail vers le haut dans des ensembles est pas bon, à moins que vous pouvez vous assurer que la taille de ces ensembles sont égaux.

Modifier : La question initiale était de la limite supérieure d'un type de données particulier pourrait tenir, et comme il résumait beaucoup de chiffres (nombre qui a été donné à titre d'exemple était de 10 ^ 9) , le type de données n'a pas pu tenir la somme. Étant donné que c'était un problème dans la solution d'origine, je suppose (ce qui est une condition préalable à ma question, désolé d'avoir manqué cela) que les chiffres sont trop grandes pour donner des réponses significatives.

Ainsi, en divisant par le nombre total de valeurs est directement. La raison initiale pour laquelle une solution normale SUM / COUNT était en était que SUM débordait, mais supposons, pour cette question que SET-SET / SET-SIZE underflow, ou autre.

L'important est que je ne peux pas simplement la somme, je ne peux pas simplement diviser par le nombre de valeurs totales. Si je ne peux pas le faire, ce que mon approche, ou non, et que puis-je faire pour y remédier?

Permettez-moi de décrire le problème.

Supposons que vous allez calculer la moyenne des numéros 1 à 6, mais vous ne pouvez pas (quelle qu'en soit la raison) faire en additionnant les nombres, en comptant les chiffres, puis en divisant la somme par le nombre. En d'autres termes, vous ne pouvez pas simplement faire (1 + 2 + 3 + 4 + 5 + 6) / 6.

En d'autres termes, SUM(1..6)/COUNT(1..6) est sorti. Nous ne sommes pas considérer NULL (psl dans la base de données de NULL) ici.

Plusieurs des réponses à cette question fait allusion à être en mesure de diviser les nombres étant moyennées en ensembles, disons 3 ou 50 ou 1000 numéros, puis en calculant un nombre pour cela, et puis finalement la combinaison de ces valeurs pour obtenir la moyenne finale.

Ma position est que ce ne soitt possible dans le cas général, car cela fera quelques chiffres, ceux qui apparaissent dans le dernier set, plus ou moins de valeur que tous ceux dans les jeux précédents, à moins que vous pouvez diviser tous les chiffres en ensembles de taille égale.

Par exemple, pour calculer la moyenne de 1-6, vous pouvez le diviser en séries de 3 chiffres comme ceci:

/ 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

Ce qui vous donne ceci:

      2               5
      -       +       - = 3.5
      2               2

(note: (1 + 2 + 3 + 4 + 5 + 6) / 6 = 3,5, de sorte que l'information est correcte ici)

Cependant, mon point est que, une fois le nombre de valeurs ne peut être divisé en un certain nombre d'ensembles de taille égale, cette méthode se désagrège. Par exemple, que sur l'ordre 1-7, qui contient un nombre premier de valeurs.

Peut une approche similaire, qui ne correspondra pas tous les valeurs, et comptez tous les valeurs, en une seule fois, travailler?

Alors, est-il une telle approche? Comment puis-je calculer la moyenne d'un nombre arbitraire de valeurs dans lesquelles ce qui suit est vrai:

Je ne peux pas faire une approche somme / de comptage normale, pour une raison quelconque
Je sais que le nombre de valeurs d'avance (si je ne le fais pas, ça va changer la réponse?)

La solution

Eh bien, supposons que vous ajouté trois chiffres et divisé par trois, puis a ajouté deux chiffres et divisé par deux. Pouvez-vous obtenir la moyenne de ces?

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

Et vous voulez

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

C'est égal à

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

Les deux lignes ci-dessus débordement, bien sûr, mais étant donné que la division est distributive, nous

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

Ce qui garantit que vous ne débordera pas, comme je multipliant x, y et z par fractions de moins d'un.

Ceci est le point fondamental. Je ne divise tous les numéros à l'avance par le nombre total, et je ne suis jamais dépasser le trop-plein.

Alors ... si vous vous continuez à ajouter à un accumulateur, garder une trace de combien de chiffres que vous avez ajouté, et toujours tester si le numéro suivant provoquera un débordement, vous pouvez obtenir des moyennes partielles, et calculer la moyenne finale .

Et non, si vous ne connaissez pas les valeurs d'avance, il ne change rien (les autant que vous pouvez compter que vous les additionnez).

Voici une fonction Scala qu'il fait. Ce n'est pas idiomatiques Scala, de sorte qu'il peut être plus facile à comprendre:

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: Ne multipliant par 2, et 3, me retourner dans la gamme de « ne pas supporter par le type de données? »

Non. Si vous étiez plongée de 7 à la fin, tout à fait. Mais là, vous divisez à chaque étape de la somme. Même dans votre cas réel les poids (2/7 et 3/7) seraient dans la gamme des nombres manageble (par exemple 1/10 ~ 1/10000) qui ne serait pas faire une grande différence par rapport à votre poids (à savoir 1).

PS: Je me demande pourquoi je travaille sur cette réponse au lieu de moi d'écriture où je peux gagner mon représentant: -)

Autres conseils

Si vous connaissez le nombre de valeurs d'avance (que c'est N), vous ajoutez juste 1/N + 2/N + 3/N etc, en supposant que vous aviez des valeurs 1, 2, 3. Vous pouvez diviser ce en autant de calculs que vous le souhaitez, et ajouter simplement vos résultats. Elle peut conduire à une légère perte de précision, mais cela ne devrait pas être un problème à moins que vous aussi besoin d'un résultat super précis.

Si vous ne l'avance, vous devrez peut-être connaissez pas le nombre d'éléments à être plus créatifs. Mais vous pouvez, encore une fois, le faire progressivement. Dites la liste est 1, 2, 3, 4. Commencez par mean = 1. Ensuite mean = mean*(1/2) + 2*(1/2). Ensuite mean = mean*(2/3) + 3*(1/3). Puis mean = mean*(3/4) + 4*(1/4) etc. Il est facile de généraliser, et il vous suffit de vous assurer que les quantités entre crochets sont calculées à l'avance, pour éviter le débordement.

Bien sûr, si vous voulez une extrême précision (par exemple, plus de 0,001% de précision), vous devrez peut-être un peu plus prudent que cela, mais sinon, vous devriez être bien.

Laissez X être votre ensemble d'échantillons. Partitionner en deux ensembles A et B de quelque façon que vous aimez. Définir delta = m_B - m_A où m_S désigne la moyenne d'un ensemble S. Ensuite,

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

où |S| désigne la cardinalité d'un ensemble S. Vous pouvez maintenant appliquer à plusieurs reprises cette partitionner et calculer la moyenne.

Pourquoi est-ce vrai? Soit s = 1 / |A| et t = 1 / |B| et u = 1 / |X| (pour la commodité de la notation) et permettent de aSigma et bSigma représentent la somme des éléments en A et B respectivement de sorte 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

La preuve est terminée.

De là, il est évident comment utiliser ce soit récursive calculer une moyenne (par exemple en divisant à plusieurs reprises un ensemble en deux) ou comment utiliser pour paralléliser le calcul de la moyenne d'un ensemble.

L'algorithme en ligne bien connue pour le calcul de la moyenne est un cas particulier de ce. Ceci est l'algorithme que si m est la moyenne de {x_1, x_2, ... , x_n} alors la moyenne des {x_1, x_2, ..., x_n, x_(n+1)} est m + ((x_(n+1) - m)) / (n + 1). Donc, avec X = {x_1, x_2, ..., x_(n+1)}, A = {x_(n+1)} et B = {x_1, x_2, ..., x_n} nous récupérons l'algorithme en ligne.

Penser en dehors de la boîte: Utilisez la médiane à la place. Il est beaucoup plus facile de calculer - il y a des tonnes d'algorithmes là-bas (par exemple en utilisant les files d'attente), vous pouvez souvent construire de bons arguments pour expliquer pourquoi il est plus significatif pour les ensembles de données (moins influencés par les valeurs extrêmes, etc.) et vous aurez zéro problème avec précision numérique. Ce sera rapide et efficace. De plus, pour les grands ensembles de données (dont il semble que vous avez), à moins que les distributions sont vraiment bizarres, les valeurs de la moyenne et la médiane seront similaires.

Lorsque vous divisez les chiffres en ensembles que vous êtes juste en divisant par le nombre total ou suis-je manque quelque chose?

Vous avez écrit comme

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

mais c'est juste

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

pour les nombres de 1 à 7 un éventuel regroupement est juste

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

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

Cela peut être appliquée à maintes reprises, et est vrai, que les sommations sont de taille égale. Donc:

Continuez à ajouter jusqu'à ce que les termes:
- ajouter un autre débordera (ou autre perte de précision)
- division par N n'underflow
Diviser la somme par N
Ajoutez le résultat à la moyenne si lointain

Il y a un cas évident maladroit, qui est qu'il ya des termes très petits à la fin de la séquence, de sorte que vous manquez de valeurs avant de satisfaire à la condition « en divisant par N ne sera pas underflow ». Dans ce cas, juste jeter ces valeurs - si leur contribution à la moyenne ne peut pas être représenté dans votre type flottant, il est en particulier inférieure à la précision de votre moyenne. Donc, il ne fait aucune différence pour le résultat que vous incluez ces termes ou non.

Il y a aussi quelques cas difficiles moins évidentes à voir avec la perte de précision sur chaque sommations. Par exemple, quelle est la moyenne des valeurs:

10^100, 1, -10^100

Mathématiques dit que c'est 1, mais l'arithmétique en virgule flottante dit que cela dépend ordre dans lequel vous ajoutez les termes, et dans 4 des 6 possibilités, c'est 0 parce que (10 ^ 100) + 1 = 10 ^ 100. Mais je pense que la non-commutativité de l'arithmétique en virgule flottante est un problème différent et plus général que cette question. Si le tri de l'entrée est hors de question, je pense qu'il ya des choses que vous pouvez faire où vous conservez beaucoup d'accumulateurs de différentes grandeurs, et d'ajouter chaque nouvelle valeur à quel que soit l'un d'entre eux donnera plus de précision. Mais je ne sais pas vraiment.

Voici une autre approche. Vous êtes « recevoir » les numéros un par un à partir d'une source, mais vous pouvez garder une trace de la moyenne à chaque étape.

D'abord, je vais écrire la formule de moyenne à l'étape n+1:

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

à l'état initial:

mean[0] = x[0]

(l'index commence à zéro).

La première équation peut être simplifiée à:

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

L'idée est que vous garder une trace de la moyenne, et quand vous recevez la valeur suivante dans la séquence, vous figurez son décalage par rapport à la moyenne actuelle, et le diviser à parts égales entre les échantillons de n+1 vus jusqu'à présent, et ajuster votre moyenne en conséquence. Si vos chiffres n'ont pas beaucoup de variance, votre moyenne de fonctionnement devra être réglé très légèrement avec les nouveaux numéros que n devient grand.

De toute évidence, cette méthode fonctionne même si vous ne connaissez pas le nombre total de valeurs lorsque vous démarrez. Il a un avantage supplémentaire que vous connaissez la valeur de la moyenne actuelle en tout temps. Un inconvénient que je peux penser est le lui donne sans doute plus « poids » aux chiffres observés au début (pas dans un sens mathématique strict, mais à cause de représentations à virgule flottante).

Enfin, tous ces calculs sont tenus de courir en « erreurs » à virgule flottante si l'on est pas assez prudent. Voir mon réponse à une autre question pour certains des problèmes avec des calculs à virgule flottante et comment tester les problèmes potentiels.

En tant que test, je N=100000 normalement générés distribuais des nombres aléatoires avec une moyenne nulle et de variance 1. Ensuite, je calcule leur moyenne de trois méthodes.

somme (nombres) / N, appeler m ₁,
ma méthode ci-dessus, appelez m ₂,
trier les numéros, puis utiliser ma méthode ci-dessus, appelez m ₃.

Voici ce que je trouve: m ₁ - m ₂ ~ -4,6 × 10 ^-17, m ₁ - m ₃ ~ -3 × 10 ^-15, m ₂ - m ₃ ~ -3 × 10 ^-15. Donc, si vos numéros sont classés, l'erreur pourrait ne pas être assez petit pour vous. (Notez cependant que même la pire erreur est 10 ^-15 pièces en 1 pour 100000 nombres, de sorte qu'il pourrait être assez bon quand même.)

Certaines des solutions mathématiques ici sont très bons. Voici une solution technique simple.

Utilisez un type de données plus grande. Cela se décompose en deux possibilités:

Utilisez une bibliothèque à virgule flottante de haute précision. Celui qui rencontre un besoin en moyenne d'un milliard le nombre a sans doute les ressources nécessaires pour acheter, ou la puissance du cerveau à écrire, une bibliothèque de virgule flottante de 128 bits (ou plus).

Je comprends les inconvénients ici. Il serait certainement plus lent que d'utiliser les types intrinsèques. Vous pourriez encore plus de / si le nombre soupassement de valeurs devient trop élevé. Patata.
Si vos valeurs sont des nombres entiers ou peuvent être facilement mis à l'échelle pour les entiers, garder votre somme dans une liste de nombres entiers. Lorsque vous débordez, ajoutez simplement un autre entier. Ceci est essentiellement une mise en œuvre simplifiée de la première option. Un simple ~~(non testé)~~ par exemple en C # suit

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

Comme je l'ai dit, ce n'est pas testé, je n'ai pas un milliard de valeurs que je veux vraiment en moyenne, donc je l'ai probablement fait une erreur ou deux, en particulier dans la fonction DivideBy, mais il devrait démontrer la idée générale.

Cela devrait fournir autant de précision que double peut représenter et devrait fonctionner pour un certain nombre d'éléments 32 bits, jusqu'à 2 ³² - 1. Si plusieurs éléments sont nécessaires, alors la variable count aura besoin être étendu et la fonction de DivideBy augmente la complexité, mais je vais laisser cela comme un exercice pour le lecteur.

En termes d'efficacité, il doit être aussi rapide ou plus rapide que toute autre technique ici, car il itérer exige que la liste une fois, n'effectue une opération de division (bien, un ensemble d'entre eux), et fait la plupart de ses travailler avec des nombres entiers. Je n'optimisez pas, cependant, et je suis assez certain qu'il pourrait être un peu plus rapide encore si nécessaire. Amerrissage l'indexation des appels de fonction récursive et la liste serait un bon début. Encore une fois, un exercice pour le lecteur. Le code est destiné à être facile à comprendre.

~~Si quelqu'un plus motivé que je suis en ce moment se sent comme vérifier l'exactitude du code, et fixer tous les problèmes qu'il pourrait y avoir, s'il vous plaît être mon invité.~~

Je l'ai maintenant testé ce code, et fait quelques petites corrections (une paire manquante entre parenthèses dans l'appel constructeur List<uint>, et un diviseur incorrect dans la division finale de la fonction DivideBy).

I testé par ce premier traversant 1000 ensembles de longueur aléatoire (comprise entre 1 et 1000) rempli d'entiers aléatoires (compris entre 0 et 2 ³² - 1). Ces ensembles étaient pour lesquels je pourrais facilement et rapidement vérifier la précision en exécutant également une moyenne canonique sur eux.

I puis testé avec 100 ^* de grandes séries, avec une longueur aléatoire entre 10 ⁵ et 10 ⁹. Les limites inférieures et supérieures de ces séries ont également été choisis au hasard, contraint de telle sorte que la série se tenir dans l'intervalle d'un nombre entier de 32 bits. Pour toute série, les résultats sont facilement vérifiables comme (lowerbound + upperbound) / 2.

^{_{^* D'accord, c'est un petit mensonge blanc. J'avorté le test de grande série au bout de 20 ou 30 courses avec succès. Une série de longueur 10 ⁹ prend moins d'une minute et demie pour courir sur ma machine, donc une demi-heure ou de tester cette routine était assez à mon goût.}}

Pour les intéressés, mon code de test est ci-dessous:

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

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow