Supprimer des éléments d'une liste en cours d'itération sans utiliser de mémoire supplémentaire en Python

Question

Mon problème est simple: j'ai une longue liste d'éléments que je veux parcourir et vérifier chaque élément par rapport à une condition. En fonction du résultat de la condition, je voudrais supprimer l'élément actuel de la liste, et continuer à itérer dessus comme d'habitude.

J'ai lu quelques autres discussions sur ce sujet. Deux solutions de couture à proposer. Soit faire un dictionnaire hors de la liste (ce qui implique de faire une copie de toutes les données qui remplissent déjà toute la RAM dans mon cas). Soit marcher la liste à l'envers (ce qui rompt le concept de l'alogrithme que je veux implémenter).

Y a-t-il un moyen meilleur ou plus élégant de le faire?

def walk_list(list_of_g): 
    g_index = 0 
    while g_index < len(list_of_g): 
     g_current = list_of_g[g_index] 
     if subtle_condition(g_current): 
      list_of_g.pop(g_index) 
     else: 
      g_index = g_index + 1 

Answer 1

Voici une réponse alternative si vous devez absolument supprimer les éléments de la liste originale, et vous ne pas avoir assez de mémoire pour faire une copie - déplacer les éléments dans la liste vous-même:

def walk_list(list_of_g): 
    to_idx = 0 
    for g_current in list_of_g: 
     if not subtle_condition(g_current): 
      list_of_g[to_idx] = g_current 
      to_idx += 1 
    del list_of_g[to_idx:] 

Ceci déplacera chaque élément (en fait un pointeur vers chaque élément) exactement une fois, donc sera O (N). L'instruction del à la fin de la fonction supprimera tous les éléments indésirables à la fin de la liste, et je pense que Python est assez intelligent pour redimensionner la liste sans allouer de la mémoire pour une nouvelle copie de la liste.

Answer 2

Que pensez-vous de cela?

[x for x in list_of_g if not subtle_condition(x)] 

son retour la nouvelle liste à l'exception de subtle_condition

Answer 3

Par souci de simplicité, utilisez une compréhension de la liste:

def walk_list(list_of_g): 
    return [g for g in list_of_g if not subtle_condition(g)] 

Bien sûr, cela ne modifie pas la liste initiale, de sorte que l'appel le code devrait être différent.

Si vous voulez vraiment muter la liste (rarement le meilleur choix), la marche arrière est plus simple:

def walk_list(list_of_g): 
    for i in xrange(len(list_of_g), -1, -1): 
     if subtle_condition(list_of_g[i]): 
      del list_of_g[i] 

Answer 4

li = [ x for x in li if condition(x)] 

et aussi

li = filter(condition,li) 

Thanks to Dave Kirby

Answer 5

Le construit -la fonction de filtre est faite juste pour faire ceci:

list_of_g = filter(lambda x: not subtle_condition(x), list_of_g) 

Answer 6

La suppression d'éléments d'une liste coûte cher, car python doit copier tous les éléments au-dessus de g_index à un endroit. Si le nombre d'éléments que vous voulez supprimer est proportionnel à la longueur de la liste N, alors votre algorithme va être O (N ** 2). Si la liste est assez longue pour remplir votre RAM, vous devrez attendre très longtemps pour la compléter.

Il est plus efficace de créer une copie filtrée de la liste, soit en utilisant une compréhension de la liste comme Marcelo a montré, ou utiliser le filtre ou les fonctions itertools.ifilter:

g_list = filter(not_subtle_condition, g_list) 

Si vous n'avez pas besoin d'utiliser la nouvelle liste et ne veulent itérer une fois, il est préférable d'utiliser ifilter car cela ne crée pas une seconde liste:

for g_current in itertools.ifilter(not_subtle_condtion, g_list): 
    # do stuff with g_current 

Answer 7

sonne comme un cas vraiment bonne utilisation de la fonction de filtre.

def should_be_removed(element): 
    return element > 5 

a = range(10) 
a = filter(should_be_removed, a) 

Ceci, cependant, ne supprimera pas la liste pendant l'itération (ni je le recommande).Si la mémoire de l'espace (ou d'autres raisons de performance) vous avez vraiment besoin, vous pouvez effectuer les opérations suivantes:

i = 0 
while i < len(a): 
    if should_be_removed(a[i]): 
     a.remove(a[i]) 
    else: 
     i+=1 
    print a 

Answer 8

Si vous effectuez une itération inverse, vous pouvez supprimer des éléments à la volée sans affecter les prochains indices que vous allez visiter:

numbers = range(20) 

# remove all numbers that are multiples of 3 
l = len(numbers) 
for i, n in enumerate(reversed(numbers)): 
    if n % 3 == 0: 
     del numbers[l - i - 1] 

print numbers 

Le enumerate(reversed(numbers)) est juste un choix stylistique. Vous pouvez utiliser une gamme si c'est plus lisible pour vous:

l = len(numbers) 
for i in range(l-1, -1, -1): 
    n = numbers[i] 
    if n % 3 == 0: 
     del numbers[i] 

Si vous devez parcourir la liste dans l'ordre, vous pouvez inverser en place avec .reverse() avant et après l'itération inversée. Cela ne dupliquera pas votre liste non plus.