Как сделать пересечение массивов в Python?

Как сделать пересечение массивов в Python

Пересечение массивов (set intersection) — это операция поиска общих элементов в двух или более массивах/списках. В Python есть несколько способов реализации с разными характеристиками производительности.

Вариант 1: Использование set

Самый эффективный и pythonic способ:

arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]

# Способ 1: оператор &
intersection = set(arr1) & set(arr2)
print(intersection)  # {3, 4, 5}

# Способ 2: метод intersection()
intersection = set(arr1).intersection(set(arr2))
print(intersection)  # {3, 4, 5}

# Способ 3: метод intersection() с распаковкой
intersection = set(arr1).intersection(arr2)  # arr2 может быть списком
print(intersection)  # {3, 4, 5}

Сложность: O(n + m), где n и m — размеры массивов.

Вариант 2: Несколько массивов

arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
arr3 = [4, 5, 8, 9, 10]

# Пересечение всех трёх
intersection = set(arr1) & set(arr2) & set(arr3)
print(intersection)  # {4, 5}

# Или через метод
intersection = set(arr1).intersection(arr2, arr3)
print(intersection)  # {4, 5}

# С переменным числом массивов
arrays = [arr1, arr2, arr3]
intersection = set(arrays[0])
for arr in arrays[1:]:
    intersection &= set(arr)
print(intersection)  # {4, 5}

# Или более elegantly
intersection = set.intersection(*[set(arr) for arr in arrays])
print(intersection)  # {4, 5}

Вариант 3: С сохранением порядка

Set не сохраняет порядок. Если нужно сохранить порядок из первого массива:

arr1 = [1, 2, 3, 4, 5]
arr2 = [5, 4, 3, 6, 7]

# Способ 1: list comprehension
intersection = [x for x in arr1 if x in arr2]
print(intersection)  # [3, 4, 5]

# Способ 2: более эффективно с set
set_arr2 = set(arr2)
intersection = [x for x in arr1 if x in set_arr2]
print(intersection)  # [3, 4, 5] — быстрее!

# Способ 3: filter
intersection = list(filter(lambda x: x in set(arr2), arr1))
print(intersection)  # [3, 4, 5]

Сложность: O(n + m) вместо O(n*m) с проверкой в списке.

Вариант 4: Отсортированные массивы (два указателя)

Если массивы уже отсортированы, можно использовать алгоритм двух указателей:

def intersection_sorted(arr1, arr2):
    """Пересечение двух отсортированных массивов"""
    result = []
    i, j = 0, 0
    
    while i < len(arr1) and j < len(arr2):
        if arr1[i] == arr2[j]:
            result.append(arr1[i])
            i += 1
            j += 1
        elif arr1[i] < arr2[j]:
            i += 1
        else:
            j += 1
    
    return result

arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(intersection_sorted(arr1, arr2))  # [3, 4, 5]

Сложность: O(n + m) — очень эффективно для отсортированных данных!

Вариант 5: Обработка дубликатов

Если нужно сохранить все дубликаты:

from collections import Counter

arr1 = [1, 2, 2, 3, 3, 3, 4, 5]
arr2 = [2, 3, 3, 4, 4, 5, 6]

# Способ 1: с дубликатами как в меньшем массиве
counter1 = Counter(arr1)
counter2 = Counter(arr2)

intersection = []
for num in counter1:
    if num in counter2:
        # Берём минимальное количество
        count = min(counter1[num], counter2[num])
        intersection.extend([num] * count)

print(sorted(intersection))  # [2, 3, 3, 4, 5]

# Способ 2: используя Counter.intersection
intersection_counter = counter1 & counter2
intersection = list(intersection_counter.elements())
print(sorted(intersection))  # [2, 3, 3, 4, 5]

Вариант 6: NumPy для больших массивов

Для больших численных массивов:

import numpy as np

arr1 = np.array([1, 2, 3, 4, 5])
arr2 = np.array([3, 4, 5, 6, 7])

intersection = np.intersect1d(arr1, arr2)
print(intersection)  # [3 4 5]

Характеристики:

• Быстро для больших массивов (написано на C)
• Автоматически удаляет дубликаты и сортирует
• Гибкость с параметром assume_unique

Сравнение производительности

import time
import numpy as np

# Создать большие массивы
arr1 = list(range(0, 1000000, 2))  # 500,000 элементов
arr2 = list(range(500000, 1500000, 2))  # 500,000 элементов

# Метод 1: set
start = time.time()
result1 = set(arr1) & set(arr2)
time1 = time.time() - start
print(f"Set method: {time1:.4f}s")

# Метод 2: list comprehension
start = time.time()
set_arr2 = set(arr2)
result2 = [x for x in arr1 if x in set_arr2]
time2 = time.time() - start
print(f"List comprehension: {time2:.4f}s")

# Метод 3: NumPy
start = time.time()
result3 = np.intersect1d(arr1, arr2)
time3 = time.time() - start
print(f"NumPy: {time3:.4f}s")

# Результат: NumPy обычно быстрее для больших данных

Практический пример: поиск общих друзей

class User:
    def __init__(self, name, friends):
        self.name = name
        self.friends = set(friends)
    
    def common_friends(self, other_user):
        """Найти общих друзей"""
        return self.friends & other_user.friends
    
    def common_friends_with_multiple(self, users):
        """Найти общих друзей со всеми пользователями"""
        common = self.friends
        for user in users:
            common &= user.friends
        return common

alice = User("Alice", ["Bob", "Charlie", "David", "Eve"])
bob = User("Bob", ["Alice", "Charlie", "Frank"])
charlie = User("Charlie", ["Alice", "Bob", "Grace"])

print(alice.common_friends(bob))  # {'Charlie'}
print(alice.common_friends_with_multiple([bob, charlie]))  # {'Charlie'}

Оптимизация для больших наборов данных

def efficient_intersection(arrays):
    """Оптимизированное пересечение нескольких массивов"""
    if not arrays:
        return []
    
    # Найти самый маленький массив
    min_array = min(arrays, key=len)
    other_arrays = [set(arr) for arr in arrays if arr is not min_array]
    
    # Проверять только элементы из самого маленького
    result = []
    for item in min_array:
        if all(item in arr for arr in other_arrays):
            result.append(item)
    
    return result

arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
arr3 = [4, 5, 8, 9, 10]

print(efficient_intersection([arr1, arr2, arr3]))  # [4, 5]

Типичные ошибки

# ❌ Неправильно: медленно для больших данных
arr1 = range(1000000)
arr2 = range(500000, 1500000)
intersection = [x for x in arr1 if x in arr2]  # O(n*m)!

# ✅ Правильно: быстро
arr2_set = set(arr2)
intersection = [x for x in arr1 if x in arr2_set]  # O(n + m)

# ❌ Неправильно: потеря порядка не требуется
intersection = sorted(set(arr1) & set(arr2))  # Лишняя сортировка

# ✅ Правильно: если порядок не важен
intersection = set(arr1) & set(arr2)

Заключение

Пересечение массивов в Python:

• Set операции (&, intersection()) — быстро и просто
• List comprehension с set — сохраняет порядок
• Двойной указатель для отсортированных массивов
• Counter для сохранения дубликатов
• NumPy для больших численных массивов
• Оптимизация: проверять маленький массив против больших
• Сложность: избегать O(n*m), стремиться к O(n + m)