Сравнение времени поиска Pandas

После экспериментов с таймингами различных типов поиска на Pandas DataFrame у меня осталось несколько вопросов.

Вот настройка...

import pandas as pd
import numpy as np
import itertools

letters = [chr(x) for x in range(ord('a'), ord('z'))]
letter_combinations = [''.join(x) for x in itertools.combinations(letters, 3)]

df1 = pd.DataFrame({
        'value': np.random.normal(size=(1000000)), 
        'letter': np.random.choice(letter_combinations, 1000000)
    })
df2 = df1.sort_values('letter')
df3 = df1.set_index('letter')
df4 = df3.sort_index()

Итак, df1 выглядит примерно так:

print(df1.head(5))


>>>
  letter     value
0    bdh  0.253778
1    cem -1.915726
2    mru -0.434007
3    lnw -1.286693
4    fjv  0.245523

Вот код для проверки различий в производительности поиска...

print('~~~~~~~~~~~~~~~~~NON-INDEXED LOOKUPS / UNSORTED DATASET~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
%timeit df1[df1.letter == 'ben']
%timeit df1[df1.letter == 'amy']
%timeit df1[df1.letter == 'abe']

print('~~~~~~~~~~~~~~~~~NON-INDEXED LOOKUPS / SORTED DATASET~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
%timeit df2[df2.letter == 'ben']
%timeit df2[df2.letter == 'amy']
%timeit df2[df2.letter == 'abe']

print('~~~~~~~~~~~~~~~~~~~~~INDEXED LOOKUPS~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
%timeit df3.loc['ben']
%timeit df3.loc['amy']
%timeit df3.loc['abe']

print('~~~~~~~~~~~~~~~~~~~~~SORTED INDEXED LOOKUPS~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
%timeit df4.loc['ben']
%timeit df4.loc['amy']
%timeit df4.loc['abe']

И результаты...

~~~~~~~~~~~~~~~~~NON-INDEXED LOOKUPS / UNSORTED DATASET~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
10 loops, best of 3: 59.7 ms per loop
10 loops, best of 3: 59.7 ms per loop
10 loops, best of 3: 59.7 ms per loop
~~~~~~~~~~~~~~~~~NON-INDEXED LOOKUPS / SORTED DATASET~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
10 loops, best of 3: 192 ms per loop
10 loops, best of 3: 192 ms per loop
10 loops, best of 3: 193 ms per loop
~~~~~~~~~~~~~~~~~~~~~INDEXED LOOKUPS~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The slowest run took 4.66 times longer than the fastest. This could mean that an intermediate result is being cached 
10 loops, best of 3: 40.9 ms per loop
10 loops, best of 3: 41 ms per loop
10 loops, best of 3: 40.9 ms per loop
~~~~~~~~~~~~~~~~~~~~~SORTED INDEXED LOOKUPS~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The slowest run took 1621.00 times longer than the fastest. This could mean that an intermediate result is being cached 
1 loops, best of 3: 259 µs per loop
1000 loops, best of 3: 242 µs per loop
1000 loops, best of 3: 243 µs per loop

Вопросы...

  • Довольно ясно, почему поиск по отсортированному индексу намного быстрее, бинарный поиск для получения O (log (n)) производительности против O (n) для полного сканирования массива. Но почему поиск в отсортированном неиндексированном столбце df2 SLOWER, чем поиск в несортированном неиндексированном столбце df1?

  • Что происходит с The slowest run took x times longer than the fastest. This could mean that an intermediate result is being cached. Конечно, результаты не кэшируются. Это потому, что созданный индекс ленив и на самом деле не переиндексирован до тех пор, пока это не понадобится? Это объясняет, почему это происходит только при первом вызове .loc[].

  • Почему индекс не отсортирован по умолчанию? Фиксированная стоимость сортировки может быть слишком большой?

Ответы

Ответ 1

Несоответствие этих результатов% timeit

In [273]: %timeit df1[df1['letter'] == 'ben']
10 loops, best of 3: 36.1 ms per loop

In [274]: %timeit df2[df2['letter'] == 'ben']
10 loops, best of 3: 108 ms per loop

также отображается в чистых сравнениях чисел NumPy:

In [275]: %timeit df1['letter'].values == 'ben'
10 loops, best of 3: 24.1 ms per loop

In [276]: %timeit df2['letter'].values == 'ben'
10 loops, best of 3: 96.5 ms per loop

Под капотом Pandas 'df1['letter'] == 'ben' вызывает Cython функция который проходит через значения базового массива NumPy, df1['letter'].values. Это, по сути, делает то же самое, что и df1['letter'].values == 'ben', но с различной обработкой NaN.

Кроме того, обратите внимание, что просто доступ к элементам в df1['letter'] в последовательный порядок может быть выполнен быстрее, чем при использовании df2['letter']:

In [11]: %timeit [item for item in df1['letter']]
10 loops, best of 3: 49.4 ms per loop

In [12]: %timeit [item for item in df2['letter']]
10 loops, best of 3: 124 ms per loop

Разница во времени в каждом из этих трех наборов тестов %timeit примерно то же самое. Я думаю, это потому, что все они имеют одну и ту же причину.

Поскольку столбец letter содержит строки, массивы NumPy df1['letter'].values и df2['letter'].values имеют dtype object и, следовательно, они сохраняют указатели на расположение памяти произвольных объектов Python (в этом случае строки).

Рассмотрим расположение памяти строк, хранящихся в DataFrames, df1 и df2. В CPython id возвращает местоположение памяти объекта:

memloc = pd.DataFrame({'df1': list(map(id, df1['letter'])),
                       'df2': list(map(id, df2['letter'])), })

               df1              df2
0  140226328244040  140226299303840
1  140226328243088  140226308389048
2  140226328243872  140226317328936
3  140226328243760  140226230086600
4  140226328243368  140226285885624

Строки в df1 (после первого десятка или около того) имеют тенденцию появляться последовательно в памяти, в то время как сортировка приводит к тому, что строки в df2 (по порядку) разбросанных по памяти:

In [272]: diffs = memloc.diff(); diffs.head(30)
Out[272]: 
         df1         df2
0        NaN         NaN
1     -952.0   9085208.0
2      784.0   8939888.0
3     -112.0 -87242336.0
4     -392.0  55799024.0
5     -392.0   5436736.0
6      952.0  22687184.0
7       56.0 -26436984.0
8     -448.0  24264592.0
9      -56.0  -4092072.0
10    -168.0 -10421232.0
11 -363584.0   5512088.0
12      56.0 -17433416.0
13      56.0  40042552.0
14      56.0 -18859440.0
15      56.0 -76535224.0
16      56.0  94092360.0
17      56.0  -4189368.0
18      56.0     73840.0
19      56.0  -5807616.0
20      56.0  -9211680.0
21      56.0  20571736.0
22      56.0 -27142288.0
23      56.0   5615112.0
24      56.0  -5616568.0
25      56.0   5743152.0
26      56.0 -73057432.0
27      56.0  -4988200.0
28      56.0  85630584.0
29      56.0  -4706136.0

Большинство строк в df1 разделены 56 байтами:

In [14]: 
In [16]: diffs['df1'].value_counts()
Out[16]: 
 56.0           986109
 120.0           13671
-524168.0          215
-56.0                1
-12664712.0          1
 41136.0             1
-231731080.0         1
Name: df1, dtype: int64

In [20]: len(diffs['df1'].value_counts())
Out[20]: 7

Напротив, строки в df2 разбросаны по всему месту:

In [17]: diffs['df2'].value_counts().head()
Out[17]: 
-56.0     46
 56.0     44
 168.0    39
-112.0    37
-392.0    35
Name: df2, dtype: int64

In [19]: len(diffs['df2'].value_counts())
Out[19]: 837764

Когда эти объекты (строки) расположены последовательно в памяти, их значения могут быть получены быстрее. Вот почему сопоставления равенства, выполняемые df1['letter'].values == 'ben' можно выполнить быстрее, чем в df2['letter'].values == 'ben'. Время поиска меньше.

Эта проблема с доступом к памяти также объясняет, почему нет различий в %timeit для столбца value.

In [5]: %timeit df1[df1['value'] == 0]
1000 loops, best of 3: 1.8 ms per loop

In [6]: %timeit df2[df2['value'] == 0]
1000 loops, best of 3: 1.78 ms per loop

df1['value'] и df2['value'] - массивы NumPy dtype float64. В отличие от объекта массивы, их значения упаковываются вместе в памяти. Сортировка df1 с df2 = df1.sort_values('letter') вызывает значения в df2['value'] переупорядочено, но поскольку значения копируются в новый массив NumPy, значения расположены последовательно в памяти. Поэтому доступ к значениям в df2['value'] может выполняться так же быстро, как в df1['value'].

Ответ 2

(1) pandas в настоящее время не знает о сортировке столбца.
Если вы хотите воспользоваться отсортированными данными, вы можете использовать df2.letter.searchsorted См. Ответ @unutbu для объяснения того, что на самом деле вызывает разницу во времени.

(2) Хэш-таблица, которая находится под индексом, создается лениво, затем кэшируется.