Блог

Существует огромная разница между pandas «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**
  

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

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

Давайте предположим, что есть 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 действительно великолепен.

Pandas делает что-то другое:

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

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

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

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

 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 действительно теряет позиции, пока поступает больше запросов. Также можно видеть, что построение хэш-карты является узким местом для Pandas, а не запросов.

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

Например. забавный факт: если бы вы взяли

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

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

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