Панды "isin" намного медленнее, чем numpy "in1d" - PullRequest
Новая
       8

Панды "isin" намного медленнее, чем numpy "in1d"

2 голосов
/ 26 марта 2019

Существует огромная разница между пандами "isin" и numpy "in1d" с точки зрения эффективности.После некоторых исследований я заметил, что тип данных и значений, которые передаются в качестве параметра в метод «in», оказывает огромное влияние на время выполнения.Во всяком случае, похоже, что реализация NumPy гораздо меньше страдают от этой проблемы.Что здесь происходит? 

import timeit
import pandas as pd
import numpy as np
df = pd.DataFrame(np.random.randint(0,10,(10**6),dtype='int8'),columns=['A'])
vals = np.array([5,7],dtype='int64')
f = lambda: df['A'].isin(vals)
g = lambda: pd.np.in1d(df['A'],vals)
print 'pandas:', timeit.timeit(stmt='f()',setup='from __main__ import f',number=10)/10
print 'numpy :', timeit.timeit(stmt='g()',setup='from __main__ import g',number=10)/10
>>
**pandas: 0.0541711091995
numpy : 0.000645089149475**

1 Ответ

2 голосов
/ 01 апреля 2019

Numpy и Pandas используют разные алгоритмы для isin.В некоторых случаях версия Numpy быстрее, а для некоторых панд.Для вашего теста numpy выглядит быстрее.

Версия Pandas имеет, однако, лучшее асимптотическое время выполнения, и выиграет для больших наборов данных.

Предположим, что есть n элементы в ряду данных (df в вашем примере) и m элементы в запросе (vals в вашем примере).

Обычно алгоритм Numpy выполняет следующие действия:

  • Используйте np.unique(..), чтобы найти все уникальные элементы в серии.Таким образом, выполняется сортировка, т. Е. O(n*log(n)), может быть N<=n уникальных элементов.
  • Для каждого элемента используйте бинарный поиск, чтобы определить, входит ли элемент в ряд, то есть O(m*log(N)) в целом.

Что приводит к общему времени выполнения O(n*log(n) + m*log(N)).

Существуют некоторые жестко запрограммированные оптимизации для случаев, когда vals только несколько элементов, а для этих случаев - Numpyдействительно сияет.

Панды делают что-то другое:

  • Заполняет хеш-карту (обернутую khash -функцию), чтобы найти все уникальные элементы,который занимает O(n).
  • Поиск в хэш-карте в O(1) для каждого запроса, т.е. всего O(m).

В целом, время выполнения O(n)+O(m), что намного лучше, чем у Numpy.

Однако для меньших входных данных постоянные факторы, а не асимптотическое поведение - это то, что имеет значение, и это просто лучше для Numpy.Есть и другие соображения, такие как потребление памяти (которое выше у панд), которое может сыграть роль.

Но если мы возьмем больший набор запросов, ситуация будет совершенно другой: 

import pandas as pd
import numpy as np
df = pd.DataFrame(np.random.randint(0,10,(10**6),dtype='int8'),columns=['A'])
vals = np.array([5,7],dtype='int64')
vals2 = np.random.randint(0,10,(10**6),dtype='int64')

А теперь: 

%timeit df['A'].isin(vals)    # 17.0 ms 
%timeit df['A'].isin(vals2)   # 16.8 ms

%timeit pd.np.in1d(df['A'],vals)    # 1.36
%timeit pd.np.in1d(df['A'],vals2)   # 82.9 ms

Numpy действительно теряет свои позиции, если есть еще запросы.Также можно видеть, что создание хеш-карты является узким местом для Панд, а не запросов.

В конце концов, не имеет смысла (даже если бы я это сделал!) Оцениватьпроизводительность только для одного размера ввода - это должно быть сделано для диапазона размеров ввода - есть некоторые сюрпризы, которые нужно обнаружить!

Например, интересный факт: если вы возьмете 

df = pd.DataFrame(np.random.randint(0,10,(10**6+1), dtype='int8'),columns=['A'])

, т.е.10^6+1 вместо 10^6, панды прибегнут к алгоритму numpy (который, на мой взгляд, не очень умен) и станут лучше для маленьких входов, но хуже для больших: 

%timeit df['A'].isin(vals)    # 6ms  was 17.0 ms 
%timeit df['A'].isin(vals2)   # 100ms was 16.8 ms
...