pandas DataFrame.join 的运行时间（大“O”顺序）是多少？

Question

这个问题更具概念性/理论性（与非常大的数据集的运行时间有关），所以我很抱歉没有一个最小的例子来展示。

我有一堆来自两个不同传感器的数据帧，我需要最终将它们连接成来自两个不同传感器（和）的两个非常大的数据帧，然后左连接成一个数据帧。我的数据是这样的，我也可以先加入，然后连接，或某种组合。我试图找出最有效的方法来做到这一点。df_snsr1df_snsr2

通过阅读这个 SO 答案，我知道它会pandas.concat为其所有数据帧的串联分配空间，如果您在循环中执行此操作，则可能会导致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)但是，如果是，那么加入许多小数据帧然后连接对我来说可能会更有效他们而不是 concat 然后加入。整个操作需要足够长的时间，值得我在这里提出问题，所以“运行它并查看”是行不通的。

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

Answer 1

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

使用 default 时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'）？下面的代码比我想要的要冗长一些（并且名称生成简直是愚蠢的），但它就是这样做的。本质上，它创建了两个具有随机名称、无序且具有1 - replace_fraction共同分数的 DF；然后它会加入它们，同时测量所用的时间。

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发现除 之外的所有系数均为 0 n log n，所以上面的方法没问题）。