python - not - Pandas pd.Series.isin rendimiento con conjunto frente a matriz

pandas query

Question

En Python en general, la pertenencia a una colección de hashable se prueba mejor a través del set . Sabemos esto porque el uso de hashing nos da O (1) complejidad de búsqueda en comparación con O (n) para la list o np.ndarray .

En Pandas, a menudo tengo que verificar si soy miembro de colecciones muy grandes. Supuse que se aplicaría lo mismo, es decir, verificar que cada elemento de una serie sea miembro de un set es más eficiente que usar list o np.ndarray . Sin embargo, este no parece ser el caso:

import numpy as np
import pandas as pd

np.random.seed(0)

x_set = {i for i in range(100000)}
x_arr = np.array(list(x_set))
x_list = list(x_set)

arr = np.random.randint(0, 20000, 10000)
ser = pd.Series(arr)
lst = arr.tolist()

%timeit ser.isin(x_set)                   # 8.9 ms
%timeit ser.isin(x_arr)                   # 2.17 ms
%timeit ser.isin(x_list)                  # 7.79 ms
%timeit np.in1d(arr, x_arr)               # 5.02 ms
%timeit [i in x_set for i in lst]         # 1.1 ms
%timeit [i in x_set for i in ser.values]  # 4.61 ms

Versiones utilizadas para la prueba:

np.__version__  # ''1.14.3''
pd.__version__  # ''0.23.0''
sys.version     # ''3.6.5''

El código fuente de pd.Series.isin , creo, utiliza numpy.in1d , lo que presumiblemente significa una gran sobrecarga para la conversión a np.ndarray .

Negando el costo de construir los insumos, las implicaciones para Pandas:

• Si sabe que sus elementos de x_list o x_arr son únicos, no se moleste en convertir a x_set . Esto será costoso (tanto para las pruebas de conversión como de membresía) para usar con Pandas.
• El uso de las comprensiones de listas es la única forma de beneficiarse de la búsqueda de conjuntos O (1).

Mis preguntas son:

1. ¿Mi análisis anterior es correcto? Esto parece un resultado obvio, pero no documentado, de cómo se ha implementado pd.Series.isin .
2. ¿Hay una solución alternativa, sin usar una lista de comprensión o pd.Series.apply , que utiliza la búsqueda de O (1) set? ¿O es esta una elección de diseño inevitable y / o el corolario de tener NumPy como la columna vertebral de Pandas?

Actualización : en una configuración anterior (versiones de Pandas / NumPy) veo x_set supera a x_arr con pd.Series.isin . Por lo tanto, una pregunta adicional: ¿ha cambiado algo fundamentalmente de antiguo a nuevo para causar que el rendimiento empeore?

%timeit ser.isin(x_set)                   # 10.5 ms
%timeit ser.isin(x_arr)                   # 15.2 ms
%timeit ser.isin(x_list)                  # 9.61 ms
%timeit np.in1d(arr, x_arr)               # 4.15 ms
%timeit [i in x_set for i in lst]         # 1.15 ms
%timeit [i in x_set for i in ser.values]  # 2.8 ms

pd.__version__  # ''0.19.2''
np.__version__  # ''1.11.3''
sys.version     # ''3.6.0''

Answer 1

Puede que esto no sea obvio, pero pd.Series.isin usa O(1) -look up.

Después de un análisis, que prueba la afirmación anterior, utilizaremos sus conocimientos para crear un prototipo de Cython que puede superar fácilmente la solución más rápida y rápida.

Supongamos que el "conjunto" tiene n elementos y la "serie" tiene m elementos. El tiempo de ejecución es entonces:

 T(n,m)=T_preprocess(n)+m*T_lookup(n)

Para la versión de python puro, eso significa:

• T_preprocess(n)=0 - no se necesita preprocesamiento
• T_lookup(n)=O(1) - comportamiento bien conocido del conjunto de python
• resulta en T(n,m)=O(m)

¿Qué sucede para pd.Series.isin(x_arr) ? Obviamente, si omitimos el preprocesamiento y la búsqueda en tiempo lineal obtendremos O(n*m) , lo cual no es aceptable.

Es fácil de ver con la ayuda de un depurador o un generador de perfiles (usé valgrind-callgrind + kcachegrind), lo que está sucediendo: el caballo de trabajo es la función __pyx_pw_6pandas_5_libs_9hashtable_23ismember_int64 . Su definición se puede encontrar here :

• En un paso de preprocesamiento, un hash-map (pandas usa khash de klib ) se crea a partir de n elementos de x_arr , es decir, en tiempo de ejecución O(n) .
• m búsquedas se realizan en O(1) cada una o O(m) en total en el mapa hash construido.
• resulta en T(n,m)=O(m)+O(n)

Debemos recordar que los elementos de numpy-array son raw-C-integer y no los objetos Python en el conjunto original, por lo que no podemos usar el conjunto tal como está.

Una alternativa a la conversión del conjunto de objetos Python en un conjunto de entradas en C, sería convertir las entradas en C individuales en el objeto Python y así poder utilizar el conjunto original. Eso es lo que sucede en [i in x_set for i in ser.values] -variante:

• Sin preprocesamiento.
• m las búsquedas se realizan en O(1) cada vez o O(m) en total, pero la búsqueda es más lenta debido a la creación necesaria de un objeto Python.
• resulta en T(n,m)=O(m)

Claramente, podrías acelerar esta versión un poco usando Cython.

Pero suficiente teoría, echemos un vistazo a los tiempos de ejecución para diferentes n s con m s fijo:

Podemos ver: el tiempo lineal de preprocesamiento domina la versión numpy para grandes n s. La versión con conversión de numpy a pure-python ( numpy->python ) tiene el mismo comportamiento constante que la versión de pure-python pero es más lenta, debido a la conversión necesaria; todo esto de acuerdo con nuestro análisis.

Esto no se puede ver bien en el diagrama: si n < m la versión numpy se vuelve más rápida, en este caso la búsqueda más rápida de khash -lib desempeña el papel más importante y no la parte de preprocesamiento.

Mis conclusiones de este análisis:

• n < m : pd.Series.isin debe tomarse porque el preprocesamiento O(n) no es tan costoso.

• n > m : (probablemente la versión citonizada de) [i in x_set for i in ser.values] debe tomarse y, por lo tanto, debe evitarse O(n) .

• claramente hay una zona gris donde n y m son aproximadamente iguales y es difícil decir cuál es la mejor solución sin probar.

• Si lo tiene bajo su control: lo mejor sería construir el set directamente como un conjunto de enteros C ( khash ( ya envuelto en pandas ) o tal vez incluso algunas implementaciones de C ++), eliminando así la necesidad de preprocesamiento. No sé si hay algo en los pandas que puedas reutilizar, pero probablemente no sea un gran problema escribir la función en Cython.

El problema es que la última sugerencia no funciona de manera inmediata, ya que ni los pandas ni los números tienen una noción de un conjunto (al menos hasta mi conocimiento limitado) en sus interfaces. Sin embargo, tener interfaces de conjuntos C crudos sería lo mejor de ambos mundos:

• no se necesita preprocesamiento porque los valores ya se pasan como un conjunto
• no se necesita conversión porque el conjunto pasado consta de valores C en bruto

He codificado un envoltorio Cython rápido y sucio para khash (inspirado en el envoltorio en pandas), que se puede instalar a través de pip install https://github.com/realead/cykhash/zipball/master y luego usarlo con Cython para una versión isin más rápida:

%%cython
import numpy as np
cimport numpy as np

from cykhash.khashsets cimport Int64Set

def isin_khash(np.ndarray[np.int64_t, ndim=1] a, Int64Set b):
    cdef np.ndarray[np.uint8_t,ndim=1, cast=True] res=np.empty(a.shape[0],dtype=np.bool)
    cdef int i
    for i in range(a.size):
        res[i]=b.contains(a[i])
    return res

Como una posibilidad adicional, el mapa unordered_map c ++ se puede envolver (ver listado C), lo que tiene la desventaja de necesitar bibliotecas de c ++ y (como veremos) es un poco más lento.

Comparando los enfoques (ver listado D para la creación de tiempos):

khash es sobre el factor 20 más rápido que el numpy->python , sobre el factor 6 más rápido que el python puro (pero de todos modos no es lo que queremos) e incluso sobre el factor 3 más rápido que la versión de cpp.

Listados

1) perfilado con valgrind:

#isin.py
import numpy as np
import pandas as pd

np.random.seed(0)

x_set = {i for i in range(2*10**6)}
x_arr = np.array(list(x_set))


arr = np.random.randint(0, 20000, 10000)
ser = pd.Series(arr)


for _ in range(10):
   ser.isin(x_arr)

y ahora:

>>> valgrind --tool=callgrind python isin.py
>>> kcachegrind

lleva al siguiente gráfico de llamadas:

B: código ipython para producir los tiempos de ejecución:

import numpy as np
import pandas as pd
%matplotlib inline
import matplotlib.pyplot as plt

np.random.seed(0)

x_set = {i for i in range(10**2)}
x_arr = np.array(list(x_set))
x_list = list(x_set)

arr = np.random.randint(0, 20000, 10000)
ser = pd.Series(arr)
lst = arr.tolist()

n=10**3
result=[]
while n<3*10**6:
    x_set = {i for i in range(n)}
    x_arr = np.array(list(x_set))
    x_list = list(x_set)

    t1=%timeit -o  ser.isin(x_arr) 
    t2=%timeit -o  [i in x_set for i in lst]
    t3=%timeit -o  [i in x_set for i in ser.values]

    result.append([n, t1.average, t2.average, t3.average])
    n*=2

#plotting result:
for_plot=np.array(result)
plt.plot(for_plot[:,0], for_plot[:,1], label=''numpy'')
plt.plot(for_plot[:,0], for_plot[:,2], label=''python'')
plt.plot(for_plot[:,0], for_plot[:,3], label=''numpy->python'')
plt.xlabel(''n'')
plt.ylabel(''running time'')
plt.legend()
plt.show()

C: envoltorio cpp:

%%cython --cplus -c=-std=c++11 -a

from libcpp.unordered_set cimport unordered_set

cdef class HashSet:
    cdef unordered_set[long long int] s
    cpdef add(self, long long int z):
        self.s.insert(z)
    cpdef bint contains(self, long long int z):
        return self.s.count(z)>0

import numpy as np
cimport numpy as np

cimport cython
@cython.boundscheck(False)
@cython.wraparound(False)

def isin_cpp(np.ndarray[np.int64_t, ndim=1] a, HashSet b):
    cdef np.ndarray[np.uint8_t,ndim=1, cast=True] res=np.empty(a.shape[0],dtype=np.bool)
    cdef int i
    for i in range(a.size):
        res[i]=b.contains(a[i])
    return res

D: trazando resultados con diferentes envoltorios de conjuntos:

import numpy as np
import pandas as pd
%matplotlib inline
import matplotlib.pyplot as plt
from cykhash import Int64Set

np.random.seed(0)

x_set = {i for i in range(10**2)}
x_arr = np.array(list(x_set))
x_list = list(x_set)


arr = np.random.randint(0, 20000, 10000)
ser = pd.Series(arr)
lst = arr.tolist()

n=10**3
result=[]
while n<3*10**6:
    x_set = {i for i in range(n)}
    x_arr = np.array(list(x_set))
    cpp_set=HashSet()
    khash_set=Int64Set()

    for i in x_set:
        cpp_set.add(i)
        khash_set.add(i)


    assert((ser.isin(x_arr).values==isin_cpp(ser.values, cpp_set)).all())
    assert((ser.isin(x_arr).values==isin_khash(ser.values, khash_set)).all())


    t1=%timeit -o  isin_khash(ser.values, khash_set)
    t2=%timeit -o  isin_cpp(ser.values, cpp_set) 
    t3=%timeit -o  [i in x_set for i in lst]
    t4=%timeit -o  [i in x_set for i in ser.values]

    result.append([n, t1.average, t2.average, t3.average, t4.average])
    n*=2

#ploting result:
for_plot=np.array(result)
plt.plot(for_plot[:,0], for_plot[:,1], label=''khash'')
plt.plot(for_plot[:,0], for_plot[:,2], label=''cpp'')
plt.plot(for_plot[:,0], for_plot[:,3], label=''pure python'')
plt.plot(for_plot[:,0], for_plot[:,4], label=''numpy->python'')
plt.xlabel(''n'')
plt.ylabel(''running time'')
ymin, ymax = plt.ylim()
plt.ylim(0,ymax)
plt.legend()
plt.show()