Упорядоченное уменьшение для нескольких функций в Python

Question

Упорядоченный список сокращения

Мне нужно сократить некоторые списки, в которых, в зависимости от типов элементов, скорость и реализация двоичной операции различаются, то есть можно добиться значительного снижения скорости, уменьшив сначала несколько пар с определенными функциями. Например foo(a[0], bar(a[1], a[2])) может быть намного медленнее, чем bar(foo(a[0], a[1]), a[2]) но в этом случае дают тот же результат.

У меня есть код, который производит оптимальный порядок в виде списка кортежей (pair_index, binary_function) уже. Я изо всех сил пытаюсь реализовать эффективную функцию для выполнения сокращения, в идеале такую, которая возвращает новую частичную функцию, которая затем может многократно использоваться в списках с одинаковым упорядочением типов, но с различными значениями.

Простое и медленное (?) Решение

Вот мое наивное решение, включающее цикл for, удаление элементов и замыкание над (pair_index, binary_function) список для возврата "предварительно вычисленной" функции.

def ordered_reduce(a, pair_indexes, binary_functions, precompute=False):
    """
    a: list to reduce, length n
    pair_indexes: order of pairs to reduce, length (n-1)
    binary_functions: functions to use for each reduction, length (n-1)
    """
    def ord_red_func(x):
        y = list(x)  # copy so as not to eat up
        for p, f in zip(pair_indexes, binary_functions):
            b = f(y[p], y[p+1])
            # Replace pair
            del y[p]
            y[p] = b
        return y[0]

    return ord_red_func if precompute else ord_red_func(a)

>>> foos = (lambda a, b: a - b, lambda a, b: a + b, lambda a, b: a * b)
>>> ordered_reduce([1, 2, 3, 4], (2, 1, 0), foos)
1
>>> 1 * (2 + (3-4))
1

И как работает предварительное вычисление:

>>> foo = ordered_reduce(None, (0, 1, 0), foos)
>>> foo([1, 2, 3, 4])
-7
>>> (1 - 2) * (3 + 4)
-7

Однако это включает в себя копирование всего списка, а также (следовательно?) Медленно. Есть ли лучший / стандартный способ сделать это?

(РЕДАКТИРОВАТЬ:) Некоторые сроки:

from operators import add
from functools import reduce
from itertools import repeat
from random import random

r = 100000
xs = [random() for _ in range(r)]
# slightly trivial choices of pairs and functions, to replicate reduce
ps = [0]*(r-1)
fs = repeat(add)
foo = ordered_reduce(None, ps, fs, precompute=True)

>>> %timeit reduce(add, xs)
100 loops, best of 3: 3.59 ms per loop
>>> %timeit foo(xs)
1 loop, best of 3: 1.44 s per loop

Это своего рода сценарий наихудшего случая, и немного обмануть, так как Reduce не требует повторяющихся функций, но функция, которая выполняет (но не порядок), все еще довольно быстрая:

def multi_reduce(fs, xs):
    xs = iter(xs)
    x = next(xs)
    for f, nx in zip(fs, xs):
        x = f(x, nx)
    return x

>>> %timeit multi_reduce(fs, xs)
100 loops, best of 3: 8.71 ms per loop

(РЕДАКТИРОВАТЬ 2): и для удовольствия, производительность массированной читерской "скомпилированной" версии, которая дает некоторое представление о суммарных накладных расходах.

from numba import jit

@jit(nopython=True)
def numba_sum(xs):
    y = 0
    for x in xs:
        y += x
    return y

>>> %timeit numba_sum(xs)
1000 loops, best of 3: 1.46 ms per loop

Answer 1

Когда я прочитал эту проблему, я сразу подумал об обратной польской записи (RPN). Хотя это может быть не самый лучший подход, он все же дает существенное ускорение в этом случае.

Моя вторая мысль заключается в том, что вы можете получить эквивалентный результат, если просто изменить порядок последовательности xs соответственно избавиться от del y[p], (Возможно, лучшая производительность была бы достигнута, если бы вся процедура уменьшения была написана на C. Но это другой котелок рыбы.)

Обратная польская запись

Если вы не знакомы с RPN, прочитайте краткое объяснение в статье в Википедии. В принципе, все операции могут быть записаны без скобок, например (1-2)*(3+4) является 1 2 - 3 4 + * в РПН, пока 1-(2*(3+4)) становится 1 2 3 4 + * -,

Вот простая реализация парсера RPN. Я отделил список объектов от последовательности RPN, чтобы одну и ту же последовательность можно было использовать непосредственно для разных списков.

def rpn(arr, seq):
    '''
    Reverse Polish Notation algorithm
    (this version works only for binary operators)
    arr: array of objects 
    seq: rpn sequence containing indices of objects from arr and functions
    '''
    stack = []
    for x in seq:
        if isinstance(x, int):
        # it's an object: push it to stack
            stack.append(arr[x])
        else:
        # it's a function: pop two objects, apply the function, push the result to stack 
            b = stack.pop()
            #a = stack.pop()
            #stack.append(x(a,b))
            ## shortcut:
            stack[-1] = x(stack[-1], b)
    return stack.pop()

Пример использования:

# Say we have an array 
arr = [100, 210, 42, 13] 
# and want to calculate 
(100 - 210) * (42 + 13) 
# It translates to RPN: 
100 210 - 42 13 + * 
# or 
arr[0] arr[1] - arr[2] arr[3] + * 
# So we apply `
rpn(arr,[0, 1, subtract, 2, 3, add, multiply])

Чтобы применить RPN к вашему делу, вам нужно либо сгенерировать последовательности rpn с нуля, либо конвертировать ваши (pair_indexes, binary_functions) в них. Я не думал о конвертере, но это, безусловно, можно сделать.

тесты

Ваш оригинальный тест на первом месте:

r = 100000
xs = [random() for _ in range(r)]
ps = [0]*(r-1)
fs = repeat(add)
foo = ordered_reduce(None, ps, fs, precompute=True)
rpn_seq = [0] + [x for i, f in zip(range(1,r), repeat(add)) for x in (i,f)]
rpn_seq2 = list(range(r)) + list(repeat(add,r-1))
# Here rpn_seq denotes (_ + (_ + (_ +( ... )...))))
# and rpn_seq2 denotes ((...( ... _)+ _) + _).
# Obviously, they are not equivalent but with 'add' they yield the same result. 

%timeit reduce(add, xs)
100 loops, best of 3: 7.37 ms per loop
%timeit foo(xs)
1 loops, best of 3: 1.71 s per loop
%timeit rpn(xs, rpn_seq)
10 loops, best of 3: 79.5 ms per loop
%timeit rpn(xs, rpn_seq2)
10 loops, best of 3: 73 ms per loop

# Pure numpy just out of curiosity:
%timeit np.sum(np.asarray(xs))
100 loops, best of 3: 3.84 ms per loop
xs_np = np.asarray(xs)
%timeit np.sum(xs_np)
The slowest run took 4.52 times longer than the fastest. This could mean that an intermediate result is being cached 
10000 loops, best of 3: 48.5 µs per loop

Так, rpn был в 10 раз медленнее, чем reduce но примерно в 20 раз быстрее, чем ordered_reduce,

Теперь давайте попробуем что-нибудь более сложное: попеременно добавление и умножение матриц. Мне нужна специальная функция для проверки reduce,

add_or_dot_b = 1
def add_or_dot(x,y):
    '''calls 'add' and 'np.dot' alternately'''
    global add_or_dot_b
    if add_or_dot_b:
        out = x+y
    else:
        out = np.dot(x,y)
    add_or_dot_b = 1 - add_or_dot_b
    # normalizing out to avoid `inf` in results
    return out/np.max(out)

r = 100001      # +1 for convenience
                # (we apply an even number of functions) 
xs = [np.random.rand(2,2) for _ in range(r)]
ps = [0]*(r-1)
fs = repeat(add_or_dot)
foo = ordered_reduce(None, ps, fs, precompute=True)
rpn_seq = [0] + [x for i, f in zip(range(1,r), repeat(add_or_dot)) for x in (i,f)]

%timeit reduce(add_or_dot, xs)
1 loops, best of 3: 894 ms per loop
%timeit foo(xs)
1 loops, best of 3: 2.72 s per loop
%timeit rpn(xs, rpn_seq)
1 loops, best of 3: 1.17 s per loop

Вот, rpn был примерно на 25% медленнее, чем reduce и более чем в 2 раза быстрее, чем ordered_reduce,