Учет списка для общего количества

Ответ 1

У понимания списка нет хорошего (чистого, портативного) способа ссылаться на тот самый список, который он строит. Один хороший и элегантный подход может заключаться в том, чтобы выполнить работу в генераторе:

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

чтобы вместо этого использовать это как список, используйте list(running_sum(a)).

Ответ 2

Если вы можете использовать numpy, у него есть встроенная функция с именем cumsum, которая делает это.

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

Ответ 3

Это может быть реализовано в 2 строках в Python.

Использование параметра по умолчанию устраняет необходимость сохранения внешней переменной aux, а затем мы просто делаем map в списке.

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

Ответ 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])

... но я до сих пор считаю это менее понятным, чем мое первоначальное предложение.

Помните слова Кернигана: "Отладка в два раза сложнее, чем запись кода в первую очередь. Поэтому, если вы пишете код настолько умно, насколько это возможно, вы по определению недостаточно умны для его отладки".

Ответ 5

Когда мы берем сумму списка, мы назначаем аккумулятор (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 в зависимости от функции мы поставляем в качестве первого аргумента. Если мы заменим "сумму" на "конкатенацию списка", а "ноль" на "пустой список", мы получим (мелкую) функцию 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 выражением) как что-то непитонного шибболета., Версия 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() список на месте, но не возвращает его, мы не можем эффективно использовать его в лямбда-выражении, и вместо этого мы должны использовать оператор +. Это создает совершенно новый список, который занимает время, пропорциональное длине накопленного списка (то есть операция O (n)). Поскольку мы уже находимся внутри O (n) for цикла reduce когда мы делаем это, общая сложность по времени составляет O (n ²).

В языке, подобном Ruby ^[2] где array.push e возвращает мутированный 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]

array.push(e) же самое в 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/scanl от традиции ML, и inject от традиции Smalltalk.
2. Python List и Ruby Array являются реализациями автоматически изменяемой структуры данных, известной как "динамический массив" (или std::vector в C++). JavaScript Array немного более барочный, но ведет себя идентично, если вы не назначаете индексы за пределами границ или не Array.length.
3. Динамический массив, который формирует резервное хранилище списка во время выполнения Python, будет изменять свой размер каждый раз, когда длина списка пересекает степень двойки. Изменение размера списка означает выделение нового списка в куче, в два раза превышающего старый, копирование содержимого старого списка в новый и возврат памяти старого списка в систему. Это операция O (n), но поскольку она происходит все реже и реже, так как список становится все больше и больше, сложность времени добавления к списку в среднем составляет O (1). Тем не менее, "дыру", оставленную старым списком, иногда трудно перерабатывать, в зависимости от его положения в куче. Даже при сборке мусора и надежном распределителе памяти предварительное выделение массива известного размера может сэкономить работающим системам некоторую работу. Во встроенной среде без использования ОС этот вид микроуправления становится очень важным.

Ответ 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 вы можете использовать backport в пакете more-itertools.

Ответ 7

Я хотел сделать то же самое, чтобы генерировать кумулятивные частоты, которые я мог бы использовать bisect_left over - это то, как я создал список;

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

Ответ 8

Здесь линейное решение времени: один слот:

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

Пример:

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]

Короче говоря, сокращение идет над списком, накапливая сумму и строя список. Конечный x[0] возвращает список, x[1] будет текущим общим значением.

Ответ 9

Другой однострочный, в линейном времени и пространстве.

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

Я подчеркиваю здесь линейное пространство, потому что большинство однострочных линий, которые я видел в других предложенных ответах --- те, которые основаны на шаблоне list + [sum] или с помощью итераторов chain, генерируют O (n) списков или генераторов и так сильно стесняют сборщик мусора, что они выполняют очень плохо, по сравнению с этим.

Ответ 10

Я бы использовал сопрограмму для этого:

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

Ответ 11

Это неэффективно, поскольку он делает это каждый раз с самого начала, но возможно:

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

Ответ 12

Вы ищете две вещи: fold (уменьшить) и смешную функцию, которая хранит список результатов другой функции, которую я назвал запущенной. Я сделал версии как с начальным параметром, так и без него; в любом случае их нужно уменьшить с помощью начального [].

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)

Это займет много времени в действительно больших списках из-за оператора+. На функциональном языке, если все сделано правильно, эта конструкция списка будет O (n).

Вот первые несколько строк вывода:

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]

Ответ 13

Начиная с Python 3.8 и введением выражений присваивания (PEP 572) (:= оператор), мы можем использовать и увеличивать переменную в пределах понимания списка:

# items = range(7)
total = 0
[(x, total := total + x) for x in items]
# [(0, 0), (1, 1), (2, 3), (3, 6), (4, 10), (5, 15), (6, 21)]

Это:

• Инициализирует переменную total значение 0 что символизирует промежуточную сумму
• Для каждого элемента это оба:
  • увеличивает total на текущий зацикленный элемент (total := total + x) с помощью выражения присваивания
  • и в то же время возвращает новое значение total как часть созданного сопоставленного кортежа