Perché statistics.mean() è lento?

Question

Ho confrontato le prestazioni della funzione mean del modulo statistics con il metodo semplice sum(l)/len(l) e ho trovato la funzione mean molto lenta per qualche motivo. Ho usato timeit con i due snippet di codice qui sotto per confrontarli, qualcuno sa che cosa causa l'enorme differenza nella velocità di esecuzione? Sto usando 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))) 

Il codice sopra viene eseguito in circa 0,043 secondi sulla mia macchina.

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))) 

Il codice di cui sopra viene eseguito in circa 0,000,565 mila secondi sulla mia macchina.

Answer 1

modulo di Python statistics non è costruito per la velocità, ma per la precisione

In the specs for this module, sembra che

La somma incorporata può perdere la precisione quando si ha a che fare con float di grandezza variabile pari a . Di conseguenza, quanto sopra medio naif non supera questo "torture test"

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

ritorno 0 invece di 1, un errore puramente computazionale di 100%.

L'utilizzo di math.fsum all'interno della media lo renderà più accurato con i dati float , ma ha anche l'effetto collaterale di convertire qualsiasi argomento in float anche se non necessario. Per esempio. dovremmo aspettarci che la media di una lista di Frazioni sia una frazione, non un float.

Al contrario, se diamo uno sguardo alla realizzazione di _sum() in questo modulo, le prime righe del docstring del metodo di seem to confirm that:

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. 

    [...] """ 

Quindi sì, statistics attuazione sum, invece di essere un semplice chiamata one-liner alla funzione incorporata di Python sum(), occupa circa 20 linee da sola con un ciclo nidificato for nel suo corpo.

Questo succede perché statistics._sum sceglie di garantire la massima precisione per tutti i tipi di numero che potrebbe incontrare (anche se sono molto diversi tra loro), invece di enfatizzare semplicemente la velocità.

Quindi, sembra normale che l'sum integrato sia cento volte più veloce. Il costo di una precisione molto inferiore in te è che lo chiami con numeri esotici.

Altre opzioni

Se è necessario dare la priorità di velocità in algoritmi, si dovrebbe avere uno sguardo a Numpy invece, gli algoritmi di cui in corso di attuazione in C.

NumPy significa che non è così precisa come statistics da un colpo lungo ma implementa (dal 2013) uno routine based on pairwise summation che è meglio di un ingenuo sum/len (maggiori informazioni nel link).

Tuttavia ...

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

Secondo tale posto: Calculating arithmetic mean (average) in Python

Dovrebbe essere "dovuto ad un particolarmente precisa attuazione dell'operatore somma statistiche".

La funzione media è codificata con una funzione interna _sum che dovrebbe essere più precisa dell'aggiunta normale ma che è molto più lenta (codice disponibile qui: https://hg.python.org/cpython/file/3.5/Lib/statistics.py).

è specificato nel PEP: https://www.python.org/dev/peps/pep-0450/ precisione è considerato più importante quanto la velocità per quel modulo.

Answer 3

ho chiesto la stessa domanda un po 'indietro, ma una volta ho notato che la funzione _sum chiamata in media on line 317 nella sorgente ho capito perché:

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) 

v'è una moltitudine di operazioni accadendo in confronto al solo chiamando l'integrato sum, secondo le stringhe doc mean calcola una somma ad alta precisione .

Si può vedere usando media vs somma può dare output diverso:

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

se si fa cura di usare la velocità NumPy/SciPy/panda invece:

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 

Conclusione: sarà ordini di grandezza più veloci - nel mio esempio era 700 volte più veloce, ma forse non così preciso (dato che numpy non usa l'algoritmo di sommatoria di Kahan).

Answer 5

Sia len() che sum() sono funzioni incorporate di Python (con funzionalità limitate), scritte in C e, cosa più importante, ottimizzate per funzionare velocemente con determinati tipi o oggetti (elenco).

Può consultare l'implementazione di funzioni built-in qui:

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

Lo statistics.mean() è una funzione di alto livello scritto in Python. Date un'occhiata qui a come viene implementato:

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

Si può vedere che in seguito utilizza internamente un'altra funzione chiamata _sum(), che fa un paio di controlli supplementari rispetto alle funzioni interne.