Короткий анализ исходного кода
- Пусть $n=$ len(arr). Внешний цикл и внутренний (по всем предыдущим индексам) дают число сравнений $\frac{n(n-1)}{2}$, т.е. временная сложность $\mathcal{O}(n^2)$.
- Доп. память (без учёта результирующего списка) — $\mathcal{O}(1)$. Результат может занимать до $\frac{n(n-1)}{2}$ пар в худшем случае (всё одинаково), т.е. выходной объём памяти тоже $\mathcal{O}(n^2)$.
Более эффективный подход (для больших данных)
1) Хеш-таблица: однопроходный алгоритм, где для каждого значения храним список предыдущих индексов и при встрече нового элемента формируем пары с этими индексами. Средняя сложность времени $\mathcal{O}(n+M)$, где $M$ — число возвращаемых пар (нижняя граница — нужно вывести все пары). Память: хранится словарь индексов — $\mathcal{O}(n)$ плюс пространство для вывода $\mathcal{O}(M)$.
Пример (лениво, с генератором):
def find_pairs(arr):
idxs = {}
for i, v in enumerate(arr):
for j in idxs.get(v, ()):
yield (j, i)
idxs.setdefault(v,[]).append(i)
2) Если нужен только счёт пар (не сами пары): подсчитать частоты $c$ для каждого значения и суммировать $\left(\genfrac{}{}{0ex}{}{c}{2}\right)=\frac{c(c-1)}{2}$. Время $\mathcal{O}(n)$, память $\mathcal{O}(k)$ (k — число различных значений).
3) Сортировка по значению (если память ограничена и можно использовать внешнюю сортировку): сортировать пары (value, index) за $\mathcal{O}(n\log n)$, затем в каждом сгруппированном блоке генерировать пары. Время $\mathcal{O}(n\log n+M)$, память $\mathcal{O}(n)$ или меньше при внешней/стриминговой сортировке.
Компромиссы и практические замечания
- Выходной объём ограничивает всё: если $M$ велик (например, всё равно $M=\frac{n(n-1)}{2}$), то любое решение будет требовать $\Omega (M)$ времени и памяти при сохранении всех пар.
- Память vs потоковая выдача: если нельзя хранить все пары — использовать генератор/стриминг, тогда пиковая память $\mathcal{O}(n)$ (для индексов в хеше) вместо $\mathcal{O}(M)$.
- Порядок пар: исходный код выдаёт пары в порядке по второму индексу $i$ (увеличивающемуся), внутри фиксированного $i$ — по $j$ возрастанию. Хеш-реализация может сохранить тот же порядок, если в списках индексов сохранять порядок добавления; сортировка даст порядок по значению (и по индексу внутри значения) — порядок будет другим.
- Потокобезопасность: общая хеш-таблица или общий список результатов не потокобезопасны — нужны блокировки или потокобезопасные структуры. Для параллелизации лучше шардинг по хешу значений: каждый поток обрабатывает свой набор значений (нет гонок), затем результаты объединяются. Альтернатива — распределённая обработка (map-reduce) по значениям.
- Устойчивость/предсказуемость: сортировка даёт детерминированный порядок и расходы времени $\mathcal{O}(n\log n)$ (без зависимостей от хеш-коллизий), хеш-метод обычно быстрее в среднем $\mathcal{O}(n)$.
Рекомендация
- Если нужно получить все пары и $M$ может быть большим — использовать хеш-таблицу + генератор (ленивую выдачу) или распределённую/шардированную обработку.
- Если требуется только количество пар — считать частоты и использовать $\left(\genfrac{}{}{0ex}{}{c}{2}\right)$.
- Если важен стабильный/детерминированный порядок или ограничена память на хосте — сортировка с последующим группированием (внешняя сортировка при больших данных).