Python: cree una función para modificar una lista por referencia, no valor

Question

Estoy haciendo un trabajo de Python crítico para el rendimiento y quiero crear una función que elimine algunos elementos de una lista si cumplen ciertos criterios. Prefiero no crear ninguna copia de la lista porque está llena de muchos objetos realmente grandes.

funcionalidad Quiero poner en práctica:

def listCleanup(listOfElements): 
    i = 0 
    for element in listOfElements: 
     if(element.meetsCriteria()): 
      del(listOfElements[i]) 
     i += 1 
    return listOfElements 

myList = range(10000) 
myList = listCleanup(listOfElements) 

No estoy familiarizado con el funcionamiento de bajo nivel de Python. ¿MyList se pasa por valor o por referencia?

¿Cómo puedo hacer esto más rápido?

¿Es posible ampliar de algún modo la clase list e implementar listCleanup() dentro de eso?

myList = range(10000) 
myList.listCleanup() 

de Acción de Gracias

Jonathan

Answer 1

Python pasa todo de la misma manera, pero llamándolo "por valor" o "por referencia" no se borrará todo lo que hasta, ya que la semántica de Python es diferente de la idiomas para los cuales esos términos usualmente se aplican. Si tuviera que describirlo, diría que todo paso fue por valor, y que el valor fue una referencia de objeto. (Esta es la razón por la que no quería decirlo!)

Si desea filtrar un poco de materia de una lista, se construye una nueva lista

foo = range(100000) 
new_foo = [] 
for item in foo: 
    if item % 3 != 0: # Things divisble by 3 don't get through 
     new_foo.append(item) 

o, utilizando la sintaxis de lista por comprensión

new_foo = [item for item in foo if item % 3 != 0] 

Python no copiará los objetos de la lista, sino que tanto foo y new_foo hará referencia a los mismos objetos. (Python nunca copia implícitamente ningún objeto.)

---

Ha sugerido que tenga problemas de rendimiento con respecto a esta operación.El uso repetido de las declaraciones del de la lista anterior dará como resultado un código que no será menos idiomático y más confuso de tratar, pero introducirá un rendimiento cuadrático porque la lista completa debe reorganizarse cada vez.

Para hacer frente a rendimiento:

• Obtener su creación y funcionamiento. No puede entender cómo es su rendimiento a menos que tenga un código funcionando. Esto también le dirá si es la velocidad o el espacio que debe optimizar; usted menciona preocupaciones sobre ambos en su código, pero a menudo la optimización implica obtener uno a costa del otro.

• Perfil. Puede usar the stdlib tools para el rendimiento en el tiempo. Hay varios perfiladores de memoria de terceros que pueden ser de alguna utilidad pero no son tan buenos para trabajar.

• Medir.Time o vuelva a imprimir la memoria cuando realice un cambio para ver si un cambio mejora y, de ser así, cuál es esa mejora.

• Para que su código sea más sensible a la memoria, a menudo querrá un cambio de paradigma en la forma de almacenar sus datos, no microoptimizastions como no construir una segunda lista para filtrar. (Lo mismo es cierto para el tiempo, realmente: cambiar a un algoritmo mejor casi siempre dará la mejor aceleración. Sin embargo, es más difícil generalizar sobre las optimizaciones de velocidad).

  Algunos paradigma común turnos para optimizar el consumo de memoria en Python incluye

  1. utilizando generadores. Los generadores son iterables perezosos: no cargan una lista completa en la memoria a la vez, sino que descubren cuáles son sus próximos artículos sobre la marcha. Para utilizar los generadores, los fragmentos anteriores se vería como

     foo = xrange(100000) # Like generators, xrange is lazy 
     def filter_divisible_by_three(iterable): 
         for item in foo: 
          if item % 3 != 0: 
           yield item 
     
     new_foo = filter_divisible_by_three(foo) 
     

     o, utilizando la sintaxis de la expresión generador,

     new_foo = (item for item in foo if item % 3 != 0) 
     

  2. Usando numpy para secuencias homogéneas, especialmente los que son de tipo numérico-mathy. Esto también puede acelerar el código que realiza muchas operaciones vectoriales.

  3. Almacenamiento de datos en el disco, como en una base de datos.

Answer 2

En Python, las listas son siempre pasados ​​por referencia.

El tamaño de los objetos en la lista no afecta el rendimiento de las listas, ya que la lista solo almacena referencias a los objetos. Sin embargo, la cantidad de elementos en la lista afecta el rendimiento de algunas operaciones, como eliminar un elemento, que es O (n).

Como está escrito, listCleanup es el caso más desfavorable O (n ** 2), ya que tiene la operación O (n) del dentro de un bucle que es potencialmente O (n) en sí.

Si el orden de los elementos no es importante, puede utilizar el tipo integrado set en lugar de una lista. El set tiene O (1) eliminaciones e inserciones. Sin embargo, deberá asegurarse de que sus objetos sean inmutables y manejables.

De lo contrario, será mejor que vuelva a crear la lista. Eso es O (n), y su algoritmo debe ser al menos O (n) ya que necesita examinar cada elemento. Puede filtrar la lista en una línea como la siguiente:

listOfElements[:] = [el for el in listOfElements if el.MeetsCriteria()] 

Answer 3

Para que quede claro:

def listCleanup(listOfElements): 
    i = 0 
    for element in listOfElements: 
     if(element.meetsCriteria()): 
      del(listOfElements[i]) 
     i += 1 
    return listOfElements 

myList = range(10000) 
myList = listCleanup(listOfElements) 

es lo mismo que

def listCleanup(listOfElements): 
    i = 0 
    for element in listOfElements: 
     if(element.meetsCriteria()): 
      del(listOfElements[i]) 
     i += 1 

myList = range(10000) 
listCleanup(listOfElements) 

?

Answer 4

Parece una optimización prematura. Debería intentar comprender mejor cómo funciona Python antes de intentar optimizar.

En este caso particular, no necesita preocuparse por el tamaño del objeto.Copiar una lista es usar la comprensión de la lista o cortar solo realizará una copia de la superficie (copiar las referencias a los objetos, incluso si el término realmente no se aplica bien a python). Pero la cantidad de elementos en la lista puede ser importante porque del es O (n). Puede haber otras soluciones, como reemplazar un artículo con None o un objeto Null convencional, o usar otra estructura de datos como un conjunto o un diccionario donde el costo de eliminar el artículo es mucho menor.

Answer 5

modificar su estructura de datos mientras la itera es como dispararse en el pie ... la iteración falla. que también podría tomar el consejo de otros y simplemente hacer una nueva lista:

myList = [element for element in listOfElements if not element.meetsCriteria()] 

la lista de edad - si no hay otras referencias a él - se desasignado y la memoria recuperada. Mejor aún, ni siquiera hagas una copia de la lista. cambiar lo anterior a una expresión generador para una versión más memoria ambiente:

myList = (element for element in listOfElements if not element.meetsCriteria()) 

todo el acceso a objetos Python es por referencia. se crean objetos y las variables son solo referencias a esos objetos. sin embargo, si alguien quisiera formular la pregunta purista, "¿qué tipo de semántica de llamadas usa Python, llamada por referencia o llamada por valor?" la respuesta tendrá que ser, "Ninguno ... y ambos". la razón es porque las convenciones de llamadas son menos importantes para Python que el tipo de objeto.

si un objeto es mutable, se puede modificar independientemente del alcance en el que se encuentre ... siempre que tenga una referencia de objeto válida, el objeto se puede cambiar. si el objeto es inmutable, ese objeto no se puede cambiar, sin importar dónde se encuentre o qué referencia tenga.

Answer 6

Borrar los elementos de la lista in-situ es posible, pero no avanzando en la lista. Su código simplemente no funciona: a medida que la lista se reduce, puede perder elementos de examen. Tienes que ir hacia atrás, para que la parte que se encoge esté detrás de ti, con un código bastante horrible. Antes de mostrarle eso, hay algunas consideraciones preliminares:

Primero, ¿cómo llegó esa basura a la lista? Es mejor prevenir que curar.

En segundo lugar, ¿cuántos elementos de la lista y qué porcentaje es probable que necesiten borrarse? Cuanto mayor sea el porcentaje, mayor es la probabilidad de que sea mejor crear una nueva lista.

bien, si todavía quiere hacerlo in situ, contemplar este:

def list_cleanup_fail(alist, is_bad): 
    i = 0 
    for element in alist: 
     print "i=%d alist=%r alist[i]=%d element=%d" % (i, alist, alist[i], element) 
     if is_bad(element): 
      del alist[i] 
     i += 1 

def list_cleanup_ok(alist, is_bad): 
    for i in xrange(len(alist) - 1, -1, -1): 
     print "i=%d alist=%r alist[i]=%d" % (i, alist, alist[i]) 
     if is_bad(alist[i]): 
      del alist[i] 

def is_not_mult_of_3(x): 
    return x % 3 != 0 

for func in (list_cleanup_fail, list_cleanup_ok): 
    print 
    print func.__name__ 
    mylist = range(11) 
    func(mylist, is_not_mult_of_3) 
    print "result", mylist 

y aquí está la salida:

list_cleanup_fail 
i=0 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=0 element=0 
i=1 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=1 element=1 
i=2 alist=[0, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=3 element=3 
i=3 alist=[0, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=4 element=4 
i=4 alist=[0, 2, 3, 5, 6, 7, 8, 9, 10] alist[i]=6 element=6 
i=5 alist=[0, 2, 3, 5, 6, 7, 8, 9, 10] alist[i]=7 element=7 
i=6 alist=[0, 2, 3, 5, 6, 8, 9, 10] alist[i]=9 element=9 
i=7 alist=[0, 2, 3, 5, 6, 8, 9, 10] alist[i]=10 element=10 
result [0, 2, 3, 5, 6, 8, 9] 

list_cleanup_ok 
i=10 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=10 
i=9 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] alist[i]=9 
i=8 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] alist[i]=8 
i=7 alist=[0, 1, 2, 3, 4, 5, 6, 7, 9] alist[i]=7 
i=6 alist=[0, 1, 2, 3, 4, 5, 6, 9] alist[i]=6 
i=5 alist=[0, 1, 2, 3, 4, 5, 6, 9] alist[i]=5 
i=4 alist=[0, 1, 2, 3, 4, 6, 9] alist[i]=4 
i=3 alist=[0, 1, 2, 3, 6, 9] alist[i]=3 
i=2 alist=[0, 1, 2, 3, 6, 9] alist[i]=2 
i=1 alist=[0, 1, 3, 6, 9] alist[i]=1 
i=0 alist=[0, 3, 6, 9] alist[i]=0 
result [0, 3, 6, 9] 

Answer 7

Yo no creo que nadie ha mencionado en realidad usando el filtro . Dado que muchas de las respuestas provienen de personas respetadas, estoy seguro de que soy yo el que falta algo. Podría alguien explicar lo que sería malo en esto:

new_list = filter(lambda o: o.meetsCriteria(), myList)