Алгоритм типа сортировки

До записи надо было думать об индексировании.

> Легко соорудить алгоритм M log N

Зачем его сооружать, он придуман давно... у Вирта описан.

Во-первых, есть линейный алгоритм - это просто один шаг quicksort'а: нужно найти N-е по "размеру" число и потом просто прогуляться по массиву, выбирая числа, которые его не меньше (с маленьикими модификациями, если числа могут быть равны). Основная часть его - это процедура выбора N-ного элемента, SELECT(N). А она скорее всего уже знакома. Если нет - то вот http://en.wikipedia.org/wiki/Selection_algorithm. Это опять фактически quicksort - на каждом шагу выбираем pivot и делаем вокруг нее partition. Если pivot выбирать случайно, то получится в среднем O(N) + хороший коэффициент + простая реализация. Либо можно получить детерминированный O(N), если на каждом шагу разбивать массив на пятерки, и выбирать медиану их медиан как pivot рекурсивно - тут и реализация сложнее и реальная производительность хуже. Да, я понимаю, что это алгоритм для выбора N максимальных элементов - переделать его на индексы, сохранив линейность, очень просто - достаточно завести параллельный массив 1...M. Хотя наверняка можно придумать что-то умнее.

Во-вторых, самый простой алгоритм с O(M log N) - это просто M операций вставки плюс (M - N) удаления из (your favorite implementation of a) min-heap размера N. В каком смысле тут надо много числа двигать?

Такой линейный алгоритм не подойдет - слишком большой объем данных, в память не поместится чтоб его qsortом ворочать.

имхо, вариант с хипом - то что нужно

А разрядность чисел известна? А то даром что ли целые.

В голову приходит такой велосипед - поиск N-го по величине значения с помощью дихотомии. Это log(N) итераций. На каждой итерации определять, сколько чисел больше пробной величины. По этой переменной (count (*) where value > эта_переменная) и делать дихотомию.

Каждая итерация - один read-only проход по массиву длиной M. Всего logN проходов.

Константу можно улучшить, заменив двойку у основания на, скажем, 32 - лишь бы гистограмма хорошо поместилась в кэш 1-го уровня.

Пардон, не log(N) итераций, а РАЗРЯДНОСТЬ итераций. Соответственно, сложность = M * РАЗРЯДНОСТЬ, где разрядность может быть как в битах, так и в любых других единицах (скажем, по 5 бит, как написано выше).

Thanks, http://en.wikipedia.org/wiki/Selection_algorithm -- то, что искал.

> В каком смысле тут надо много числа двигать?

M операций вставки. Чтобы от логарифма N не уходить, надо либо держать хип упорядоченным, либо дерево вертеть.

> слишком большой объем данных, в память не поместится чтоб его qsortом ворочать.

Нормально, у меня памяти хватит.

> А разрядность чисел известна? А то даром что ли целые.

Нет, к сожалению. Возможны любые восьмибайтные целые.

> До записи надо было думать об индексировании.

А это я и сооружаю индекс. Все в памяти, но у меня ее 64 гига.

> Да, я понимаю, что это алгоритм для выбора N максимальных элементов - переделать его на индексы, сохранив линейность, очень просто - достаточно завести параллельный массив 1...M. Хотя наверняка можно придумать что-то умнее.

Остановился на таком варианте: нахожу N-е по "размеру" число и прохожу по массиву M, запихивая индексы бОльших элементов в FIFO. Мне потом как раз эта очередь и нужна.