Оптимизировать генератор для многовариантных полиномиальных показателей - PullRequest
Новая
       17

Оптимизировать генератор для многовариантных полиномиальных показателей

3 голосов
/ 06 февраля 2011

HI, я пытаюсь найти общее выражение для получения показателей многовариантного многочлена порядка order и с n_variables, подобно тому, которое представлено в этой ссылке в уравнении (3).

Вот мой текущий код, который использует генератор itertools.product. 

def generalized_taylor_expansion_exponents( order, n_variables ):
    """
    Find the exponents of a multivariate polynomial expression of order
    `order` and `n_variable` number of variables. 
    """
    exps = (p for p in itertools.product(range(order+1), repeat=n_variables) if sum(p) <= order)
    # discard the first element, which is all zeros..
    exps.next()
    return exps

Требуется следующее: 

for i in generalized_taylor_expansion_exponents(order=3, n_variables=3): 
    print i

(0, 0, 1)
(0, 0, 2)
(0, 0, 3)
(0, 1, 0)
(0, 1, 1)
(0, 1, 2)
(0, 2, 0)
(0, 2, 1)
(0, 3, 0)
(1, 0, 0)
(1, 0, 1)
(1, 0, 2)
(1, 1, 0)
(1, 1, 1)
(1, 2, 0)
(2, 0, 0)
(2, 0, 1)
(2, 1, 0)
(3, 0, 0)

На самом деле этот код выполняется быстро, потому что объект генератора только создан.Если я хочу заполнить список значениями из этого генератора, выполнение действительно начинает выполняться медленно, в основном из-за большого количества вызовов sum.Типичное значение для order и n_variables составляет 5 и 10. соответственно.

Как я могу значительно улучшить скорость выполнения?

Спасибо за любую помощь.

Davide Lasagna

Ответы [ 2 ]

2 голосов
/ 06 февраля 2011

На самом деле ваша самая большая проблема с производительностью заключается в том, что большинство генерируемых вами кортежей слишком велики и должны быть выброшены. Следующее должно генерировать именно те кортежи, которые вы хотите. 

def generalized_taylor_expansion_exponents( order, n_variables ):
    """
    Find the exponents of a multivariate polynomial expression of order
    `order` and `n_variable` number of variables. 
    """
    pattern = [0] * n_variables
    for current_sum in range(1, order+1):
        pattern[0] = current_sum
        yield tuple(pattern)
        while pattern[-1] < current_sum:
            for i in range(2, n_variables + 1):
                if 0 < pattern[n_variables - i]:
                    pattern[n_variables - i] -= 1
                    if 2 < i:
                        pattern[n_variables - i + 1] = 1 + pattern[-1]
                        pattern[-1] = 0
                    else:
                        pattern[-1] += 1
                    break
            yield tuple(pattern)
        pattern[-1] = 0
0 голосов
/ 06 февраля 2011

Я бы попробовал написать это рекурсивно, чтобы генерировать только нужные элементы: 

def _gtee_helper(order, n_variables):
    if n_variables == 0:
        yield ()
        return
    for i in range(order + 1):
        for result in _gtee_helper(order - i, n_variables - 1):
            yield (i,) + result


def generalized_taylor_expansion_exponents(order, n_variables):
    """
    Find the exponents of a multivariate polynomial expression of order
    `order` and `n_variable` number of variables. 
    """
    result = _gtee_helper(order, n_variables)
    result.next() # discard the first element, which is all zeros
    return result
...