El mejor método para cambiar una lista mientras se itera sobre ella

Question

Tengo varias instancias en un script de python (v2.6) donde necesito modificar una lista en contexto. Necesito mostrar los valores de la lista en respuesta a la entrada interactiva del usuario y me gustaría saber cuál es el método más limpio para hacerlo. Actualmente tengo las soluciones muy sucias de a) establecer elementos en la lista que quiero eliminar en False y eliminarlos con un filtro o lista de comprensión ob) generar una lista completamente nueva al pasar por el ciclo, que parece ser innecesariamente agregar variables al espacio de nombre y tomar memoria.

Un ejemplo de este problema es el siguiente:

for i, folder in enumerate(to_run_folders): 
    if get_size(folder) < byte_threshold: 
     ans = raw_input(('The folder {0}/ is less than {1}MB.' + \ 
        ' Would you like to exclude it from' + \ 
        ' compression? ').format(folder, megabyte_threshold)) 
     if 'y' in ans.strip().lower(): 
      to_run_folders.pop(i) 

me gustaría buscar en cada carpeta en la lista. Si la carpeta actual tiene menos de un tamaño determinado, quiero preguntarle al usuario si desea excluirla. Si lo hacen, abre la carpeta de la lista.

El problema con esta rutina es que si repito la lista, aparece un comportamiento inesperado y una terminación anticipada. Si itero sobre una copia cortando, pop no tira del valor correcto porque los índices se desplazan y el problema se complica a medida que aparecen más elementos. También necesito un ajuste dinámico de la lista de este tipo en otras áreas de mi script. ¿Hay algún método limpio para este tipo de funcionalidad?

Answer 1

Puede recorrer la lista hacia atrás o utilizar un objeto de vista.

Consulte https://stackoverflow.com/a/181062/711085 para saber cómo recorrer una lista al revés. Básicamente use reversed(yourList) (lo que sucede crea un objeto de vista que visita hacia atrás).

Si necesita indexación, que podría hacer reversed(enumerate(yourList)), pero eso sería efectivamente crear una lista temporal en la memoria porque enumerate tendría que correr antes de reversed podría poner en Usted tendrá que o bien hacer la manipulación del índice, o para hacer esto.:

for i in xrange(len(yourList)-1, -1, -1): 
    item = yourList[i] 
    ... 

aún más limpio: reversed es consciente de range, por lo que se puede hacer esto en python3, o en python2 si utiliza xrange lugar:

for i in reversed(range(len(yourList))): 
    item = yourList[i] 
    ... 

(la prueba: se puede hacer next(reversed(range(10**10))), pero esto va a bloquear el equipo si se utiliza python2)

Answer 2

Puede recorrer más hacia atrás

al revés:

x = range(10) 
l = len(x)-1 # max index 

for i, v in enumerate(reversed(x)): 
    if v % 2: 
     x.pop(l-i) # l-1 is the forward index 

Answer 3

Actualmente tengo el mismo soluciones sucias de a) establecer elementos en la lista que quiero eliminar en False y eliminarlos con un filtro o lista de comprensión ob) generar una lista completamente nueva mientras se pasa por el ciclo, que parece ser innecesariamente agregar variables al espacio de nombres y tomando memoria.

En realidad, no es esa solución sucia. ¿Cuánto tiempo suele durar la lista? Incluso la creación de la nueva lista no debería consumir demasiada memoria ya que la lista solo contiene referencias.

También puede recorrer el bucle while y enumerarlo usted mismo, realizando del lst[n] si el usuario decide (posiblemente contando por separado las posiciones en el original).

Answer 4

Bien, he medido la solución. Las soluciones invertidas son casi lo mismo. El ciclo while hacia adelante es aproximadamente 4 veces más lento. PERO! solución del Patrik sucia es aproximadamente 80 veces más rápido para la lista de 100.000 enteros aleatorios [bug en Patrik2 corregido]:

import timeit 
import random 

def solution_ninjagecko1(lst): 
    for i in xrange(len(lst)-1, -1, -1): 
     if lst[i] % 2 != 0: # simulation of the choice 
      del lst[i] 
    return lst 

def solution_jdi(lst): 
    L = len(lst) - 1 
    for i, v in enumerate(reversed(lst)): 
     if v % 2 != 0: 
      lst.pop(L-i) # L-1 is the forward index 
    return lst 

def solution_Patrik(lst): 
    for i, v in enumerate(lst): 
     if v % 2 != 0:   # simulation of the choice 
      lst[i] = None 
    return [v for v in lst if v is not None] 

def solution_Patrik2(lst): 
    ##buggy lst = [v for v in lst if v % 2 != 0] 
    ##buggy return [v for v in lst if v is not None] 
    # ... corrected to 
    return [v for v in lst if v % 2 != 0] 

def solution_pepr(lst): 
    i = 0      # indexing the processed item 
    n = 0      # enumerating the original position 
    while i < len(lst): 
     if lst[i] % 2 != 0: # simulation of the choice 
      del lst[i]   # i unchanged if item deleted 
     else: 
      i += 1    # i moved to the next 
     n += 1 
    return lst 

def solution_pepr_reversed(lst): 
    i = len(lst) - 1   # indexing the processed item backwards 
    while i > 0: 
     if lst[i] % 2 != 0: # simulation of the choice 
      del lst[i]   # i unchanged if item deleted 
     i -= 1     # i moved to the previous 
    return lst 

def solution_steveha(lst): 
    def should_keep(x): 
     return x % 2 == 0 
    return filter(should_keep, lst) 

orig_lst = range(30) 
print 'range() generated list of the length', len(orig_lst) 
print orig_lst[:20] + ['...'] # to have some fun :) 

lst = orig_lst[:] # copy of the list 
print solution_ninjagecko1(lst) 

lst = orig_lst[:] # copy of the list 
print solution_jdi(lst) 

lst = orig_lst[:] # copy of the list 
print solution_Patrik(lst) 

lst = orig_lst[:] # copy of the list 
print solution_pepr(lst) 

orig_lst = [random.randint(1, 1000000) for n in xrange(100000)] 
print '\nrandom list of the length', len(orig_lst) 
print orig_lst[:20] + ['...'] # to have some fun :) 

lst = orig_lst[:] # copy of the list 
t = timeit.timeit('solution_ninjagecko1(lst)', 
        'from __main__ import solution_ninjagecko1, lst', 
        number=1) 
print 'solution_ninjagecko1: ', t 

lst = orig_lst[:] # copy of the list 
t = timeit.timeit('solution_jdi(lst)', 
        'from __main__ import solution_jdi, lst', 
        number=1) 
print 'solution_jdi: ', t 

lst = orig_lst[:] # copy of the list 
t = timeit.timeit('solution_Patrik(lst)', 
        'from __main__ import solution_Patrik, lst', 
        number=1) 
print 'solution_Patrik: ', t 

lst = orig_lst[:] # copy of the list 
t = timeit.timeit('solution_Patrik2(lst)', 
        'from __main__ import solution_Patrik2, lst', 
        number=1) 
print 'solution_Patrik2: ', t 

lst = orig_lst[:] # copy of the list 
t = timeit.timeit('solution_pepr_reversed(lst)', 
        'from __main__ import solution_pepr_reversed, lst', 
        number=1) 
print 'solution_pepr_reversed: ', t 

lst = orig_lst[:] # copy of the list 
t = timeit.timeit('solution_pepr(lst)', 
        'from __main__ import solution_pepr, lst', 
        number=1) 
print 'solution_pepr: ', t 

lst = orig_lst[:] # copy of the list 
t = timeit.timeit('solution_steveha(lst)', 
        'from __main__ import solution_steveha, lst', 
        number=1) 
print 'solution_steveha: ', t 

Imprime en mi consola:

c:\tmp\_Python\Patrick\so10305762>python a.py 
range() generated list of the length 30 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, '...'] 
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28] 
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28] 
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28] 
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28] 

random list of the length 100000 
[915411, 954538, 794388, 847204, 846603, 454132, 866165, 640004, 930488, 609138, 
333405, 986073, 318301, 728151, 996047, 117633, 455353, 581737, 55350, 485030, 
'...'] 
solution_ninjagecko1: 2.41921752625 
solution_jdi: 2.45477176569 
solution_Patrik: 0.0468565138865 
solution_Patrik2: 0.024270403082 
solution_pepr_reversed: 2.43338888043 
solution_pepr: 9.11879694207 

Por lo tanto, Lo intenté con una lista más larga. Usar solo el doble de tiempo hace una gran diferencia (en mi computadora vieja). La solución dirty de Patrik se comporta muy bien. Es aproximadamente 200 veces más rápido que las soluciones invertidas:

random list of the length 200000 
[384592, 170167, 598270, 832363, 123557, 81804, 319315, 445945, 178732, 726600, 
516835, 392267, 552608, 40807, 349215, 208111, 880032, 520614, 384119, 350090, 
'...'] 
solution_ninjagecko1: 17.362140719 
solution_jdi: 17.86837545 
solution_Patrik: 0.0957998851809 
solution_Patrik2: 0.0500024444448 
solution_pepr_reversed: 17.5078452708 
solution_pepr: 52.175648581 

[Alta después de los comentarios de ninjagecko]

La solución Patrik2 corregido es aproximadamente dos veces más rápido que la solución de Patrick 2 etapas.

Para simular la eliminación no tan frecuente de los elementos, la prueba como if v % 2 != 0: se cambió a if v % 100 == 0:. Entonces aproximadamente el 1% de los artículos se deben eliminar. Es obvio que lleva menos tiempo. Por 500.000 enteros aleatorios en la lista, los resultados son los siguientes:

random list of the length 500000 
[403512, 138135, 552313, 427971, 42358, 500926, 686944, 304889, 916659, 112636, 
791585, 461948, 82622, 522768, 485408, 774048, 447505, 830220, 791421, 580706, 
'...'] 
solution_ninjagecko1: 6.79284210703 
solution_jdi: 6.84066913532 
solution_Patrik: 0.241242951269 
solution_Patrik2: 0.162481823807 
solution_pepr_reversed: 6.92106007886 
solution_pepr: 7.12900522273 

solución de Patrick es stil alrededor de 30 veces más rápido.

[Agregado 2012/04/25]

Otra solución que funciona en el lugar, que los bucles hacia adelante, y que es tan rápido como solución de Patrick. No mueve toda la cola cuando se elimina el elemento. En cambio, mueve los elementos deseados a su posición final y luego corta la cola no utilizada de la lista.

def solution_pepr2(lst): 
    i = 0 
    for v in lst: 
     lst[i] = v    # moving the element (sometimes unneccessary) 
     if v % 100 != 0:  # simulation of the choice 
      i += 1    # here will be the next one 
    lst[i:] = []    # cutting the tail of the length of the skipped 
    return lst 

# The following one only adds the enumerate to simulate the situation when 
# it is needed -- i.e. slightly slower but with the same complexity.   
def solution_pepr2enum(lst): 
    i = 0 
    for n, v in enumerate(lst): 
     lst[i] = v    # moving the element (sometimes unneccessary) 
     if v % 100 != 0:  # simulation of the choice 
      i += 1    # here will be the next one 
    lst[i:] = []    # cutting the tail of the length of the skipped 
    return lst 

En comparación con las soluciones anteriores para v % 100 != 0:

random list of the length 500000 
[533094, 600755, 58260, 295962, 347612, 851487, 523927, 665648, 537403, 238660, 
781030, 940052, 878919, 565870, 717745, 408465, 410781, 560173, 51010, 730322, 
'...'] 
solution_ninjagecko1: 1.38956896051 
solution_jdi: 1.42314502685 
solution_Patrik: 0.135545530079 
solution_Patrik2: 0.0926935780151 
solution_pepr_reversed: 1.43573239178 
solution_steveha: 0.122824246805 
solution_pepr2: 0.0938177241656 
solution_pepr2enum: 0.11096263294 

Answer 5

La mejor manera de manejar esto, la forma más "Pythonic", es, de hecho, para recorrer la lista y crea una nueva lista que contiene solo las carpetas que desea. Así es como yo lo haría:

def want_folder(fname): 
    if get_size(folder) >= byte_threshold: 
     return True 
    ans = raw_input(('The folder {0}/ is less than {1}MB.' + \ 
       ' Would you like to exclude it from' + \ 
       ' compression? ').format(folder, megabyte_threshold)) 
    return 'y' not in ans.strip().lower() 

to_run_folders = [fname for fname in to_run_folders if want_folder(fname)] 

Si la lista es realmente grande, entonces tal vez usted tiene que preocuparse por el rendimiento de esta solución y utilizar trucos sucios. Pero si su lista es tan grande, podría ser una locura tener una respuesta humana sí/no a todos los archivos que puedan aparecer.

¿El rendimiento es un problema real o simplemente un tipo de preocupación persistente? Porque estoy seguro de que el código anterior es lo suficientemente rápido para el uso práctico, y es más fácil de entender y modificar que un código complicado.

EDIT: @jdi sugirió, en los comentarios, usando itertools.ifilter() o filter()

Probé, y esto en realidad debería ser más rápido que lo que he mostrado antes:

to_run_folders = filter(want_folder, to_run_folders) 

simplemente copié @ evaluación comparativa de PEPR código, y probado la solución usando filter() como se muestra aquí. Fue el segundo más rápido en general, con solo Patrik2 siendo más rápido. Patrik2 fue dos veces más rápido, pero de nuevo, cualquier conjunto de datos lo suficientemente pequeño como para que sea práctico tener respuestas humanas con preguntas de sí/no es probablemente lo suficientemente pequeño como para que un factor de dos no importe demasiado.

EDIT: solo por diversión, seguí adelante y escribí una versión que es una lista pura de comprensión. Tiene una sola expresión para evaluar, ninguna llamada de función Python.

to_run_folders = [fname for fname in to_run_folders 
     if get_size(fname) >= mb_threshold or 
       'y' not in raw_input(('The folder {0}/ is less than {1}MB.' + 
       ' Would you like to exclude it from compression? ' 
       ).format(fname, mb_threshold)).strip().lower() 

] 

¡Yuck! Prefiero hacer una función.