Есть известная задача для новичков которые только научились алгоритму поиска минимума в массиве: найти M минимальных в массиве из N элементов.

И вот коллега недавно проводил собеседование и троллил соискателя вариацией:

Есть десятки терабайт логов — обозначим их как N записей — каждая запись содержит в частности значение некоторого параметра A. Мы хотим выбрать небольшое количество M (ну скажем, миллион) записей в которых значение параметра минимально. Как это сделать?

Характерные нюансы вариации:

• исходные данные живут во внешней памяти, в оперативку их целиком не прогрузишь;
• очень желательно чтобы алгоритм можно было распараллелить т.к. N определяемое терабайтами близко по порядку к 1e12 и один проход на обычном компьютере будет занимать примерно сутки (исходный массив хранится в распределённой системе так что нет проблем с тем чтобы использовать его пофрагментно).

Собеседуемого мой коллега успешно затроллил и выгнал с позором, но потом я взялся троллить его самого — и его собственное решение ему нравиться перестало.

Какие возможны подходы к этой задаче?

У меня родилось немного "детских" версий:

1. Можно идти по нашим данным и пихать их в двоичную кучу с максимальным размером M (т.е. пропускаем элемент если его параметр больше чем максимальный в куче, а если в кучу что-то запихнули и размер стал M+1 то вытряхнем из неё максимальный элемент). Быстродействие здесь будет лучше чем N*log(M) потому что не придётся обычно пихать все элементы — даже вероятно ближе к N + M*log(M). Однако как распараллелить двоичную кучу? Возможно заменить её на ConcurrentSkipListMap...

2. Если само M таково, что не помещается в оперативку (ещё вариация предложенная коллегой), то вместо кучи мы будем складывать элементы в список-копилку и после достижения размера 2M будем её сортировать слияниями и обрезать размер до M. Быстродействие по-видимому N*log(M). Распараллеливать наверное не очень легко но можно.

3. Больше всего мне нравится вариант (против которого коллега протестует) стохастический: пройдём по исходным данным и выберем все записи значение параметра у которых ниже некоего порога k. Как определим этот порог? Тут разные варианты — например сделаем предварительный проход по данным и выберем рандомно столько значений параметра сколько влезает в оперативку, скажем миллиард. Возьмём от них пропорциональное M/N количество наименьших значений и в качестве порога k выберем максимальное из этих значений. Конечно в результате просеивания мы потом можем получить не совсем M записей — но мы можем либо заранее завысить порог, чтобы прицелиться на 2M записей например — и отбросить лишнее. Т.е. этот способ хорош "среднестатистически". Его сложность может быть близка к O(N) и распараллелить его вроде легко.

Но хотелось бы узнать о более остроумных вариантах — если есть какая-то удобная структура со свойствами очереди с приоритетами, которую можно распараллеливать (а то ещё держать во внешней памяти) — то первый вариант можно довести до ума?