Дано: обрабатывается большой поток неких "цифровых сущностей", представленных неким набором параметров, среди которых, есть параметр Q (от "quality").

Нужно отбирать из потока и сохранять на диске "самые лучшие" из сущностей по параметру Q, так, чтобы сохранялось около 1/1000 от общего объёма "просеянного" потока.

Каков тут может быть достаточно эффективный -- по соотношению "качество/затраты" -- алгоритм отбора?

Заковыка в том, что точного решения задача не имеет, ибо в процессе работы мы не можем определить, попадает ли то или иное Q в 1/1000 от всей выборки.

Также не желательно решение, предполагающее накопление (по ходу работы) всех числовых значений самого Q. Хотя бы потому, что оно является тривиальным.

миллиард

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

Наверное, мне стоило сразу сказать, что речь идет о методе Монте-Карло, так что то, что часть "не самых плохих" сущностей потеряется -- не критично.

- надеюсь, что вы прочитали словосочетание "набором параметров" в
-- каждая из "цифровых сущностей" многократно больше числа Q. Так что хранить в памяти 1/1000 от потока -- понятное решение, но несколько прямолинейное.

каким образом случайно выбранный экземпляр окажется одним из лучших (по параметру Q)?

Я размышляю над таким алгоритмом: имеем два параметра -- порог П и "шаг порога" Ш

1) если Q очередного экземпляра в потоке больше или равно П, то а) сбрасываем экземпляр на диск и б) изменяем порог

П = П + 999*Ш;

2) если Q очередного экземпляра в потоке меньше П, то а) игнорируем экземпляр и б) изменяем порог

П = П - Ш.

Понятно, что П будет колебаться около некоторого равновесного уровня, только если на одно событие (1) будет приходиться 999 событий (2). Не понятно только, как выбрать Ш. И должен ли он быть постоянным в ходе работы алгоритма...

(Упссс, знаки попутал, теперь правильно.)

наверное, полезна будет какая-то зависимость Ш от текущих значений (Q-П), потому что если всё время Ш много меньше, чем Abs(Q-П), то производимая коррекция порога мало влияет на его работу...

наверное, правильно, но это -- линейно растущие Q в потоке -- какой-то вычурный пример.

конкретно в моем проекте (в нынешнем его состоянии) в самом деле можно не только "второй проход по тому же потоку" сделать, но и любой экземпляр в потоке отдельно воспроизвести повторно по его "ключу"(*). Так что я продолжаю обсуждать постановку задачи более общую (чем в моём проекте).

____________________
* -- типа, вот так https://www.sql.ru/forum/1335743/o-razvorachivanii-dlinnogo-celogo-v-nabor-iz-100-psevdosluchaynyh-deystvitelnyh

Имя пользователя1, допуски приемлемы, только я так и не понял, как выбрать Ш.

mayton, в виде графика ... у которого что отложено по осям X и Y? И как построен набор отображаемых (в виде точек) элементов -- график всех значений Q, типа, всего "миллиарда"?