Cython - Berechnen eines Arrays von Entfernungen zwischen 2D-Koordinaten

Question

Ich habe eine Funktion, die einen Generator verwenden, um große 2D-Python-Listen von Float-Koordinaten zu durchlaufen, um flache Listen von ganzen Zahlen zu erstellen, die den Abstand zwischen Koordinaten darstellen.

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]] 

reine 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 

Für Speed-Leistung möchte ich cython Umsetzung derselben Funktion verwenden. Ich verwende Typdeklaration für Integer-Variablen in der calculate_distance-Funktion.

cython Umsetzung:

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 

hier ein Skript, das die Funktion zum Benchmark verwendet werden kann:

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) 

Gibt es Verbesserungen, die Leistung in der cython Implementierung erhöhen könnte? vielleicht mit 2D Cython Arrays oder Carrays?

Answer 1

Der Python, ohne den Generator neu geschrieben, ist

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] 

Ich bin nur der Ausdruck der Berechnung obwohl alternative Wege zu denken. Ich hätte append zu einer Liste der Paare anstelle der flachen Liste verwenden können.

Ein Array äquivalent:

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] 

Ignoriert die Kosten für eine Liste zu Array Umwandeln das aussieht wie ein effizienter numpy Betrieb. Um es in Cython zu verbessern, erwarte ich, dass Sie das Array in memoryview konvertieren und c Stil über Paare von Werten iterieren müssen.

Ich vergesse, warum Sie zu diesem Distanzformat wechseln. Versuchen Sie, Speicherplatz zu sparen? Oder beschleunigen Sie eine nachgeschaltete Berechnung?