列出运行总计的理解

Question

我想从一个数字列表中获得一个总计.

出于演示目的,我从使用的顺序数字列表开始 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)

产量

  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

如您所见,我初始化一个空列表[],然后append()在每个循环迭代中.是否有更优雅的方式,如列表理解？

Answer 1

列表理解没有好的(干净的,可移植的)方式来引用它正在构建的列表.一个好的和优雅的方法可能是在生成器中完成工作:

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

当然,使用,将此作为列表list(running_sum(a)).

Answer 2

如果你可以使用numpy,它有一个名为的内置函数cumsum.

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

Answer 3

这可以在Python中用2行实现.

使用默认参数消除了在外部维护辅助变量的需要,然后我们只map对列表执行操作.

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

Answer 4

我不确定'优雅',但我认为以下更简单,更直观(以额外变量为代价):

a = range(20)

runningTotal = []

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

做同样事情的功能方法是:

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

......但是那些可读性/维护性较差等等.

@Omnifarous建议将其改进为:

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

......但我仍然发现,比我最初的建议更难以理解.

请记住Kernighan的话:"调试的难度是首先编写代码的两倍.因此,如果您尽可能巧妙地编写代码,那么根据定义,您不够聪明,无法对其进行调试."

Answer 5

当我们取一个列表的总和时,我们指定一个accumulator(memo),然后遍历列表,将二进制函数"x + y"应用于每个元素和累加器.程序上,这看起来像:

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

这是一种常见模式,除了获取总和之外的其他东西很有用 - 我们可以将它概括为任何二元函数,我们将其作为参数提供,并让调用者指定初始值.这给我们称为函数reduce,foldl或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)

在Python 2中,reduce是一个内置函数,但在Python 3中它已被移动到functools模块:

from functools import reduce

我们可以reduce根据我们提供的功能作为第一个参数来做各种很酷的事情.如果我们将"sum"替换为"list concatenation",将"zero"替换为"empty list",我们得到(浅)copy函数:

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

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

如果我们将一个transform函数添加为另一个参数copy,并在连接之前应用它,我们得到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]

如果我们添加一个predicate函数e作为参数并返回一个布尔值,并使用它来决定是否连接,我们得到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并且filter是编写列表理解的一种不切实际的方式 - 我们也可以说[x*2 for x in range(10)]或者[x for x in range(10) if x%2==0].没有相应的列表理解语法reduce,因为reduce根本不需要返回列表(正如我们之前看到的sum那样,Python也恰好作为内置函数提供).

事实证明,为了计算一个运行总和,列表构建能力reduce正是我们想要的,并且可能是解决这个问题的最优雅的方式,尽管它的声誉(以及lambda)作为一种非pythonic shibboleth的东西.它的版本在运行时reduce留下其旧值的副本被调用reductions或scanl^[1],它看起来像这样:

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

如此装备,我们现在可以定义:

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]

虽然在概念上很优雅,但这种精确的方法在Python的实践中表现不佳.因为Python list.append()改变了列表但没有返回它,我们不能在lambda中有效地使用它,+而是必须使用运算符.这构造了一个全新的列表,其占用的时间与累积列表的长度成比例(即O(n)操作).由于我们已经在O(n)for循环中,reduce当我们这样做时,总体时间复杂度复合到O(n ²).

在像Ruby ^[2]这样的语言中,array.push e返回mutated array,等价在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]

在JavaScript ^{[2]中也是如此},其array.push(e)返回e(不是array),但其匿名函数允许我们包含多个语句,我们可以使用它们来单独指定返回值:

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]

那么,我们如何解决这个问题,同时保留reductions我们刚刚传递lambda x, y: x + y给函数的概念简单性以创建运行和函数？让我们在reductions程序上重写.我们可以修复意外的二次问题,当我们处理它时,预先分配结果列表以避免堆栈抖动^[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]

这对我来说是个好消息:O(n)性能,优化的过程代码隐藏在一个有意义的名称下,下次当你需要编写一个将中间值累积到列表中的函数时,它可以被重用.

1. 名称reduce/ reductions来自LISP传统,foldl/ scanlML传统和injectSmalltalk传统.
2. Python List和Ruby Array都是自动调整大小的数据结构的实现,称为"动态数组"(或std::vector在C++中).JavaScript Array是一个更加巴洛克式的,但行为相同,只要您不指定超出范围的索引或变异Array.length.
3. 每次列表的长度超过2的幂时,在Python运行时中形成列表的后备存储的动态数组将自行调整大小.调整列表大小意味着在堆的新列表上分配旧列表的两倍,将旧列表的内容复制到新列表中,并将旧列表的内存返回给系统.这是一个O(n)操作,但是因为随着列表变得越来越大,它的发生频率越来越低,所以附加到列表的时间复杂度在平均情况下达到O(1).但是,旧列表留下的"洞"有时难以回收,具体取决于它在堆中的位置.即使使用垃圾收集和强大的内存分配器,预先分配已知大小的数组也可以为底层系统节省一些工作.在没有操作系统优势的嵌入式环境中,这种微观管理变得非常重要.

Answer 6

使用itertools.accumulate().这是一个例子:

from itertools import accumulate

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

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

这仅适用于Python 3.在Python 2上,您可以在more-itertools包中使用backport .