Производительность Pandas pd.Series.isin с набором против массива

В Python, как правило, членство в хешируемой коллекции лучше всего проверяется через set. Мы это знаем, потому что использование хэширования дает нам O (1) сложность поиска по сравнению с O (n) для list или np.ndarray.

В Пандах мне часто приходится проверять членство в очень больших коллекциях. Я предположил, что это применимо, т.е. Проверка каждого элемента серии для членства в set более эффективна, чем использование list или np.ndarray. Однако, похоже, это не так:

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

Версии, используемые для тестирования:

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

Исходный код для pd.Series.isin, я полагаю, использует numpy.in1d, который предположительно означает большие накладные расходы для set на преобразование np.ndarray.

Отрицая затраты на создание входных данных, последствия для Pandas:

  • Если вы знаете, что ваши элементы x_list или x_arr уникальны, не беспокойтесь о преобразовании в x_set. Это будет дорогостоящим (как тестирование конверсии, так и членство) для использования с Pandas.
  • Использование списков - единственный способ извлечь выгоду из поиска O (1).

Мои вопросы:

  1. Правильно ли мой анализ? Это похоже на очевидный, но недокументированный результат реализации pd.Series.isin.
  2. Есть ли обходной путь, не используя понимание списка или pd.Series.apply, который использует O (1) набор поиска? Или это неизбежный выбор дизайна и/или следствие наличия NumPy в качестве основы Pandas?

Обновление: при более старой настройке (версии Pandas/NumPy) я вижу x_set outperform x_arr с pd.Series.isin. Поэтому дополнительный вопрос: имеет что - то принципиально изменилось от старого к новому, чтобы вызвать работу с set ухудшаться?

%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'

Ответы

Ответ 1

Это может быть не очевидно, но pd.Series.isin использует O(1) -look вверх.

После анализа, который доказывает вышеприведенное утверждение, мы будем использовать его идеи для создания прототипа Cython, который может легко побить самое быстрое решение из коробки.

Предположим, что "множество" имеет n элементов, а "серия" имеет m элементов. Время работы:

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

Для версии pure-python это означает:

  • T_preprocess(n)=0 - не требуется предварительная обработка
  • T_lookup(n)=O(1) - хорошо известное поведение набора python
  • приводит к T(n,m)=O(m)

Что происходит с pd.Series.isin(x_arr)? Очевидно, что если мы пропустим предварительную обработку и поиск в линейном времени, мы получим O(n*m), что неприемлемо.

Легко видеть с помощью отладчика или профилировщика (я использовал valgrind-callgrind + kcachegrind), что происходит: рабочей лошадкой является функция __pyx_pw_6pandas_5_libs_9hashtable_23ismember_int64. Его определение можно найти здесь:

  • На этапе предварительной обработки хэш-карта (pandas использует khash из klib) создается из n элементов из 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 я in ser.values] -variant:

  • Нет предварительной обработки.
  • м просмотры происходят в O(1) раз каждый или O(m), но поиск медленнее из-за необходимости создания объекта Python.
  • приводит к T(n,m)=O(m)

Понятно, что вы можете немного ускорить эту версию, используя Cython.

Но достаточно теории, позвольте взглянуть на время работы для разных n с фиксированными m s:

enter image description here

Мы можем видеть: линейное время предварительной обработки доминирует над версией numpy- для больших n s. Версия с преобразованием из numpy в pure-python (numpy->python) имеет такое же постоянное поведение, как и версия pure-python, но медленнее, из-за необходимого преобразования - это все в соответствии с нашим анализом.

Это не может быть хорошо видно на схеме: если n < m NumPy версия становится быстрее - в этом случае быстрее просмотровых из khash -lib играет самую важную роль, а не первичная обработка частей.

Мои выводы из этого анализа:

  • n < m: pd.Series.isin следует взять, потому что O(n) -preprocessing не так дорого.

  • n > m: (возможно, cythonized version of) [i in x_set for я in ser.values], и, следовательно, O(n) избегается.

  • очевидно, есть серая зона, где n и m приблизительно равны, и трудно сказать, какое решение лучше всего без тестирования.

  • Если у вас есть это под вашим контролем: лучше всего построить set непосредственно как набор C-целого (khash (уже завернутый в панды) или, возможно, даже некоторые c++ -выполнения), тем самым устраняя необходимость предварительной обработки, Я не знаю, есть ли что-то в пандах, которые вы могли бы повторно использовать, но, вероятно, не очень важно написать функцию в Cython.

Проблема в том, что последнее предложение не работает из коробки, так как ни у pandas, ни numpy нет понятия набора (по крайней мере, для моих ограниченных знаний) в их интерфейсах. Но наличие raw-C-set-интерфейсов было бы лучшим из обоих миров:

  • не требуется предварительная обработка, поскольку значения уже переданы как набор
  • нет необходимости в преобразовании, потому что прошедший набор состоит из значений raw-C

Я закодировал быструю и грязную Cython-обертку для хаша (вдохновленную оболочкой в пандах), которую можно установить через 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

В качестве дополнительной возможности c++ unordered_map можно обернуть (см. Список C), что имеет недостаток в необходимости использования c++ -lib и, как мы увидим, немного медленнее.

Сравнение подходов (см. Список D для создания таймингов):

enter image description here

khash примерно на 20 раз быстрее, чем numpy->python, о факторе 6 быстрее, чем чистый python (но чистый-питон - это не то, что мы хотим) и даже около фактора 3 быстрее, чем версия cpp.

Объявления

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

приводит к следующему графику вызовов:

enter image description here

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: отображение результатов с помощью различных наборов-оберток:

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()