python - Pandas 查找时间比较

Question

在 Pandas (0.17.1) 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

问题...

1. 很清楚为什么在排序索引上的查找要快得多，二分查找获得 O(log(n)) 的性能与 O(n) 的全数组扫描。但是，为什么在排序的非索引 df2 列 SLOWER 上的查找比在未排序的非索引列 df1 上的查找？

2. 最慢的运行时间比最快的运行时间长 x 倍。这可能意味着正在缓存中间结果。当然，结果没有被缓存。是因为创建的索引是惰性的，并且 实际上 直到需要时才重新索引？这可以解释为什么它只在第一次调用 .loc[].

3. 为什么默认不排序索引？排序的固定成本会不会太大？

Answer 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

也出现在 pure 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' calls a Cython function 它循环遍历底层 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 更快地完成 == '本'。 查找时间更短。

这个内存访问问题也解释了为什么在 %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'] 是 dtype float64 的 NumPy 数组。与对象不同 数组，它们的值在内存中连续打包在一起。排序 df1 df2 = df1.sort_values('letter') 导致 df2['value'] 中的值是 重新排序，但由于值被复制到一个新的 NumPy 数组中，这些值 在内存中按顺序定位。所以访问 df2['value'] 中的值可以 与 df1['value'] 中的操作一样快。