У меня очень большая коллекция объектов, и в идеале я хотел бы найти лучший x% из них по некоторой метрике (в моем практическом приложении x% - это маленький, скажем, 0.1%).Очевидное решение состоит в том, чтобы отсортировать их все по этой метрике и взять лучший x%.Но у меня есть следующие сложности:
- Вычисление метрики занимает довольно много времени, поэтому я не хочу делать это для всех объектов.
- Коллекция оченьбольшой, поэтому я не хочу хранить их все в памяти сразу.
Я хотел бы создать приближение к лучшим x%, соблюдая эти ограничения.
MyИдея состояла бы в том, чтобы создать буфер, который содержит до N из них, а затем вытянуть до N случайных объектов, вычисляя метрику для этих объектов, как я.Затем я освободил бы некоторые слоты буфера, приняв некоторые из буферизованных объектов как достаточно хорошие для моего приблизительного пула x%, и освободил бы больше слотов буфера, отклонив некоторые из буферизованных объектов как слишком плохие, чтобы их даже рассмотреть, и оставил остальные вбуфер для дальнейшего рассмотрения.Затем я бы нарисовал больше объектов из всей коллекции, чтобы заполнить свободные слоты.Повторяя этот цикл, я бы произвел приближение к лучшим x%.
Мой вопрос: есть ли теория о том, как сделать это оптимально?Я уже могу сделать это с помощью специальных правил, но мне хотелось бы получить некоторые рекомендации о том, как оптимально заполнить буфер и принять и отклонить кандидатов в нем.Может ли кто-нибудь указать мне на некоторые соответствующие теории, статьи или условия поиска?