Ответ 1
Давайте начнем с установления ориентира. Самый простой способ решить эту проблему - использовать временный столбец "ключ":
def cartesian_product_basic(left, right):
return (
left.assign(key=1).merge(right.assign(key=1), on='key').drop('key', 1))
cartesian_product_basic(left, right)
col1_x col2_x col1_y col2_y
0 A 1 X 20
1 A 1 Y 30
2 A 1 Z 50
3 B 2 X 20
4 B 2 Y 30
5 B 2 Z 50
6 C 3 X 20
7 C 3 Y 30
8 C 3 Z 50
Как это работает, так это то, что обоим фреймам данных назначается временный столбец "ключа" с одинаковым значением (скажем, 1). Затем merge выполняет JOIN "многие ко многим" для "ключа".
Хотя трюк "многие ко многим" работает для DataFrames разумного размера, вы увидите относительно более низкую производительность при работе с большими данными.
Более быстрая реализация потребует NumPy. Вот некоторые известные реализации NumPy 1-мерного декартового произведения. Мы можем использовать некоторые из этих эффективных решений, чтобы получить желаемый результат. Моя любимая, однако, первая реализация @senderle.
def cartesian_product(*arrays):
la = len(arrays)
dtype = np.result_type(*arrays)
arr = np.empty([len(a) for a in arrays] + [la], dtype=dtype)
for i, a in enumerate(np.ix_(*arrays)):
arr[...,i] = a
return arr.reshape(-1, la)
Обобщение: CROSS JOIN для уникальных или неуникальных проиндексированных фреймов данных
отказ
Эти решения оптимизированы для DataFrames с несмешанными скалярными dtypes. Если вы имеете дело со смешанными dtypes, используйте на свой страх и риск!
Этот трюк будет работать на любом виде DataFrame. Мы вычисляем декартово произведение числовых индексов DataFrames с использованием вышеупомянутого cartesian_product, используем его для переиндексации DataFrames и
def cartesian_product_generalized(left, right):
la, lb = len(left), len(right)
idx = cartesian_product(np.ogrid[:la], np.ogrid[:lb])
return pd.DataFrame(
np.column_stack([left.values[idx[:,0]], right.values[idx[:,1]]]))
cartesian_product_generalized(left, right)
0 1 2 3
0 A 1 X 20
1 A 1 Y 30
2 A 1 Z 50
3 B 2 X 20
4 B 2 Y 30
5 B 2 Z 50
6 C 3 X 20
7 C 3 Y 30
8 C 3 Z 50
np.array_equal(cartesian_product_generalized(left, right),
cartesian_product_basic(left, right))
True
И, по аналогии,
left2 = left.copy()
left2.index = ['s1', 's2', 's1']
right2 = right.copy()
right2.index = ['x', 'y', 'y']
left2
col1 col2
s1 A 1
s2 B 2
s1 C 3
right2
col1 col2
x X 20
y Y 30
y Z 50
np.array_equal(cartesian_product_generalized(left, right),
cartesian_product_basic(left2, right2))
True
Это решение может распространяться на несколько фреймов данных. Например,
def cartesian_product_multi(*dfs):
idx = cartesian_product(*[np.ogrid[:len(df)] for df in dfs])
return pd.DataFrame(
np.column_stack([df.values[idx[:,i]] for i,df in enumerate(dfs)]))
cartesian_product_multi(*[left, right, left]).head()
0 1 2 3 4 5
0 A 1 X 20 A 1
1 A 1 X 20 B 2
2 A 1 X 20 C 3
3 A 1 X 20 D 4
4 A 1 Y 30 A 1
Дальнейшее упрощение
Более простое решение, не включающее @senderle cartesian_product, возможно при работе только с двумя DataFrames. Используя np.broadcast_arrays, мы можем достичь почти такого же уровня производительности.
def cartesian_product_simplified(left, right):
la, lb = len(left), len(right)
ia2, ib2 = np.broadcast_arrays(*np.ogrid[:la,:lb])
return pd.DataFrame(
np.column_stack([left.values[ia2.ravel()], right.values[ib2.ravel()]]))
np.array_equal(cartesian_product_simplified(left, right),
cartesian_product_basic(left2, right2))
True
Сравнение производительности
Сравнивая эти решения на некоторых надуманных фреймах данных с уникальными индексами, мы имеем
Обратите внимание, что сроки могут варьироваться в зависимости от вашей настройки, данных и выбора вспомогательной функции cartesian_product зависимости от ситуации.
Код производительности производительности
Это временный скрипт. Все функции, вызываемые здесь, определены выше.
from timeit import timeit
import pandas as pd
import matplotlib.pyplot as plt
res = pd.DataFrame(
index=['cartesian_product_basic', 'cartesian_product_generalized',
'cartesian_product_multi', 'cartesian_product_simplified'],
columns=[1, 10, 50, 100, 200, 300, 400, 500, 600, 800, 1000, 2000],
dtype=float
)
for f in res.index:
for c in res.columns:
# print(f,c)
left2 = pd.concat([left] * c, ignore_index=True)
right2 = pd.concat([right] * c, ignore_index=True)
stmt = '{}(left2, right2)'.format(f)
setp = 'from __main__ import left2, right2, {}'.format(f)
res.at[f, c] = timeit(stmt, setp, number=5)
ax = res.div(res.min()).T.plot(loglog=True)
ax.set_xlabel("N");
ax.set_ylabel("time (relative)");
plt.show()
