python - Lista de comprensión para el total acumulado

list-comprehension running-total

Question

Quiero obtener un total acumulado de una lista de números.

Para propósitos de demostración, comienzo con una lista secuencial de números usando el range

a = range(20)

runningTotal = []
for n in range(len(a)):
    new = runningTotal[n-1] + a[n] if n > 0 else a[n]
    runningTotal.append(new)

# This one is a syntax error
# runningTotal = [a[n] for n in range(len(a)) if n == 0 else runningTotal[n-1] + a[n]]

for i in zip(a, runningTotal):
    print "{0:>3}{1:>5}".format(*i)

rendimientos

  0    0
  1    1
  2    3
  3    6
  4   10
  5   15
  6   21
  7   28
  8   36
  9   45
 10   55
 11   66
 12   78
 13   91
 14  105
 15  120
 16  136
 17  153
 18  171
 19  190

Como puede ver, inicializo una lista vacía [] , luego append() en cada iteración de bucle. ¿Hay una manera más elegante de esto, como una lista de comprensión?

Answer 1

Aquí hay una solución de tiempo lineal de un forro:

list(reduce(lambda (c,s), a: (chain(c,[s+a]), s+a), l,(iter([]),0))[0])

Ejemplo:

l = range(10)
list(reduce(lambda (c,s), a: (chain(c,[s+a]), s+a), l,(iter([]),0))[0])
>>> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

En resumen, la reducción recorre la lista acumulando la suma y construyendo una lista. La x[0] final x[0] devuelve la lista, x[1] sería el valor total actual.

Answer 2

Cuando tomamos la suma de una lista, designamos un acumulador ( memo ) y luego recorremos la lista, aplicando la función binaria "x + y" a cada elemento y al acumulador. Procedimiento, esto se parece a:

def mySum(list):
    memo = 0
    for e in list:
        memo = memo + e
    return memo

Este es un patrón común y útil para otras cosas que no sean sumas: podemos generalizarlo a cualquier función binaria, que le proporcionaremos como un parámetro, y también permitir que la persona que llama especifique un valor inicial. Esto nos da una función conocida como reduce , foldl o inject ^[1] :

def myReduce(function, list, initial):
    memo = initial
    for e in list:
        memo = function(memo, e)
    return memo

def mySum(list):
    return myReduce(lambda memo, e: memo + e, list, 0)

En Python 2, reduce era una función incorporada, pero en Python 3 se ha movido al módulo functools :

from functools import reduce

Podemos hacer todo tipo de cosas interesantes con la reduce dependiendo de la función que suministramos como su primer argumento. Si reemplazamos "suma" con "concatenación de lista", y "cero" con "lista vacía", obtenemos la función de copy (superficial):

def myCopy(list):
    return reduce(lambda memo, e: memo + [e], list, [])

myCopy(range(10))
> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Si agregamos una función de transform como otro parámetro para copy , y la aplicamos antes de concatenar, obtenemos el map :

def myMap(transform, list):
    return reduce(lambda memo, e: memo + [transform(e)], list, [])

myMap(lambda x: x*2, range(10))
> [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

Si agregamos una función de predicate que toma e como parámetro y devuelve un valor booleano, y la usamos para decidir si concatenar o no, obtenemos el filter :

def myFilter(predicate, list):
    return reduce(lambda memo, e: memo + [e] if predicate(e) else memo, list, [])

myFilter(lambda x: x%2==0, range(10))
> [0, 2, 4, 6, 8]

map y el filter son formas poco sofisticadas de escribir una lista de comprensión; también podríamos haber dicho [x*2 for x in range(10)] o [x for x in range(10) if x%2==0] . No hay una sintaxis de comprensión de lista correspondiente para reduce , porque reduce no es necesario para devolver una lista (como vimos con la sum anterior, que Python también ofrece como función integrada).

Resulta que para calcular una suma corriente, las capacidades de reduce de listas son exactamente lo que queremos, y probablemente la forma más elegante de resolver este problema, a pesar de su reputación (junto con lambda ) como una especie de shibboleth antiptónica. . La versión de reduce que deja copias de sus valores antiguos mientras se ejecuta se llama reductions o scanl ^[1] , y se ve así:

def reductions(function, list, initial):
    return reduce(lambda memo, e: memo + [function(memo[-1], e)], list, [initial])

Así equipados, ahora podemos definir:

def running_sum(list):
    first, rest = list[0], list[1:]
    return reductions(lambda memo, e: memo + e, rest, first)

running_sum(range(10))
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

Si bien es conceptualmente elegante, este enfoque preciso no tiene buenos resultados en la práctica con Python. Debido a que list.append() Python list.append() una lista en su lugar pero no la devuelve, no podemos usarla de manera efectiva en un lambda, y tenemos que usar el operador + lugar. Esto construye una lista completamente nueva, que lleva un tiempo proporcional a la longitud de la lista acumulada hasta el momento (es decir, una operación O (n)). Dado que ya estamos dentro del O (n) for bucle de reduce cuando hacemos esto, la complejidad del tiempo global se compone de O (n ² ).

En un lenguaje como Ruby ^[2] , donde array.push e devuelve la array mutada, el equivalente se ejecuta en tiempo O (n):

class Array
  def reductions(initial, &proc)
    self.reduce [initial] do |memo, e|
      memo.push proc.call(memo.last, e)
    end
  end
end

def running_sum(enumerable)
  first, rest = enumerable.first, enumerable.drop(1)
  rest.reductions(first, &:+)
end

running_sum (0...10)
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

Lo mismo en JavaScript ^[2] , cuyo array.push(e) devuelve e (no array ), pero cuyas funciones anónimas nos permiten incluir varias declaraciones, que podemos usar para especificar por separado un valor de retorno:

function reductions(array, callback, initial) {
    return array.reduce(function(memo, e) {
        memo.push(callback(memo[memo.length - 1], e));
        return memo;
    }, [initial]);
}

function runningSum(array) {
    var first = array[0], rest = array.slice(1);
    return reductions(rest, function(memo, e) {
        return x + y;
    }, first);
}

function range(start, end) {
    return(Array.apply(null, Array(end-start)).map(function(e, i) {
        return start + i;
    }
}

runningSum(range(0, 10));
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

Entonces, ¿cómo podemos resolver esto manteniendo la simplicidad conceptual de una función de reductions que le pasamos lambda x, y: x + y para crear la función de suma de ejecución? Vamos a reescribir las reductions procedimiento. Podemos solucionar el problema accidentalmente cuadrático , y mientras estamos en ello, pre-asignamos la lista de resultados para evitar el apilamiento del montón ^[3] :

def reductions(function, list, initial):
    result = [None] * len(list)
    result[0] = initial
    for i in range(len(list)):
        result[i] = function(result[i-1], list[i])
    return result

def running_sum(list):
    first, rest = list[0], list[1:]
    return reductions(lambda memo, e: memo + e, rest, first)

running_sum(range(0,10))
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

Este es el punto ideal para mí: rendimiento O (n), y el código de procedimiento optimizado está escondido bajo un nombre significativo, donde se puede reutilizar la próxima vez que necesite escribir una función que acumule valores intermedios en una lista.

1. Los nombres de reduce / reductions provienen de la tradición LISP, foldl / scanl de la tradición ML e inject de la tradición Smalltalk.
2. Python''s List y Ruby''s Array son implementaciones de una estructura de datos de redimensionamiento automático conocida como "array dinámico" (o std::vector en C ++). La Array de JavaScript es un poco más barroca, pero se comporta de forma idéntica siempre que no asigne índices fuera de límites o Array.length .
3. La matriz dinámica que forma el almacén de respaldo de la lista en el tiempo de ejecución de Python se redimensionará a sí misma cada vez que la longitud de la lista cruce una potencia de dos. Cambiar el tamaño de una lista significa asignar una nueva lista en el montón del doble del tamaño de la anterior, copiar el contenido de la lista antigua en la nueva y devolver la memoria de la lista anterior al sistema. Esta es una operación O (n), pero como ocurre cada vez con menos frecuencia a medida que la lista se hace más y más grande, la complejidad del tiempo de agregar a una lista se resuelve en O (1) en el caso promedio. Sin embargo, el "agujero" dejado por la lista anterior a veces puede ser difícil de reciclar, dependiendo de su posición en el montón. Incluso con la recolección de basura y un robusto asignador de memoria, la asignación previa de una matriz de tamaño conocido puede ahorrarle algún trabajo a los sistemas subyacentes. En un entorno integrado sin el beneficio de un sistema operativo, este tipo de microgestión se vuelve muy importante.

Answer 3

Estás buscando dos cosas: fold (reducir) y una función divertida que mantiene una lista de los resultados de otra función, a la que he llamado en ejecución. Hice versiones con y sin un parámetro inicial; De cualquier manera, estos deben ir para reducir con una inicial [].

def last_or_default(list, default):
    if len(list) > 0:
        return list[-1]
    return default

def initial_or_apply(list, f, y):
    if list == []:
        return [y]
    return list + [f(list[-1], y)]

def running_initial(f, initial):
    return (lambda x, y: x + [f(last_or_default(x,initial), y)])

def running(f):
    return (lambda x, y: initial_or_apply(x, f, y))

totaler = lambda x, y: x + y
running_totaler = running(totaler)
running_running_totaler = running_initial(running_totaler, [])

data = range(0,20)
running_total = reduce(running_totaler, data, [])
running_running_total = reduce(running_running_totaler, data, [])

for i in zip(data, running_total, running_running_total):
    print "{0:>3}{1:>4}{2:>83}".format(*i)

Esto llevará mucho tiempo en listas realmente grandes debido al operador +. En un lenguaje funcional, si se hace correctamente, esta construcción de lista sería O (n).

Aquí están las primeras líneas de salida:

0   0                      [0]
1   1                   [0, 1]
2   3                [0, 1, 3]
3   6             [0, 1, 3, 6]
4  10         [0, 1, 3, 6, 10]
5  15     [0, 1, 3, 6, 10, 15]
6  21 [0, 1, 3, 6, 10, 15, 21]

Answer 4

Esto es ineficiente ya que lo hace cada vez desde el principio, pero es posible que sea:

a = range(20)
runtot=[sum(a[:i+1]) for i,item in enumerate(a)]
for line in zip(a,runtot):
    print line

Answer 5

No estoy seguro acerca de ''elegante'', pero creo que lo siguiente es mucho más simple e intuitivo (a costa de una variable adicional):

a = range(20)

runningTotal = []

total = 0
for n in a:
  total += n
  runningTotal.append(total)

La forma funcional de hacer lo mismo es:

a = range(20)
runningTotal = reduce(lambda x, y: x+[x[-1]+y], a, [0])[1:]

... pero eso es mucho menos legible / mantenible, etc.

@Omnifarous sugiere que esto debería mejorarse para:

a = range(20)
runningTotal = reduce(lambda l, v: (l.append(l[-1] + v) or l), a, [0])

... pero todavía lo encuentro menos comprensible de inmediato que mi sugerencia inicial.

Recuerde las palabras de Kernighan: "La depuración es dos veces más difícil que escribir el código en primer lugar. Por lo tanto, si escribe el código de la manera más inteligente posible, no es lo suficientemente inteligente como para depurarlo".

Answer 6

Otro de una sola línea, en tiempo y espacio lineal.

def runningSum(a):
    return reduce(lambda l, x: l.append(l[-1]+x) or l if l else [x], a, None)

Estoy acentuando el espacio lineal aquí, porque la mayoría de las frases de una línea que vi en las otras respuestas propuestas, las basadas en la list + [sum] patrones list + [sum] o el uso de iteradores de chain --- generan listas O (n) o generadores e insista tanto en el recolector de basura que se desempeñan muy mal en comparación con esto.

Answer 7

Quería hacer lo mismo para generar frecuencias acumulativas sobre las que podría usar bisect_left - esta es la forma en que he generado la lista;

[ sum( a[:x] ) for x in range( 1, len(a)+1 ) ]

Answer 8

Si está utilizando Python3.x y superior, el módulo itertools tiene una función llamada a accumulate() que hará el truco.

Aquí hay un ejemplo:

from itertools import accumulate

a = range(20)
runningTotals = list(accumulate(a))

for i in zip(a, runningTotals):
    print "{0:>3}{1:>5}".format(*i)

Answer 9

Si puede usar numpy , tiene una función cumsum llamada cumsum que hace esto.

import numpy
tot = numpy.cumsum(a)  # returns a numpy.ndarray
tot = list(tot)        # if you prefer a list

Answer 10

Una lista de comprensión no tiene una manera buena (limpia, portátil) de referirse a la lista que está creando. Un enfoque bueno y elegante podría ser hacer el trabajo en un generador:

def running_sum(a):
  tot = 0
  for item in a:
    tot += item
    yield tot

por supuesto, para obtener esto como una lista, por supuesto, use list(running_sum(a)) .

Answer 11

Yo usaría una coroutina para esto:

def runningTotal():
    accum = 0
    yield None
    while True:
        accum += yield accum

tot = runningTotal()
next(tot)
running_total = [tot.send(i) for i in xrange(N)]

Answer 12

Esto se puede implementar en 2 líneas en Python.

El uso de un parámetro predeterminado elimina la necesidad de mantener una variable auxiliar fuera, y luego simplemente hacemos un map a la lista.

def accumulate(x, l=[0]): l[0] += x; return l[0];
map(accumulate, range(20))