Исходный код и его сложность:
res = []
for i in range(len(a)):
for j in range(len(b)):
if a[i] == b[j]:
res.append((i, j))
Время: $O(nm)$ (где $n=|a|,m=|b|$). Память: $O(k)$ для результата (где $k$ — число совпадений).
Практическое задание — оптимизировать и оценить выигрыш. Предложенные решения, объяснение и оценки.
1) Хэш-таблица по b (рекомендуемый общий случай)
Код:
from collections import defaultdict
pos = defaultdict(list)
for j, val in enumerate(b):
pos[val].append(j)
res = []
for i, val in enumerate(a):
for j in pos.get(val, ()):
res.append((i, j))
Анализ:
- Построение: $O(m)$ время.
- Поиск: суммарно $O(n+k)$ (каждый элемент a делает ожидаемый O(1)-lookup, плюс перебор реальных совпадений).
- Итого: ожидаемое $O(n+m+k)$ времени.
- Память: $O(u+k)$, где $u$ — число уникальных значений в b (хэш-структура + списки индексов).
Практический выигрыш: вместо квадратичной сложности — почти линейная. Пример: при $n=m=10^5$ naive делает $10^{10}$ сравнений, хэш-метод ≈ $2\cdot 10^5$ операций + перебор совпадений — выигрыш по времени порядка $\frac{10^{10}}{2\cdot 10^5}=5\cdot 10^4$.
2) Если важна только проверка вхождения (не нужны индексы)
Код:
set_b = set(b)
res = [i for i, val in enumerate(a) if val in set_b]
Анализ: время $O(n+m)$, память $O(u)$. Быстрее и экономнее по памяти, если индексы не нужны.
3) Сортировка + двухуказатель (когда память для хэша ограничена)
Код (сохранение индексов):
sa = sorted((val, i) for i, val in enumerate(a))
sb = sorted((val, j) for j, val in enumerate(b))
i = j = 0
res = []
while i < len(sa) and j < len(sb):
if sa[i][0] < sb[j][0]:
i += 1
elif sa[i][0] > sb[j][0]:
j += 1
else:
# при равных значениях может потребоваться учитывать дубликаты
# соберите все равные в блоки и создайте декартово произведение индексов
...
Анализ: время $O(n\log n+m\log m+k)$, память $O(n+m)$. Подходит, если хэш-накладные расходы недопустимы или данные нужно сортировать/агрегировать далее. Можно делать внешнюю сортировку для больших данных.
4) Векторизация / numpy (для числовых массивов)
Использовать argsort + searchsorted или маски; сложность похожа на сортировку: $O(n\log n+m\log m)$, часто быстрее в константе за счёт C-реализации. Память: дополнительные массивы.
5) Потоковая обработка, генераторы, запись результата на диск
Если $k$ очень велик и нельзя хранить результат в памяти — yield пары из цикла или записывать в файл/БД вместо накопления в list. Память ≈ $O(1)$ (помимо структур для поиска).
6) Распараллеливание и шардинг для очень больших входов
Разбить по хэш-значению (sharding) и обрабатывать в параллельных процессах или узлах; для распределённых данных подойдёт MapReduce/SQL/SQLite. Позволяет масштабировать по времени и памяти.
7) Специальные структуры при ограниченном домене
Если значения — целые в небольшом диапазоне, использовать массив индексирования/битовые массивы (bitmap), что даёт очень низкое потребление и быстрые операции.
Краткая сводка сложностей:
- Наивный: время $O(nm)$, память $O(k)$.
- Хэш по b: время $O(n+m+k)$ (ожид.), память $O(u+k)$.
- Set (только вхождение): время $O(n+m)$, память $O(u)$.
- Сортировка + двухуказатель: время $O(n\log n+m\log m+k)$, память $O(n+m)$.
Рекомендация:
- По умолчанию использовать хэш-таблицу по b (вариант 1). Для огромных данных — комбинировать шардинг/внешнюю сортировку/потоковую обработку. Если нужны оценки для конкретных размеров (память в байтах, время в секундах) — пришлите $n$, $m$, характеристики данных (уникальность, тип) и мой пример оценю точнее.