Как оптимизировать вложенный цикл for с помощью NumPy (возможно, с трансляцией)? - PullRequest
Новая
       86

Как оптимизировать вложенный цикл for с помощью NumPy (возможно, с трансляцией)?

0 голосов
/ 04 октября 2019

Я пытаюсь оптимизировать некоторый код из пакета teneto. В частности, следующие функции bezier_points, make_bezier, pascal_row

Вот оригинальная реализация: https://teneto.readthedocs.io/en/latest/_modules/teneto/plot/slice_plot.html#slice_plot

Вот моя реализация: 

import numpy as np

def bezier_points(p1, p2, number_of_nodes, granularity=20):
    """
    Credit: William Hedley Thompson
    https://teneto.readthedocs.io/en/latest/_modules/teneto/plot/slice_plot.html#slice_plot

    This has been adapted from the teneto package. 
    """
    def pascal_row(n):
        # This returns the nth row of Pascal's Triangle
        result = [1]
        x, numerator = 1, n
        for denominator in range(1, n // 2 + 1):
            x *= numerator
            x /= denominator
            result.append(x)
            numerator -= 1
        if n & 1 == 0:
            # n is even
            result.extend(reversed(result[:-1]))
        else:
            result.extend(reversed(result))
        return np.asarray(result)
    # These two functions originated from the plot.ly's documentation for python API.
    # They create points along a curve.
    def make_bezier(points):
        # xys should be a sequence of 2-tuples (Bezier control points)
        n = len(points)
        combinations = pascal_row(n - 1)

        def bezier(ts):
            # This uses the generalized formula for bezier curves
            # http://en.wikipedia.org/wiki/B%C3%A9zier_curve#Generalization
            result = []
            for t in ts:
                tpowers = np.power(np.ones_like(n)*t, np.arange(n))
                upowers = np.power(np.ones_like(n)*(1-t), np.arange(n))[::-1]
                coefs = combinations*tpowers*upowers

                print((coefs * points.reshape(1,-1)).shape)
                result.append(
                    tuple(np.sum(coefs*ps) for ps in zip(*points)))
            return result
        return bezier

    ts = np.arange(granularity+1)/granularity
    d = p1[0] - (max(p1[1], p2[1]) - min(p1[1], p2[1])) / number_of_nodes
    points = np.asarray([p1, (d, p1[1]), (d, p2[1]), p2])
    bezier = make_bezier(points)
    points = bezier(ts)
    bvx = [i[0] for i in points]
    bvy = [i[1] for i in points]
    return np.asarray([bvx, bvy])

Вот как я тестирую ее в отношении исходной функции: 

gold_standard = np.asarray([[ 0.0000e+00, -1.3000e-03, -1.7000e-03, -4.5000e-04,  3.2000e-03,
         1.0000e-02,  2.0700e-02,  3.6050e-02,  5.6800e-02,  8.3700e-02,
         1.1750e-01,  1.5895e-01,  2.0880e-01,  2.6780e-01,  3.3670e-01,
         4.1625e-01,  5.0720e-01,  6.1030e-01,  7.2630e-01,  8.5595e-01,
         1.0000e+00],
       [ 0.0000e+00,  7.2500e-03,  2.8000e-02,  6.0750e-02,  1.0400e-01,
         1.5625e-01,  2.1600e-01,  2.8175e-01,  3.5200e-01,  4.2525e-01,
         5.0000e-01,  5.7475e-01,  6.4800e-01,  7.1825e-01,  7.8400e-01,
         8.4375e-01,  8.9600e-01,  9.3925e-01,  9.7200e-01,  9.9275e-01,
         1.0000e+00]])
output = bezier_points([0,0], [1,1], 100, 20)
np.allclose(output, gold_standard)

Часть, которую я не могу понять, как оптимизировать с помощью NumPy, - это следующая строка:

result.append(tuple(sum([coef * p for coef, p in zip(coefs, ps)]) for ps in zip(*xys)))

Лучше всего я могу сделать это следующим образом (заметьте, я изменил xys на points):

result.append(tuple(np.sum(coefs*ps) for ps in zip(*points)))

Кто-нибудь знает, какоптимизировать этот цикл for с помощью NumPy?

...