Skip to main content
2 de 3
se añadieron 233 caracteres en el cuerpo
FJSevilla
  • 62.1k
  • 7
  • 43
  • 68

Como comentaba en la pregunta y como muestra @abulafia en su respuesta, generalmente la forma más eficiente de eliminar duplicados de un iterable es usar conjuntos/diccionarios por dos razones:

  • No repeticiones de items (conjuntos) / claves (diccionarios).

  • Son muy eficientes a la hora de buscar y comprobar si un determinado elemento/clave un elemento está contenido en ellos (tablas hash).

La única posible pega es que se crea un contendor temporal (el conjunto/diccionario), aunque dado que son significativamente más eficientes en cuanto a tiempo de ejecución y que la memoria extra usada no es tan importante (en el fondo solo almacenas un conjunto de referencias), no suele ser realmente un problema en la mayoría de casos a no ser que debamos cuidar mucho el uso de RAM por alguna razón y no nos importe tanto el tiempo de CPU.

Siendo totalmente cierto lo anterior, se puede hacer lo mismo sin crear absolutamente ninguna estructura más que la lista resultado usando un simple for y el operador de pertenencia in. Por culpa de éste último, dado que las búsquedas en listas son menos eficientes y que en caso de no existir el item se tiene que iterar sobre toda la lista, esta aproximación es más lenta (list.append también influye), sobretodo para listas grandes con pocos duplicados dónde el tiempo de ejecución y uso de cpu puede incrementarse mucho con respecto al uso de conjuntos. Eso si, es la opción que menos memoria va a usar (quitando las fórmulas inplace) y mantiene el orden original:

cities = [
          ['madrid', 'salamanca', 'oviedo', 'sevilla'],
          ['lugo', 'coruña', 'madrid', 'murcia']
         ]

result = []
for cities in cities_set:
    for city in cities:
        if not city in result:
            result.append(city)
 
print(result)
['madrid', 'salamanca', 'oviedo', 'sevilla', 'lugo', 'coruña', 'murcia']

Dicho esto, aunque no es una respuesta para la pregunta dado que no te dejan usar módulos de la biblioteca estándar, voy a completar un poco la respuesta de abulafia por si a otros usuarios les es de ayuda:

La forma más eficiente de usar un conjunto para eliminar los duplicados si estamos tratando con listas relativamente grandes es usar itertools.chain.from_iterable para generar un iterador que permite aplanar la lista y pasarla a set():

>>> import itertools
>>> result = list(set(itertools.chain.from_iterable(cities_set)))
>>> ['lugo', 'salamanca', 'murcia', 'sevilla', 'madrid', 'oviedo', 'coruña']

Si se quisiera mantener el orden original al eliminar los duplicados podemos recurrir a un diccionario en Python >= 3.7 (3.6 realmente también, pero el orden en los diccionarios se considera un efecto colateral de la implementación en esta versión):

>>> import itertools
>>> result = list(dict(itertools.chain.from_iterable(cities_set).keys))
>>> ['madrid', 'salamanca', 'oviedo', 'sevilla', 'lugo', 'coruña', 'murcia']

en Python >= 3.7 debemos usar collections.OrderedDict en su lugar, ya que los diccionarios no mantienen el orden de inserción.

Algunas test de tiempo de ejecución para listas relativamente grandes (2000 sublistas):

%%timeit
result = []
for city in itertools.chain.from_iterable(cities_set):
    if not city in result:
        result.append(city)
573 µs ± 9.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%%timeit
result = list({ city  for cities in cities_set for city in cities })
301 µs ± 9.58 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%%timeit
result = list(dict.fromkeys(itertools.chain.from_iterable(cities_set)).keys())
268 µs ± 12.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%%timeit
result = list(set(itertools.chain.from_iterable(cities_set)))
181 µs ± 801 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Puede sorprender que la diferencia entre usar for anidados con in y list.append y las otras opciones no sea tan significativa. Esto se debe a que la lista final contiene pocos items (hay muchas repeticiones), cuantas menos repeticiones existan mayor será el tiempo de ejecución dado que al usar in se buscará en una lista mayor (más iteraciones) pudiendo llegar a ser contraproducente en estas situaciones.

Puede observarse como para listas grandes itertools.chain es considerablemente más eficiente. Para listas muy pequeñas como es el caso de la pregunta, itertools.chain no es tan útil dado que la ventaja que da al iterar se pierde por la sobrecarga de llamar a la función. Para la lista de la pregunta, los tiempos de ejecución en el mismo orden que antes son:

# for andiados + in + list.append 
1.11 µs ± 9.95 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)  

# list + "conjunto por compresión"  
869 ns ± 12.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 

# dict + itertools.chain (mantiene orden)   
1.15 µs ± 12.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
 
#  set + itertools.chain
877 ns ± 13.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)    
FJSevilla
  • 62.1k
  • 7
  • 43
  • 68