如何合并两个带排序MultiIndex的DataFrame且结果保持排序MultiIndex？

Great question! Since both of your DataFrames are already sorted on their MultiIndex, we can implement a two-pointer (merge sort-like) approach that runs in linear time (O(n+m)) (where (n) and (m) are the row counts of the two DataFrames). This matches the efficiency of merging two ordered lists, avoiding the higher (O((n+m)\log(n+m))) complexity of concatenating then re-sorting.

Step-by-Step Solution #

Here's how to implement it:

1. Initialize pointers to track our position in each DataFrame
2. Iterate through both DataFrames, comparing the current MultiIndex entries
3. Append the row with the smaller index to the result
4. Once one DataFrame is exhausted, append all remaining rows from the other

import pandas as pd

# Your sample data
t1 = pd.DataFrame(data={'i1':[0,0,1,1,2,2], 'i2':[0,1,0,1,0,1], 'x':[1.,2.,3.,4.,5.,6.]})
t1.set_index(['i1','i2'], inplace=True)
t1.sort_index(inplace=True)

t2 = pd.DataFrame(data={'i1':[0,0,1,1,2,2], 'i2':[2,3,2,3,2,3], 'x':[7.,8.,9.,10.,11.,12.]})
t2.set_index(['i1','i2'], inplace=True)
t2.sort_index(inplace=True)

def merge_sorted_multiindex(df1, df2):
    n, m = len(df1), len(df2)
    i = j = 0
    result_rows = []
    
    while i < n and j < m:
        # Compare the current MultiIndex entries (pandas supports direct comparison of MultiIndex tuples)
        if df1.index[i] < df2.index[j]:
            result_rows.append(df1.iloc[i])
            i += 1
        else:
            result_rows.append(df2.iloc[j])
            j += 1
    
    # Append any remaining rows from the non-exhausted DataFrame
    result_rows.extend(df1.iloc[i:].to_list())
    result_rows.extend(df2.iloc[j:].to_list())
    
    # Combine into a single DataFrame, preserving the sorted MultiIndex
    merged_df = pd.DataFrame(result_rows).set_index(['i1', 'i2'])
    return merged_df

# Get the merged result
merged = merge_sorted_multiindex(t1, t2)
print(merged)

Output #

x
i1 i2       
0  0    1.0
   1    2.0
   2    7.0
   3    8.0
1  0    3.0
   1    4.0
   2    9.0
   3   10.0
2  0    5.0
   1    6.0
   2   11.0
   3   12.0

Why not just pd.concat([t1,t2]).sort_index()? #

While that approach works for small datasets, it requires a full re-sort of the combined data, which has a time complexity of (O((n+m)\log(n+m))). For large datasets (e.g., millions of rows), this will be significantly slower than our linear-time merge approach.

内容的提问来源于stack exchange，提问作者S.V