Python eliminar de la lista mientras se itera

Tengo una lista de cadenas y quiero mantener solo las cadenas más únicas. Aquí es cómo he implementado esto (tal vez hay un problema con el bucle),

def filter_descriptions(descriptions): MAX_SIMILAR_ALLOWED = 0.6 #40% unique and 60% similar i = 0 while i < len(descriptions): print("Processing {}/{}...".format(i + 1, len(descriptions))) desc_to_evaluate = descriptions[i] j = i + 1 while j  MAX_SIMILAR_ALLOWED: del descriptions[j] j += 1 i += 1 return descriptions 

Tenga en cuenta que la lista puede tener alrededor de 110 K elementos, por lo que estoy acortando la lista en cada iteración.

¿Alguien puede identificar qué es lo que está mal con esta implementación actual?

Edición 1:

Los resultados actuales son “demasiado similares”. La función filter_descriptions devolvió 16 artículos (de una lista de ~ 110K artículos). Cuando intenté lo siguiente,

 SequenceMatcher(None, descriptions[0], descriptions[1]).ratio() 

La relación fue de 0.99, y con SequenceMatcher(None, descriptions[1], descriptions[2]).ratio() fue de alrededor de 0.98. Pero con SequenceMatcher(None, descriptions[0], descriptions[15]).ratio() fue de alrededor de 0.65 (lo que es mejor)

Espero que esto ayude.

Si invierte su lógica, puede evitar tener que modificar la lista en su lugar y reducir el número de comparaciones necesarias. Es decir, comience con una lista de salida / única vacía y repita sobre sus descripciones para ver si puede agregar cada una. Entonces, para la primera descripción, puede agregarla inmediatamente ya que no puede ser similar a nada en una lista vacía. La segunda descripción solo necesita compararse con la primera en oposición a todas las demás descripciones. Las iteraciones posteriores pueden provocar un cortocircuito tan pronto como encuentren una descripción previa con la que son similares (y descartar la descripción del candidato). es decir.

 import operator def unique(items, compare=operator.eq): # compare is a function that returns True if its two arguments are deemed similar to # each other and False otherwise. unique_items = [] for item in items: if not any(compare(item, uniq) for uniq in unique_items): # any will stop as soon as compare(item, uniq) returns True # you could also use `if all(not compare(item, uniq) ...` if you prefer unique_items.append(item) return unique_items 

Ejemplos:

 assert unique([2,3,4,5,1,2,3,3,2,1]) == [2, 3, 4, 5, 1] # note that order is preserved assert unique([1, 2, 0, 3, 4, 5], compare=(lambda x, y: abs(x - y) <= 1))) == [1, 3, 5] # using a custom comparison function we can exclude items that are too similar to previous # items. Here 2 and 0 are excluded because they are too close to 1 which was accepted # as unique first. Change the order of 3 and 4, and then 5 would also be excluded. 

Con su código su función de comparación se vería así:

 MAX_SIMILAR_ALLOWED = 0.6 #40% unique and 60% similar def description_cmp(candidate_desc, unique_desc): # use unique_desc as first arg as this keeps the argument order the same as with your filter # function where the first description is the one that is retained if the two descriptions # are deemed to be too similar similarity_ratio = SequenceMatcher(None, unique_desc, candidate_desc).ratio() return similarity_ratio > MAX_SIMILAR_ALLOWED def filter_descriptions(descriptions): # This would be the new definition of your filter_descriptions function return unique(descriptions, compare=descriptions_cmp) 

El número de comparaciones debe ser exactamente el mismo. Es decir, en su implementación, el primer elemento se compara con todos los demás, y el segundo elemento solo se compara con los elementos que se consideraron no similares al primer elemento y así sucesivamente. En esta implementación, el primer elemento no se compara con nada inicialmente, pero todos los demás elementos deben compararse con él para que se pueda agregar a la lista única. Solo los artículos considerados no similares al primer elemento se compararán con el segundo elemento único, y así sucesivamente.

La implementación unique hará menos copias, ya que solo tiene que copiar la lista única cuando la matriz de respaldo se quede sin espacio. Considerando que, con las partes del enunciado de la lista debe copiarse cada vez que se utiliza (para mover todos los elementos posteriores a su nueva posición correcta). Sin embargo, esto probablemente tendrá un impacto insignificante en el rendimiento, ya que el cuello de botella es probablemente el cálculo de la relación en el emparejador de secuencias.

El problema con su lógica es que cada vez que borra un elemento de la matriz, el índice se reorganiza y se salta una cadena en medio. P.ej:

Supongamos que esta es la matriz: Descripción: [“A”, “A”, “A”, “B”, “C”]

itinerario 1:

 i=0 -------------0 description[i]="A" j=i+1 -------------1 description[j]="A" similarity_ratio>0.6 del description[j] 

Ahora la matriz se vuelve a indexar como: Descripción: [“A”, “A”, “B”, “C”]. El siguiente paso es:

  j=j+1 ------------1+1= 2 

Descripción [2] = “B”

Has omitido la Descripción [1] = “A”


Para solucionar esto: Reemplazar

 j+=1 

Con

 j=i+1 

si se elimina De lo contrario, haga la iteración j = j + 1 normal.

El valor de j no debe cambiar cuando se elimina un elemento de la lista (ya que un elemento de lista diferente estará presente en ese punto en la siguiente iteración). Hacer j=i+1 reinicia la iteración cada vez que se elimina un elemento (que no es lo que se desea). El código actualizado ahora solo incrementa j en la condición else.

 def filter_descriptions(descriptions): MAX_SIMILAR_ALLOWED = 0.6 #40% unique and 60% similar i = 0 while i < len(descriptions): print("Processing {}/{}...".format(i + 1, len(descriptions))) desc_to_evaluate = descriptions[i] j = i + 1 while j < len(descriptions): similarity_ratio = SequenceMatcher(None, desc_to_evaluate, descriptions[j]).ratio() if similarity_ratio > MAX_SIMILAR_ALLOWED: del descriptions[j] else: j += 1 i += 1 return descriptions