Как объединить два кадра данных не по значениям, а по диапазонам значений?

Question

Фрейм данных A:

pd.Dataframe({
    'price': [50, 150, 250], 
    'group':[2, 5, 10]
})

Фрейм данных B:

pd.Dataframe({
    'low_price': [0, 100, 200], 
    'high_price': [99, 199, 299],
    'low_group':[0, 4, 8],
    'high_group':[3, 6, 12],
    'something':['A', 'B', 'C']
})

Как объединить эти фреймы данных при условии, как:
- Цена фрейма данных A составляет между Низкие и высокие цены в кадре данных.
AND
- Группа данных в кадре А * между Низкими и высокими группами данных в кадре В.

Есть ли способ сделать это без итерации по строкам и проверки по очереди?Я уже сделал это так, и это стоит O (n ^ 2), не масштабируется.

---

EDIT :

PS1: Каждая строка в A имеет 0или 1 совпадение в B. Я ищу "внутреннее" слияние.

PS2: у A миллионы записей, у B сотни.

Answer 1

Вы не можете легко сделать это одновременно для цены и группы, но merge_asof может присоединиться к соответствующей low_price of B для каждой строки из A за один проход. Тогда запрос выбора с loc сохранит только строки, соответствующие другим условиям.

pd.merge_asof(A, B, left_on='price', right_on='low_price').query(
    '(price<=high_price)&(group>=low_group)&(group<=high_group)')

Answer 2

Если ваши данные уже отсортированы, вы можете получить их до O (log n), если вы реализуете какой-то бинарный поиск, чтобы найти, где разделить данные (Предполагая, что процесс объединения не занимает больше, чемO (log n) также).

Если ваши данные не отсортированы, лучшее, что вы можете сделать, - это O (n), слияние одновременно с обнаружением кандидата на слияние.