pandasDataFrame.join的运行时间（大"O"单）是多少？

Question

这个问题更多 conceptual/theoretical（对于非常大的数据集，有运行次），所以我很抱歉没有一个最小的例子来展示。

我有一堆来自两个不同传感器的数据帧，我需要最终将它们连接成来自两个不同传感器（df_snsr1 和 [=16] 的两个非常大数据帧=]), 然后左连接成一个DataFrame。我的数据是这样的，我也可以先加入，然后连接，或某种组合。我正在尝试找出最有效的方法。

根据阅读 I know that pandas.concat 分配 space 用于连接其所有数据帧，如果您在循环中执行此操作，可能会导致 O(N**2) 复制和一些严重的减速。因此，我目前首先构建一个大数据帧列表（从文件加载），一次将它们连接起来，然后加入两个大数据帧：

df_list = []
for file in my_pickle_files_snsr1:  # O(M) loop over M files
    df_list.append(pd.read_pickle(file))  # O(1) append, M times
df_snsr1 = pd.concat(df_list)  # O(N) copies of N records
# repeat for sensor 2 (df_snsr2)
df_snsr1.join(df_snsr2, on=['some', 'columns'])  # O(dunno, maybe bears?)

我无法在 pandas.DataFrame.join 上的文档中找到有关执行速度的任何信息。是O(N)吗？ O(N**2)？我的想法是，如果它与 pandas.concat 的顺序相似，那么我执行这两个操作的顺序实际上无关紧要。但是，如果它是 O(N**2)，那么它可能会更有效率对我来说加入许多小数据框然后连接它们而不是连接然后加入。整个操作需要足够长的时间，值得我在这里提问，所以 "run it and see" 不会起作用。

有人知道 join 使用的是什么算法以及它的执行大 O 顺序是什么吗？或者有人对获得 join 和 concat 的最有效组合有任何其他建议吗？

Answer 1

我认为这取决于您传递给 join 的选项（例如连接类型和是否排序）。

当使用默认的how='left'时，看起来结果是排序的，至少对于单个索引（文档只指定了一些输出的顺序how 方法中的一种，而 inner 不是其中之一）。无论如何，排序是 O(n log n)。每个索引查找是 O(1) 并且有 O(n) 个。所以，在那种情况下，O(n log n)占主导地位。

相比之下，在how='inner'情况下，指定保持调用DataFrame的顺序。在那种情况下，我们期望 O(n)（对于可能的集合交集以及索引查找和插入）。

在任何一种情况下，随着大小变大，缓存局部性（或缺乏缓存局部性）的各种问题开始逐渐出现在您身上，并且在随机访问中访问大内存区域所花费的实际时间将开始占主导地位。以上仅针对操作复杂度。

如其他地方所述，对于较大的数据集，Dask 或 Spark 是一种选择。

但是你说我们测试它是什么（至少 how='left' 案例）？下面的代码比我希望的要冗长一点（而且名称生成很愚蠢），但它就是这样做的。本质上，它使两个 DF 具有随机名称，无序，并且具有共同的 1 - replace_fraction 分数；然后它加入他们，同时测量使用的时间。

from IPython.core.magics.execution import _format_time as walltime

def make_names(n):
    names = [
        f'{x}{y}{z}' for (x, y), z in zip(
            np.random.choice(['foo', 'bar', 'hi'], (n, 2)),
            np.random.randint(0, n, size=n))
    ]
    return names

def work(n, replace_fraction=0.1):
    a_names = make_names(n)
    replace_n = int(n * replace_fraction)
    b_names = make_names(replace_n) + list(np.random.choice(a_names, size=n - replace_n, replace=False))
    np.random.shuffle(b_names)
    a = pd.DataFrame({
        'name': a_names,
        'v': np.random.uniform(size=n),
        'w': np.random.uniform(size=n),
    }).set_index('name')
    b = pd.DataFrame({
        'name': b_names,
        'v': np.random.uniform(size=n),
        'w': np.random.uniform(size=n),
    }).set_index('name')

    t0 = time.time()
    df = a.join(b, rsuffix='_r')
    dt = time.time() - t0
    return a, b, df, dt

示例：尝试 work(4, .5).

现在，对尺寸的几何系列进行一些时间测量：

sizes = (2**np.arange(10, 23, .5)).astype(int)
times = []
for n in sizes:
    a, b, df, dt = work(n)
    times.append(dt)
    print(f'{n}: {walltime(dt)}')

# out:
1024: 2.9 ms
1448: 4.78 ms
2048: 4.37 ms
...
2965820: 18.2 s
4194304: 30.2 s
5931641: 44.8 s

适合 n log n:

from numpy.polynomial.polynomial import polyfit

n = np.array(sizes)
t = np.array(times)
b, m = polyfit(n * np.log(n), t, 1)

plt.plot(n/1e6, t, '.')
plt.plot(n/1e6, b + m * n * np.log(n), '-')
plt.xlabel('size [M]')
plt.ylabel('time [s]')
plt.show()

(旁注：scipy.optimize.nnls 与所有项 n、log n、n log n、1 找到除 [=26= 之外的所有系数 0 ], 所以以上没问题).

pandasDataFrame.join的运行时间（大"O"单）是多少？

What is the running time (big "O" order) of pandas DataFrame.join?

python

big-o

execution-time

dataframe

pandas