Comprobando presencia de subconjuntos dentro de conjunto de forma eficiente

Hoy estaba trabajando con fechas y tenía que encontrar subconjuntos de fechas que estaban presentes o no en otros conjuntos. Numpy nos ofrece varias funciones de ayuda para comprobar este tipo de cosas. Ahora mismo se me vienen a la cabeza numpy.in1d y numpy.setdiff1d. El tema es que necesitaba hacer muchas operaciones de este tipo y he estado buscando la forma de poder optimizar el código un poco y resulta que, dependiendo de la operación, numpy puede resultar hasta 10 veces más lento (según mis pruebas de hoy) que usar puro CPython3. Veamos un ejemplo sencillo:

1) Imaginemos que mis datos son arrays de numpy y quiero conocer los datos de un array a que no están presentes en b:

import numpy as np
a = np.arange(1000000)
b = np.arange(10, 1000010)
%timeit np.setdiff1d(a, b)

Usando IPython y en mi máquina el anterior código me da el siguiente resultado:

10 loops, best of 3: 148 ms per loop

2) Si ahora hago lo mismo usando conjuntos (sets) obtendría el siguiente resultado:

a = set(np.arange(1000000))
b = set(np.arange(10, 1000010))
%timeit a.difference(b)

De la misma forma, usando IPython y en mi máquina el anterior código me da el siguiente resultado:

10 loops, best of 3: 30.2 ms per loop

Para este caso concreto numpy es ¡¡¡hasta 5 veces más lento!!!

Esto es una micro-optimización que me ha servido a mi en un caso concreto y si aplica espero que os resulte útil pero ya sabéis que la optimización prematura es la fuente de todos los males 🙂

Saludos

Actualización:

Como bien comentan tanto Jaime como Chema más abajo, la comparación es tramposa ya que, normalmente, lo que mido no es lo que se hace en un programa completo, se debería de medir el proceso completo. La pretensión de este post era baja y solo mostrar la diferencia de implementaciones entre lo que hace numpy y lo que hace CPython. Os recomiendo que leáis los comentarios para aprender más.

Gracias, Jaime y Chema.

Kiko Correoso

Licenciado y PhD en Ciencias Físicas, especializado en temas de física, meteorología, climatología, energías renovables, estadística, aprendizaje automático, análisis y visualización de datos. Apasionado de Python y su comunidad. Fundador de pybonacci y editor del sitio en el que se divulga Python, Ciencia y el conocimiento libre en español.

More Posts

Follow Me:
TwitterLinkedIn

6 thoughts on “Comprobando presencia de subconjuntos dentro de conjunto de forma eficiente

  1. Buah ! Me viene de perlas esto ! Nunca hubiera pensado que fuese menos eficiente hacerlo con numpy. Siempre trabajar con fechas se hace tedioso. Siempre heche a faltar algún post con este tema. Igual me animo 🙂

  2. Todas las funciones de Numpy para conjuntos estan basadas en ordenar los arrays para encontrar duplicados. La implementacion es Python puro, y es muy educativo echarle un vistazo: https://github.com/numpy/numpy/blob/master/numpy/lib/arraysetops.py

    Por contra las operaciones de conjuntos de Python usan hashing.

    Ordenar tiene una complejidad algorítmica O(n logn), mientras que buscar n elementos en una hash table solo tiene complejidad O(n). Para conjuntos suficientemente grandes, el algoritmo más eficiente de Python siempre tendrá ventaja sobre Numpy.

    De todas formas, la comparación que has hecho es un poco tramposa: salvo que no necesites Numpy para nada más, convertir un array en un set no es gratuito, y si tus datos originales estan en un array, el código que deberías cronometrar es `set(a).difference(b)`, sin convertir ni a ni b en sets antes. En mi ordenador esto es ~50% más lento que usar np.setdiff1d directamente.

    1. Gracias por el enlace, le echaré un ojo a la implementación.

      La verdad es que el post es algo bastante informal y con pocas pretensiones y la comparación, como comentas, puede resultar tramposa (somos así :-P). Está claro que si hay que usar distintos tipos de datos y transformar entre tipos y demás la cosa no está clara. Solo era para resaltar que para alguna operación muy determinada quizá (y solo quizá) numpy no sea la mejor opción siempre. Con tu explicación sobre las implementaciones de numpy y de los sets de Python queda mucho más completo. Gracias.

  3. Además de lo que comenta Jaime sobre el coste de crear sets, ambos códigos no están haciendo lo mismo. Habría que indicarle a `np.setdiff1d` que son elementos únicos (`assume_unique=True`) para partir en las mismas condiciones.

    1. Esta noche no creo que pueda pero mañana intento rehacer el post para que quede un poco más completo y riguroso con tu aportación y la de Jaime. La verdad es que lo escribí rápido y mal con niños gritando a mi alrededor (no es una excusa, es una observación :-))

    2. Después de hacer la prueba con assume_unique=True en np.setdiff1d me sale lo siguiente:

      Considerando datos únicos: 121 ms
      Sin considerar datos únicos: 150 ms

      Es cierto que esta comparación sería más fiel.

      Gracias por el apunte.

Leave a Reply

Your email address will not be published. Required fields are marked *