performance - Pandas 中的合并为何如此之快？即使我没有对索引进行排序？

Question

我在 Pandas 中合并了两个数据集，并希望加快这个过程，所以我在用于合并的列上对它们进行了排序。 (以前这些列根本没有排序。)排序没有造成明显的速度差异；两者都花了大约八秒钟。

如果我根据页码手动合并两叠纸，我会首先按页码对每叠纸进行排序。否则我将不得不在堆栈之间来回翻转很多。

我写了一个测试来比较这两个过程。它以随机顺序生成两个帧，每个帧有一百万行。然后它生成两个已经在第一列上排序的。然后合并前两个，最后合并后两个。

数据生成过程非常缓慢，我没有时间尝试更多行——但即使没有排序，合并仍然发生在零可感知时间内。

import pandas as pd
import numpy as np

def shuffle(df, n=1, axis=0):
  """ https://stackoverflow.com/questions/15772009/shuffling-permutating-a-dataframe-in-pandas """
  df = df.copy()
  for _ in range(n):
    df.apply(np.random.shuffle, axis=axis)
  return df

# Create some shuffled data
df1 = pd.DataFrame({'A':range(1000000), 'B':range(1000000)})
df2 = pd.DataFrame({'A':range(1000000), 'B':range(1000000)})
df1 = shuffle(df1)
df2 = shuffle(df2)

# Sort that data on column A
df1s = df1.sort_values(by='A')
df2s = df2.sort_values(by='A')

m  = df1. merge(df2,  on='A') # Merge the unsorted data
ms = df1s.merge(df2s, on='A') # Merge the sorted data

编辑:我用 50 倍宽和 1/5 高的数据编写了一个测试，现在排序似乎有帮助？

import pandas as pd
import numpy as np

def shuffle(df, n=1, axis=0):
  """ https://stackoverflow.com/questions/15772009/shuffling-permutating-a-dataframe-in-pandas """
  df = df.copy()
  for _ in range(n):
    df.apply(np.random.shuffle, axis=axis)
  return df

# Create some shuffled data
nrows = 200000
reorderedIntegers  = shuffle( pd.DataFrame({ 'A':range(nrows) }) )
reorderedIntegers2 = shuffle( pd.DataFrame({ 'A':range(nrows) }) )

# Widen it
extraColumns = pd.DataFrame( np.random.rand( nrows, 100 ) )
df  = pd.concat( [reorderedIntegers,  extraColumns], axis=1 )
df2 = pd.concat( [reorderedIntegers2, extraColumns], axis=1 )

# Create sorted copies
dfs  = df .sort_values(by='A')
dfs2 = df2.sort_values(by='A')

# Compare merge speeds
m  = df. merge(df2,  on='A') # Merge the unsorted data
ms = dfs.merge(df2s, on='A') # Merge the sorted data -- substantially faster now

附言我想用 timeit.timeit() 来测量两个例程的速度，但是我一直收到如下错误:

>>> timeit.timeit( "ms = df1s.merge(df2s, on='A')" )
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/opt/conda/lib/python3.6/timeit.py", line 233, in timeit
    return Timer(stmt, setup, timer, globals).timeit(number)
  File "/opt/conda/lib/python3.6/timeit.py", line 178, in timeit
    timing = self.inner(it, self.timer)
  File "<timeit-src>", line 6, in inner
NameError: name 'df1s' is not defined

Answer 1

首先，pandas DataFrame 不是作为简单的多维数组实现的。在代码中，它将对象描述为:

Two-dimensional size-mutable, potentially heterogeneous tabular data structure with labeled axes (rows and columns). Arithmetic operations align on both row and column labels. Can be thought of as a dict-like container for Series objects.

这是非常复杂的，我不希望任何人立即解决这个问题。

这提到的是，它“可以被认为是”作为像对象一样的字典。这意味着它可能会使用某种哈希映射，这意味着查找时间是恒定的。

由于后端结构完全不同，因此合并哈希映射与合并数组(合并 2 堆论文所做的工作)无法比较。因此排序不会有什么不同。

不幸的是，DataFrame 和哈希映射之间的连接并不完美。哈希映射通常是未排序的，并且不能有重复的条目，这两个条目都不匹配 DataFrame 对象实现。

另一种可能性，似乎更有可能从查看代码来看，由于合并操作不假定列已排序，因此在应用更像数组的合并之前，它会继续对列本身进行排序。这意味着预排序不会有什么不同，因为无论如何合并都会对列进行重新排序。

可以找到pandas DataFrame 对象代码 here
可以找到 DataFrame 的合并操作的合并操作 here .