python - Cython - 计算 2D 坐标之间的距离数组

Question

我有一个函数，它使用生成器循环遍历大型 2D python 浮点坐标列表，以创建表示坐标之间距离的平面整数列表。

point_input = {"x": -8081441.0, "y": 5685214.0}
output = [-8081441, 5685214]

polyline_input = {"paths" : [[-8081441.0, 5685214.0], [-8081446.0, 5685216.0], [-8081442.0, 5685219.0], [-8081440.0, 5685211.0], [-8081441.0, 5685214.0]]}
output = [[-8081441, 5685214, 5, -2, -4, -3, -2, 8, 1, -3]]

polygon_input = {"rings" : [[-8081441.0, 5685214.0], [-8081446.0, 5685216.0], [-8081442.0, 5685219.0], [-8081440.0, 5685211.0], [-8081441.0, 5685214.0]]}
output = [[-8081441, 5685214, 5, -2, -4, -3, -2, 8, 1, -3]]

纯Python:

def geometry_to_distance(geometry, geometry_type):
    def calculate_distance(coords):
        iterator = iter(coords)
        previous_x, previous_y = iterator.next()
        yield int(previous_x)
        yield int(previous_y)
        for current_x, current_y in iterator:
            yield int(previous_x - current_x)
            yield int(previous_y - current_y)
            previous_x, previous_y = current_x, current_y

    if geometry_type == "POINT":
        distance_array = [int(geometry["x"]), int(geometry["y"])]
    elif geometry_type == "POLYLINE":
        distance_array = [list(calculate_distance(path)) for path in geometry["paths"]]
    elif geometry_type == "POLYGON":
        distance_array = [list(calculate_distance(ring)) for ring in geometry["rings"]]
    else:
        raise Exception("{} geometry type not supported".format(geometry_type))

    return distance_array

为了速度性能，我想使用 cython 实现相同的功能。我在 calculate_distance 函数中使用整数变量的类型声明。

cython 实现:

def geometry_to_distance(geometry, geometry_type):
    def calculate_distance(coords):
        cdef int previous_x, previous_y, current_x, current_y
        iterator = iter(coords)
        previous_x, previous_y = iterator.next()
        yield previous_x
        yield previous_y
        for current_x, current_y in iterator:
            yield previous_x - current_x
            yield previous_y - current_y
            previous_x, previous_y = current_x, current_y 

    if geometry_type == "POINT":
        distance_array = [geometry["x"], geometry["y"]]
    elif geometry_type == "POLYLINE":
        distance_array = [list(calculate_distance(path)) for path in geometry["paths"]]
    elif geometry_type == "POLYGON":
        distance_array = [list(calculate_distance(ring)) for ring in geometry["rings"]]
    else:
        raise Exception("{} geometry type not supported".format(geometry_type))

    return distance_array

这里有一个可用于对函数进行基准测试的脚本:

import time
from functools import wraps
import numpy as np
import geometry_converter as gc

def timethis(func):
    '''Decorator that reports the execution time.'''
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        end = time.time()
        print(func.__name__, end-start)
        return result
    return wrapper


def prepare_data(featCount, size):
    ''' Create arrays of polygon geometry (see polygon_input above)'''
    input = []
    for i in xrange(0, featCount):
        polygon = {"rings" : []}
        #random x,y coordinates inside a quadrant of the world bounding box in a spherical mercator (epsg:3857) projection
        ys = np.random.uniform(-20037507.0,0,size).tolist()
        xs = np.random.uniform(0,20037507.0,size).tolist()
        polygon["rings"].append(zip(xs,ys))
        input.append(polygon)
    return input

@timethis
def process_data(data):
    output = [gc.esriJson_to_CV(x, "POLYGON") for x in data]
    return output

data = prepare_data(100, 100000)
process_data(data)

是否有可以提高 cython 实现性能的改进？也许通过使用 2D cython 数组或 carray？

Answer 1

在没有生成器的情况下重写的 Python 是

In [362]: polyline_input = {"paths" : [[-8081441.0, 5685214.0], [-8081446.0, 568
     ...: 5216.0], [-8081442.0, 5685219.0], [-8081440.0, 5685211.0], [-8081441.0
     ...: , 5685214.0]]}
In [363]: output=polyline_input['paths'][0][:] # copy
In [364]: i0,j0 = output
     ...: for i,j in polyline_input['paths'][1:]:
     ...:     output.extend([i0-i, j0-j][:])
     ...:     i0,j0 = i,j
     ...:     
In [365]: output
Out[365]: [-8081441.0, 5685214.0, 5.0, -2.0, -4.0, -3.0, -2.0, 8.0, 1.0, -3.0]

我只是在考虑表达计算的替代方法。我可以使用 append 到成对列表而不是平面列表。

等效数组:

In [375]: arr=np.array(polyline_input['paths'])
In [376]: arr[1:,:]=arr[:-1,:]-arr[1:,:]
In [377]: arr.ravel().tolist()
Out[377]: [-8081441.0, 5685214.0, 5.0, -2.0, -4.0, -3.0, -2.0, 8.0, 1.0, -3.0]

忽略将列表转换为数组的成本，这看起来像是一个高效的 numpy 操作。为了在 cython 中改进它，我希望您必须将数组转换为内存 View ，并在值对上迭代 c 样式。

我忘记了为什么要切换到这种距离格式。您是否想节省一些文件空间？或者加速一些下游计算？