deepcopy and python - consejos para evitar usarlo?

Question

Tengo una rutina de pitón muy simple que implica recorrer una lista de aproximadamente 20,000 coordenadas de latitud y longitud y calcular la distancia de cada punto a un punto de referencia.

def compute_nearest_points(lat, lon, nPoints=5): 
    """Find the nearest N points, given the input coordinates.""" 

    points = session.query(PointIndex).all() 
    oldNearest = [] 
    newNearest = [] 
    for n in xrange(nPoints): 
     oldNearest.append(PointDistance(None,None,None,99999.0,99999.0)) 
     newNearest.append(obj2) 

    #This is almost certainly an inappropriate use of deepcopy 
    # but how SHOULD I be doing this?!?! 
    for point in points: 
     distance = compute_spherical_law_of_cosines(lat, lon, point.avg_lat, point.avg_lon) 
     k = 0 
     for p in oldNearest: 
      if distance < p.distance: 
       newNearest[k] = PointDistance(
        point.point, point.kana, point.english, point.avg_lat, point.avg_lon, distance=distance 
        ) 
       break 
      else: 
       newNearest[k] = deepcopy(oldNearest[k]) 
      k += 1 
     for j in range(k,nPoints-1): 
      newNearest[j+1] = deepcopy(oldNearest[j]) 
     oldNearest = deepcopy(newNearest) 

    #We're done, now print the result 
    for point in oldNearest: 
     print point.station, point.english, point.distance 

    return 

al principio me escribió esto en C, utilizando el mismo enfoque exacto, y trabaja muy bien allí, y es básicamente instantánea para NPOINTS < = 100. Así que decidí portarlo a Python porque quería usar SqlAlchemy para hacer otras cosas.

Lo porté por primera vez sin las declaraciones de copia profunda que ahora salpican el método, y esto causó que los resultados fueran "impares" o parcialmente incorrectos, porque algunos de los puntos solo se copiaban como referencias (¿supongo? ?) - pero todavía era casi tan rápido como la versión C.

Ahora, con las llamadas deepcopy añadidas, la rutina hace su trabajo correctamente, pero ha incurrido en una penalización de rendimiento extremo, y ahora lleva varios segundos hacer el mismo trabajo.

Esto parece ser un trabajo bastante común, pero evidentemente no lo estoy haciendo de manera pitonica. ¿Cómo debería estar haciendo esto para poder obtener los resultados correctos, pero no tengo que incluir una copia profunda en todas partes?

EDIT:
He golpeado en una solución mucho más simple y más rápido,

def compute_nearest_points2(lat, lon, nPoints=5): 
    """Find the nearest N points, given the input coordinates.""" 

    points = session.query(PointIndex).all() 
    nearest = [] 

    for point in points: 
     distance = compute_spherical_law_of_cosines(lat, lon, point.avg_lat, point.avg_lon) 
     nearest.append( 
      PointDistance(
       point.point, point.kana, point.english, point.avg_lat, point.avg_lon, distance=distance 
       ) 
      ) 

    nearest_points = sorted(nearest, key=lambda point: point.distance)[:nPoints]  
    for item in nearest_points: 
     print item.point, item.english, item.distance 
    return 

Así que, básicamente, sólo estoy haciendo una copia completa de la entrada y la introducción de un nuevo valor - la distancia desde la punto de referencia. Luego, simplemente aplico 'ordenado' a la lista resultante, especificando que la clave de clasificación debe ser la propiedad de distancia del objeto PointDistance.

Esto es mucho más rápido que usar Deepcopy aunque confieso que realmente no entiendo por qué. ¿Supongo que se debe a las eficientes implementaciones de C python "ordenadas"?

Answer 1

Está bien, las cosas más simples primero:

1. deepcopy es lento, en general, ya que tiene que hacer un montón de contabilidad interna para copiar casos patológicos como los objetos que contienen a sí mismos de una manera sana. Ver, por ejemplo, this page, o echar un vistazo al código fuente de deepcopy en copy.py que está en algún lugar de su ruta de Python.

2. sorted es rápido, ya que se implementa en C. Es mucho más rápido que un tipo equivalente en Python.

Ahora, algo más acerca del comportamiento de recuento de referencias de Python como lo pidió en su comentario. En Python, las variables son referencias. Cuando diga a=1, piense que tiene 1 como un objeto existente y a es solo una etiqueta adjunta. En algunos otros lenguajes como C, las variables son contenedores (no etiquetas), y cuando lo hace a=1, realmente pone 1 en a. Esto no es válido para Python, donde las variables son referencias.Esto tiene algunas consecuencias interesantes que puede que también se han topado con:

>>> a = []  # construct a new list, attach a tag named "a" to it 
>>> b = a  # attach a tag named "b" to the object which is tagged by "a" 
>>> a.append(1) # append 1 to the list tagged by "a" 
>>> print b  # print the list tagged by "b" 
[1] 

Este comportamiento se ve porque las listas mutables objetos: se puede modificar una lista después de haber creado, y la modificación se ve cuando se accede la lista a través de cualquiera de las variables que se refieren a ella. Los inmutables equivalentes de listas son tuplas:

>>> a =()  # construct a new tuple, attach a tag named "a" to it 
>>> b = a  # now "b" refers to the same empty tuple as "a" 
>>> a += (1, 2) # appending some elements to the tuple 
>>> print b 
() 

Aquí, a += (1, 2) crea una nueva tupla de la tupla vigentes mencionados por a, más otra tupla (1, 2) que se construye sobre la marcha, y a se ajusta para apuntar a la nueva tupla, mientras que por supuesto b todavía se refiere a la antigua tupla. Lo mismo ocurre con adiciones numéricas simples como a = a+2: en este caso, el número apuntado originalmente por a no está mutado de ninguna manera, Python "construye" un nuevo número y mueve a para apuntar al nuevo número. Entonces, en pocas palabras: los números, las cuerdas y las tuplas son inmutables; listas, dictados y conjuntos son mutables. Las clases definidas por el usuario son en general mutables a menos que se asegure explícitamente que el estado interno no puede ser mutado. Y está frozenset, que es un conjunto inmutable. Además de muchos otros, por supuesto :)

No sé por qué el código original no funcionó, pero probablemente tocas un comportamiento relacionado con el fragmento de código que he mostrado con las listas ya que tu clase PointDistance también es mutable por defecto. Una alternativa podría ser la clase namedtuple de collections, que construye un objeto tipo tupla cuyos campos también se puede acceder por nombres. Por ejemplo, se podría haber hecho esto:

from collections import namedtuple 
PointDistance = namedtuple("PointDistance", "point distance") 

Esto crea una clase PointDistance para usted que tiene dos campos denominados: point y distance. En su ciclo principal for, puede asignarlos de forma adecuada. Dado que los objetos puntuales señalados por los campos point no se modificarán durante el transcurso de su ciclo for, y distance es un número (que, por definición, es inmutable), debe estar seguro haciendo esto. Pero sí, en general, parece que simplemente usar sorted es más rápido ya que sorted está implementado en C. También podría ser afortunado con el módulo heapq, que implementa una estructura de datos de pila respaldada por una lista ordinaria de Python, por lo tanto le permite encontrar el arriba k elementos fácilmente sin tener que ordenar los demás. Sin embargo, dado que heapq también se implementa en Python, es probable que sorted funcione mejor a menos que tenga muchos puntos.

Por último, me gustaría añadir que nunca tuve que usar deepcopy hasta ahora, así que supongo que hay formas de evitarlo en la mayoría de los casos.

Answer 2

Entiendo que esto no aborda directamente su pregunta (y sé que esta es una pregunta antigua), pero dado que hay cierta discusión sobre el rendimiento, puede valer la pena observar la operación append. Es posible que desee considerar "preasignar" la matriz.Por ejemplo:

array = [None] * num_elements 
for i in range(num_elements): 
    array[i] = True 

frente:

array = [] 
for i in range(num_elements): 
    array.append(True) 

Un simple timeit ejecución de estos dos métodos muestra una mejora del 25% si se pre-asignar la matriz, incluso para valores moderados de num_elements.