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