Как выбрать наименее N элементов с ограниченным пространством?

Question

Проблема:

Функция f возвращает элементы один за один раз в неизвестном порядке. Я хочу выбрать наименьшие N элементов. Функция f называется много раз (я просматриваю очень сложное пространство поиска), и у меня недостаточно памяти для хранения каждого выходного элемента для будущей сортировки.

Очевидное решение:

Держите вектор N элементов в памяти и на каждом f() поиска минимального и максимального и, возможно, заменить что-то. Вероятно, это работает для очень маленького N. Тем не менее, я ищу более общее решение.

Мое решение до сих пор:

Я хотя об использовании priority_queue для того, чтобы хранить, скажем, 2N значения и уменьшая верхнюю половину после каждого 2N шагов.

псевдокод:

while (search goes on) 
    for (i=0..2N) 
     el = f() 
     pust el to the priority queue 
    remove N greatest elements from the priority queue 
select N least elements from the priority queue 

Я думаю, что это должно работать, однако, я не считаю его элегантным вообще. Возможно, уже существует какая-то структура данных, которая справляется с этой проблемой. Было бы очень просто изменить priority_queue, чтобы выбросить элементы, которые не вписываются в сохраненный диапазон.

Не могли бы вы порекомендовать мне существующую структуру данных std для C++ или предложить мне реализовать решение, которое я предложил выше? Или, может быть, есть отличный и элегантный трюк, о котором я не могу думать.

Answer 1

Вы хотите найти least n элементов всего K элементов, полученных от вызова функции. Каждый раз, когда вы вызываете функцию f(), вы получаете один элемент, и вы хотите сохранить least n элементов среди них без сохранения всего k элементов, полученных от функции с k слишком большой.

Вы можете задать heap or priority_queue, чтобы сохранить это least n, найденное до сих пор. Просто добавьте возвращенный элемент из f() в pq и введите наибольший элемент, если его размер стал n+1.

Общая сложность была бы O(K*log(n)), а пространство было бы O(n). (Если мы игнорируем дополнительное пространство, требуемое pq)

Answer 2

Альтернативный вариант - использовать массив. В зависимости от максимально допустимых элементов по сравнению с N, есть два варианта я могу думать:

1. Сделать массив как можно больше и несортированный, периодически извлекать мельчайшие элементы.
2. Имейте массив размером N, отсортированный с максимальными элементами на конце.

Вариант 1 бы сортировать массив с O(n log n) времени каждый раз, когда вы заполните массив. Это произойдет для каждого элемента n - N (кроме первого раза), что дает (k - n)/(n - N) сортировки, что приводит к сложности времени O((k - n)/(n - N) n log n) для k всего элементов, n элементов в массиве, N элементов подлежит отображению. Итак, для n = 2N вы получаете O(2*(k - 2N) log 2N) сложность времени, если я не ошибаюсь.

Вариант 2 у вас будет массив (размер N), отсортированный с максимальными элементами в конце. Каждый раз, когда вы получаете элемент, вы можете быстро (O(1)) посмотреть, меньше ли он последнего. Используя двоичный поиск, вы можете найти нужное место для элемента в O(log N) времени. Однако теперь вам нужно переместить все элементы после того, как новый элемент останется в одном месте. Это занимает O(N) раз. Таким образом, вы заканчиваете теоретическую сложность времени O(k*N). Учитывая, что компьютеры, такие как работа с гомогенными доступом к данным, однако (кеши и прочее), могут быть быстрее, чем куча, даже если они поддерживаются массивом.

Если ваши элементы большие, вам может быть лучше иметь структуру { coparison_value; actual_element_pointer }, даже если вы используете кучу (если только она не поддерживается списком).