Если вы сказали максимум триллион, значит у вас есть диска на миллиард. (Иначе вам некуда 1/1000 сохранить)

Далее следует решение white owl, которое вам отсеивает верхний миллиард. По окончании потока, который не превышает триллион, делите счётчик сущностей на 1000, округляете в удобную для вас сторону (рекомендую вверх), и берете таковое число строчек из отсеянного миллиарда который уже на диске. Готово: точное решение в один проход потока неизвестного заранее размера.

Не забудьте отвести счётчику сущностей хотя бы 40 бит, всё-таки триллион ожидаете.

Чем вас не устраивает точное решение задачи?

А, вижу. Вас наверное не устраивает то, что вы думали что точного решения не существует, а оно оказалось довольно очевидным.

Ну тогда давайте забудем о существовании точного решения и решим неточно, статистическими методами. Только не способом тыка папы Карло, а с формулами.

На основании значений первых N cущностей делаете предположение о статистическом распределении Q. Надеетесь на гауссовое или равномерное в фиксированном интервале. Затем, выбрав погрешность альфа, определяете Qmin, которое с заданной погрешностью альфа будет меньше чем верхний 0.1% значений Q всей популяции, затем отбирает все сущности из потока для которых Q > Qmin.

Не забудьте сохранить первые N сущностей предшествующие анализу; они не бросовые. Число N зависит от альфы.

Вуаля, неточное решение зато с формулами и ограничениями на распределение Q.

Иван FXS,

Видел конечно.

Вам в памяти сущности хранить и не требуется, только Q значения уже сохранённых на диске сущностей, чтобы знать какие из них заменять.

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

И при условиях выше (поток произвольной длины, диск одноразовый) все эвристики разваливаются при Q = n, где n номер сущности в потоке.

Да. Первый миллион точно*. А если Q сущностей монотонно растет, то вообще все сущности потока коснутся диска, по правилу FIFO. Мало того, для монотонно растущих Q ничего лучше и не будет.

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

Не совсем в тему, но эту задачу базы данных решают точно и успешно каждый день. "Отсортировать таблицу неизвестной длины** по колонке Q, показать/сохранить первые 1% строчек". Строчки в БД могут содержать многомегабпйтные объекты.

(*) Предвидя возможные придирки, не всегда. min(1e6,N), где N длина потока.

(**) Иногда таблицы в БД не имеют известного числа строк. Это встречается, но не все с этим знакомы.

Иван FXS,

Я прочитал ваши недавние ответы, заметил что вас беспокоит скорость сохранения сущностей на диск.

Если точное решение не устраивает из-за медленной операции сохранения данных, которое в худшем случае включает в себя *все* сущности потока, ты вы будете оптимизировать сокращение числа сохранений в ущерб точности. Тут придется решать какой выигрыш стоит какой точности.

Например, отсортированный поток даст точность 0 (всегда не то что надо) для любой экономящей записи эвристики.

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

К сожалению, неуважительное отношение к собеседнику это часто, но не всегда особенность русскоязычных форумов.
Причина возможно в том, что ценность специалиста в первую очередь определяется не знанием, а умением продуктивно общаться с коллегами, и улучшать эффективность команды. Для людей значительных знаний в какой-то технической области добавляется обязательное требование уметь преподавать: связно и доходчиво выражать мысли, точку зрения и т.д.

Для первоначальной постановки задачи решение white owl выглядит на мой взгляд превосходно, поэтому появились вопросы чем точное решение не подходит, и есть ли дополнительные критерии.
Не сразу, но выяснилось что есть важный для вас но ранее не упомянутый критерий количества сохранений, который вы связываете со скоростью.

Что я знаю о вашей задаче: у вас есть поток этих сущностей, каждая содержит неотделимую от нее метрику Q. Поток высокоскоростной, неизвестной но конечной длины не превышающей миллиард.
Нужно в один проход выбрать и сохранить верхние 0.1%
сущностей по метрике Q. Диапазон Q неизвестен, порядок следования сущностей может быть любой.
Устройство может сохранить один миллион сущностей, не больше.
Метод сохранения сущностей считается медленным, поэтому точное решение с перезаписью не годится.
Допускается неточное решение, если оно использует меньше сохранений чем точное.

Этого мало для ТЗ. Если бы меня наняли решать такую задачу, я бы задал вопросы:
- прочность критериев. Например, можно ли любую часть потока читать дважды?
- природа данных, происхождение и примеры. Мне известны неудачные данные, которые мочат все эвристики в нулевую точность.
- скоростные характеристики потока данных и механизма сохранения. Это важно. Например, если вход один гигабит, а сохранение всего 100mbps, то при соотношении чтение/запись 10:1 и выше сохранение перестанет тормозить процесс. Оптимизировать вечно нет смысла.
- скоростные параметры железа. Если вычисляла слабая, некоторые подходы исключаются.
- допустимое количество ошибок, как меняется
- допустимое время исполнения.
- есть ли требование регулировки, чтоб заказчик мог сам подкручивать быстрее/точнее
- формат результата: "пришло 100500 шт, самые верхние были #42, #69, .. из них сохранены 88%"

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

Последнее вполне тянет на курсовую, где стоимость усилий и ответственность низкая.