Pourquoi est-statistiques.moyenne() si lent?

Question

J'ai comparé la performance de l' mean fonction de l' statistics module avec la simple sum(l)/len(l) méthode et a trouvé l' mean fonction très lent pour une raison quelconque. J'ai utilisé timeit avec les deux extraits de code ci-dessous pour les comparer, personne ne sait quelles sont les causes de l'énorme différence dans la vitesse d'exécution? Je suis à l'aide de Python 3.5.

from timeit import repeat
print(min(repeat('mean(l)',
                 '''from random import randint; from statistics import mean; \
                 l=[randint(0, 10000) for i in range(10000)]''', repeat=20, number=10)))

Le code ci-dessus s'exécute sur 0.043 secondes sur ma machine.

from timeit import repeat
print(min(repeat('sum(l)/len(l)',
                 '''from random import randint; from statistics import mean; \
                 l=[randint(0, 10000) for i in range(10000)]''', repeat=20, number=10)))

Le code ci-dessus s'exécute sur 0.000565 secondes sur ma machine.

Answer 1

Python statistics module n'est pas construit pour la vitesse, mais pour la précision

Dans les specs de ce module, il semble que

La somme intégrée pouvez perdre de la précision lorsque vous traitez avec des flotteurs de sauvagement différentes grandeur. Par conséquent, le ci-dessus naïf échoue, cela signifie "torture test"

assert mean([1e30, 1, 3, -1e30]) == 1

de retour 0 au lieu de 1, un pur calcul d'erreur de 100%.

L'utilisation des mathématiques.fsum à l'intérieur de moyenne, il sera plus précis avec flotteur de données, mais il a aussi le côté-effet de la conversion de tous les arguments pour flotteur même quand elles sont inutiles. E. g. nous devrions nous attendre à la moyenne d'une liste des Fractions à une Fraction, pas d'un flotteur.

A l'inverse, si nous prenons un coup d'oeil à la mise en œuvre de l' _sum() dans ce module, les premières lignes de la méthode de la docstring semblent confirmer que:

def _sum(data, start=0):
    """_sum(data [, start]) -> (type, sum, count)

    Return a high-precision sum of the given numeric data as a fraction,
    together with the type to be converted to and the count of items.

    [...] """

Donc ouais, statistics de la mise en œuvre de l' sum, au lieu d'être un simple one-liner appel à Python intégré dans l' sum() fonction, prend environ 20 lignes par lui-même avec un imbriquée for boucle dans son corps.

Cela se produit parce que l' statistics._sum choisit pour garantir le maximum de précision pour tous les types de nombre il pourrait rencontrer (même si elles diffèrent l'une de l'autre), au lieu de simplement en mettant l'accent sur la vitesse.

Par conséquent, il semble normal que le haut- sum prouve une centaine de fois plus rapide. Le coût de celui-ci étant beaucoup moins de précision que vous arrive d'appeler avec des numéros exotiques.

D'autres options

Si vous avez besoin de prioriser la vitesse de votre algorithmes, vous devriez jeter un oeil à Numpy au lieu de cela, les algorithmes de mises en œuvre de C.

NumPy veux dire, c'est pas aussi précis qu' statistics par un long shot, mais il met en œuvre (depuis 2013) une routine basée sur des paires de sommation qui est mieux qu'un naïf sum/len (plus d'info dans le lien).

Cependant...

import numpy as np
import statistics

np_mean = np.mean([1e30, 1, 3, -1e30])
statistics_mean = statistics.mean([1e30, 1, 3, -1e30])

print('NumPy mean: {}'.format(np_mean))
print('Statistics mean: {}'.format(statistics_mean))

> NumPy mean: 0.0
> Statistics mean: 1.0

Answer 2

si vous vous souciez de la vitesse d'utilisation de numpy/scipy/pandas à la place:

In [119]: from random import randint; from statistics import mean; import numpy as np;

In [122]: l=[randint(0, 10000) for i in range(10**6)]

In [123]: mean(l)
Out[123]: 5001.992355

In [124]: %timeit mean(l)
1 loop, best of 3: 2.01 s per loop

In [125]: a = np.array(l)

In [126]: np.mean(a)
Out[126]: 5001.9923550000003

In [127]: %timeit np.mean(a)
100 loops, best of 3: 2.87 ms per loop

Conclusion: il sera ordres de grandeur plus rapide dans mon exemple, il était de 700 fois plus rapide, mais peut-être pas aussi précis (comme numpy ne pas utiliser Kahan algorithme de sommation).

Answer 3

J'ai posé la même question tout à l'arrière, mais une fois que j'ai remarqué l' _sum fonction appelée en moyenne sur la ligne 317 dans la source que j'ai compris pourquoi:

def _sum(data, start=0):
    """_sum(data [, start]) -> (type, sum, count)
    Return a high-precision sum of the given numeric data as a fraction,
    together with the type to be converted to and the count of items.
    If optional argument ``start`` is given, it is added to the total.
    If ``data`` is empty, ``start`` (defaulting to 0) is returned.
    Examples
    --------
    >>> _sum([3, 2.25, 4.5, -0.5, 1.0], 0.75)
    (<class 'float'>, Fraction(11, 1), 5)
    Some sources of round-off error will be avoided:
    >>> _sum([1e50, 1, -1e50] * 1000)  # Built-in sum returns zero.
    (<class 'float'>, Fraction(1000, 1), 3000)
    Fractions and Decimals are also supported:
    >>> from fractions import Fraction as F
    >>> _sum([F(2, 3), F(7, 5), F(1, 4), F(5, 6)])
    (<class 'fractions.Fraction'>, Fraction(63, 20), 4)
    >>> from decimal import Decimal as D
    >>> data = [D("0.1375"), D("0.2108"), D("0.3061"), D("0.0419")]
    >>> _sum(data)
    (<class 'decimal.Decimal'>, Fraction(6963, 10000), 4)
    Mixed types are currently treated as an error, except that int is
    allowed.
    """
    count = 0
    n, d = _exact_ratio(start)
    partials = {d: n}
    partials_get = partials.get
    T = _coerce(int, type(start))
    for typ, values in groupby(data, type):
        T = _coerce(T, typ)  # or raise TypeError
        for n,d in map(_exact_ratio, values):
            count += 1
            partials[d] = partials_get(d, 0) + n
    if None in partials:
        # The sum will be a NAN or INF. We can ignore all the finite
        # partials, and just look at this special one.
        total = partials[None]
        assert not _isfinite(total)
    else:
        # Sum all the partial sums using builtin sum.
        # FIXME is this faster if we sum them in order of the denominator?
        total = sum(Fraction(n, d) for d, n in sorted(partials.items()))
    return (T, total, count)

Il existe une multitude d'opérations qui se passe dans la comparaison de simplement appeler l'builtin sum, selon la doc cordes mean calcule une haute précision de la somme.

Vous pouvez voir l'aide moyenne de vs somme peut vous donner de sortie différents:

In [7]: l = [.1, .12312, 2.112, .12131]

In [8]: sum(l) / len(l)
Out[8]: 0.6141074999999999

In [9]: mean(l)
Out[9]: 0.6141075

Answer 4

Les deux len() et sum() sont Python fonctions internes (avec des fonctionnalités limitées), qui sont écrites en C et, plus important encore, sont optimisés pour travailler rapidement avec certains types ou des objets (liste).

Vous pouvez regarder la mise en œuvre de fonctions internes ici:

https://hg.python.org/sandbox/python2.7/file/tip/Python/bltinmodule.c

Les statistiques.moyenne() est un haut de niveau de la fonction écrite en Python. Jetez un coup d'oeil ici à la façon dont il est mis en œuvre:

https://hg.python.org/sandbox/python2.7/file/tip/Lib/statistics.py

Vous pouvez voir que plus tard utilise en interne une autre fonction appelée _sum(), qui fait quelques vérifications supplémentaires par rapport aux fonctions internes.

Answer 5

Selon ce post: Le calcul de la moyenne arithmétique (moyenne) en Python

Il doit être "grâce à une très précises de mise en œuvre de la somme de l'opérateur dans les statistiques".

La moyenne de la fonction est codée avec un intérieur _sum fonction qui est censé être plus précis que la normale, mais ce qui est beaucoup plus lent (code disponible ici: https://hg.python.org/cpython/file/3.5/Lib/statistics.py).

Il est spécifié dans le PEP: https://www.python.org/dev/peps/pep-0450/ La précision est jugée plus importante que la vitesse de ce module.