Это может быть неочевидно, но pd.Series.isin использует O(1) -просмотреть вверх.
После анализа, подтверждающего вышеприведенное утверждение, мы используем его идеи для создания прототипа Cython, который может легко превзойти самое быстрое готовое решение.
Предположим, что в «наборе» есть n элементов, а в «серии» - m элементов.Время работы составляет:
T(n,m)=T_preprocess(n)+m*T_lookup(n)
Для версии с чистым питоном это означает:
T_preprocess(n)=0 - предварительная обработка не требуется T_lookup(n)=O(1)- хорошо известное поведение набора питонов - приводит к
T(n,m)=O(m)
Что происходит для pd.Series.isin(x_arr)?Очевидно, что если мы пропустим предварительную обработку и поиск по линейному времени, мы получим O(n*m), что недопустимо.
Это легко увидеть с помощью отладчика или профилировщика (я использовал valgrind-callgrind + kcachegrind), что происходит: рабочая лошадь - это функция __pyx_pw_6pandas_5_libs_9hashtable_23ismember_int64.Его определение можно найти здесь :
- На этапе предварительной обработки из * 1038 создается хэш-карта (панды используют khash из klib )* элементы из
x_arr, то есть во время выполнения O(n). m поиски происходят в O(1) каждый или O(m) в общей сложности в построенной хэш-карте. - приводит к
T(n,m)=O(m)+O(n)
Мы должны помнить - элементы массива numpy являются целыми числами raw-C, а не объектами Python в исходном наборе - поэтому мы не можем использовать набор какэто.
Альтернативой преобразованию набора Python-объектов в набор C-ints было бы преобразование отдельных C-ints в Python-объект и, таким образом, возможность использования исходного набора.Это то, что происходит в [i in x_set for i in ser.values] -варианте:
- Нет предварительной обработки.
- m поиск происходит за
O(1) раз каждый или O(m) всего, но внешний вид-произведение медленнее из-за необходимости создания Python-объекта. - приводит к
T(n,m)=O(m)
Очевидно, что вы могли бы немного ускорить эту версию, используя Cython.
Но достаточно теории, давайте взглянем на время работы для разных n с фиксированными m с:
Мы можем видеть: линейное время предварительной обработки доминирует над numpy-версией для больших n с.Версия с преобразованием из numpy в pure-python (numpy->python) имеет то же постоянное поведение, что и версия pure-python, но медленнее из-за необходимого преобразования - все это в соответствии с нашим анализом.
Это не очень хорошо видно на диаграмме: если n < m версия с клочками становится быстрее - в этом случае более быстрый поиск khash -lib играет самую важную роль, а не часть предварительной обработки.
Мои выводы из этого анализа:
n < m: pd.Series.isin должно быть взято, потому что O(n) -обработка не такая дорогая.
n > m: (вероятно, цитонизированная версия) [i in x_set for i in ser.values] следует взять и, таким образом, O(n) следует избегать.
явно есть серая зона, где nи m приблизительно равны, и трудно определить, какое решение лучше без тестирования.
Если он у вас под контролем: лучше всего построить set напрямую как набор целых чисел C (khash ( уже обернут вpandas ) или, может быть, даже несколько реализаций c ++), что исключает необходимость предварительной обработки.Я не знаю, есть ли в пандах что-то, что вы могли бы использовать повторно, но написать функцию на Cython, вероятно, не составляет большого труда.
Проблема в том, чтопоследнее предложение не работает «из коробки», так как ни панды, ни numpy не имеют понятия набора (по крайней мере, насколько мне известно) в их интерфейсах.Но наличие raw-C-set-интерфейсов было бы лучшим из обоих миров:
- предварительная обработка не требуется, поскольку значения уже переданы как набор
- преобразование не требуется, поскольку переданный набор состоитraw-C-значения
Я написал быстрый и грязный Cython-обертка для khash (вдохновленный оберткой в пандах), который можно установить через pip install https://github.com/realead/cykhash/zipball/master, а затем использовать с Cython для более быстрого isinверсия:
%%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
В качестве дополнительной возможности можно обернуть unordered_map в c ++ (см. листинг C), что имеет недостаток в необходимости использования библиотек c ++ и (как мы увидим) немного медленнее.
Сравнение подходов (см. Листинг D для создания таймингов):
хэш примерно в 20 раз быстрее, чем numpy->pythonпримерно в 6 раз быстрее, чем чистый python (но в любом случае чистый python - это не то, что нам нужно) и даже в 3 раза быстрее, чем версия cpp.
Listings
1) профилирование с помощью 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)
и теперь:
>>> valgrind --tool=callgrind python isin.py
>>> kcachegrind
приводит к следующему графу вызовов:
B: код ipython для создания времени выполнения:
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: cpp-wrapper:
%%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: plotРезультаты с разными наборами-обёртками:
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()