El día 19 de octubre de 2010 23:48, tny <a.por...@gmail.com> escribió: > El mar, 19-10-2010 a las 16:03 +0200, lasizoillo escribió: >> 2010/10/19 Arnau Sanchez <pyar...@gmail.com>: >> > On Tue, 19 Oct 2010 13:50:37 +0200 tny wrote: >> > >> >> uno_de_cada_en_orden_original = [a[i] for i in range(len(a)) if a[i] not >> >> in a[:i]] >> > >> > Uf, eso tiene pinta de O(n^2) en tiempo cuando unique puede (debería) ser >> > O(n). >> >> Un unique sobre una colección ordenada debería ser O(n) porque basta >> con comparar con el anterior. Si la lista no esta ordenada habría que >> encontrar si ya hemos leido ese dato antes o no. Si puede hacer esa >> búsqueda con O(1), seguiría siendo O(n), pero lo más probable es que >> acabara siendo O(n log n). En su caso tiene pinta de O(n^2) u O(n^2 / >> 2) si nos ponemos finos, cosa que es mejorable, pero tiene la ventaja >> de no necesitar otra estructura adicional para hacer ese loopback. Es >> más lento, pero requiere menos memoria. >> >> Resumiendo, me parece ideal para los casos en los que se quiera quitar >> duplicados de una lista manteniendo el orden (desordenado) original de >> esta y los requisitos de espacio/memoria sean necesarios. Para el >> resto de los casos hay soluciones mejores ;-) >> >> Un saludo: >> >> Javi >> _______________________________________________ >> Python-es mailing list >> Python-es@python.org >> http://mail.python.org/mailman/listinfo/python-es >> FAQ: http://python-es-faq.wikidot.com/ > > ¿Cual de los siguientes modos sería más rápido?
La respuesta ideal es ejecutarlos y medir el tiempo. Una forma cómoda de hacerlo es usar la consola ipython y comando timeit. Te puede pasar que una implementación más rápida en una versión de python sea más lenta en otra. El primero sería seguramente más lento porque la recursividad penaliza bastante. Aparte de que podrías llegar al limite de llamadas recursivas facilmente: http://docs.python.org/library/sys.html?highlight=setrecursionlimit#sys.getrecursionlimit > ¿Cual sería su complejidad? Cuando solo cambies la implementación, sin cambiar el algoritmo que se implementa, no cambia el orden de complejidad. Así que del segundo deberías ya saber su complejidad. Otro consejo practico de alguien sin estudios: Hasta coger práctica calculando el orden de ejecución, puedes medirlo empíricamente. Implementas, das distintos valores de n midiendo tiempos de ejecución y pintas sobre una gráfica. > ¿Beneficiaría en algo al rendimiento del primer algoritmo forkear cada > mitad, y cuando estén calculadas unirlas? Los procesos son útiles a veces. Ventajas: * El código se puede ejecutar en varios procesadores Desventajas: * Añaden complejidad de muchas formas: * Algorítmica. Separas el proceso en dos partes (manteniendo complejidad algorítmica en cada una de ellas en el mejor de los casos) y luego añades complejidad al mezclar los resultados. * De implementación. Sincronización de memoria compartida, serializar datos a través de pipes, ... * La complejidad añadida afecta al rendimiento. Un código que se ejecute en 8 cores nunca va a llegar a ir 8 veces más rápido que ejecutándose en uno solo. Si el cuello de botella no es la cpu, puedes obtener un código más lento. > > def unicos_manteniendo_orden(lista): > size = len(lista) > if size == 1: > return lista > primera_mitad = unicos_manteniendo_orden(lista[:size/2]) > segunda_mitad = unicos_manteniendo_orden(lista[size/2:]) > return primera_mitad + [x for x in segunda_mitad if x not in > primera_mitad] > > def unicos_manteniendo_orden_2(lista): > resultado = [] > for elemento in lista: > if elemento in resultado: > continue > resultado.append(elemento) > return resultado > > Si te interesa mucho el rendimiento podrías hacer cosas como quitarle el punto del append en la segunda implementación: http://wiki.python.org/moin/PythonSpeed/PerformanceTips#Avoidingdots... Personalmente no suelo hacerlas. Lo optimo en la implementación del intérprete de hoy puede ser peor en la implementación del intérprete o JIT de python de mañana. Pero lo que es seguro es que tu código va a perder en legibilidad y mantenibilidad. Y python sin legibilidad ya no es python ;-) Espero que este post de agüelo cebolleta te resulte de utilidad ;-) Un saludo: Javi _______________________________________________ Python-es mailing list Python-es@python.org http://mail.python.org/mailman/listinfo/python-es FAQ: http://python-es-faq.wikidot.com/
