Как упростить решение, чтобы пройти по списку меньше раз

Что проверяют

Умеете ли вы заметить, что решение несколько раз читает одни и те же данные, и собрать работу в один проход. Следом спрашивают, всегда ли один проход быстрее трёх и как тот же приём переносится на pandas или Spark, где данные не помещаются в память.

Как отвечать

Сначала честно оговорите: три прохода по O(n) это всё ещё O(n). Сокращать проходы имеет смысл, когда чтение дорогое (файл, сеть, таблица на миллиарды строк) или когда данные приходят итератором, который читается один раз. Затем приёмы:

• несколько агрегатов в одном цикле: сумма, минимум, максимум и счётчик копятся одновременно. Среднее и дисперсию можно считать потоково по алгоритму Уэлфорда;
• словарь или множество вместо поиска в списке: x in lst внутри цикла даёт O(n·m), заранее построенный set даёт O(n + m). Классика: задача двух сумм за один проход через dict уже встреченных значений;
• collections.Counter и defaultdict: подсчёт частот и группировка за один проход вместо list.count в цикле;
• генераторы: цепочка map, filter и генераторных выражений ленивая, каждый элемент проходит все шаги сразу, промежуточных списков нет;
• pandas: один groupby().agg() с набором функций вместо нескольких группировок, векторные операции вместо apply по строкам;
• Spark: каждое действие (count, collect, запись) заново вычисляет весь план. Если по одному DataFrame считается несколько результатов, его кэшируют через cache() или сводят вычисления в один agg.

Где спотыкаются

Считают, что один проход всегда быстрее. В CPython цикл, который на каждом элементе делает три дела, часто проигрывает трём встроенным sum, min и max, работающим на уровне C. Такое утверждение надо подкреплять замером.

Убирают дубли через list(set(lst)) и обещают сохранить порядок. Множество порядок не гарантирует, его сохраняет list(dict.fromkeys(lst)).

В Spark вызывают подряд несколько действий на тяжёлом DataFrame без кэша и не замечают, что источник читается столько же раз.