Данные выборки из большого массива

Question

В основном у меня есть очень большой массив объектов, и мне нужно удалить 10% объектов с наименьшей степенью точности.

Каждый объект имеет связанную с ним переменную пригодности (двойную). У меня нет числа, которое определяет, подходит ли объект, я просто хочу, чтобы он был наименее приспособлен.

Каков наилучший способ получения (выборки) наименее подходящих объектов?

Один способ может быть случайным образом выбирает путь 20%, сортирует данные, а затем удаляет 10%. Но я думаю, что это не очень умный способ сделать это.

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

Answer 1

Пусть k будет yourCollection.length() * 0.1 и n = yourCollection.length().

Найти k-й самый маленький элемент (QuickSelect или Median of 5), где ключ - ваш фитнес. Назовем это p. Это можно сделать в O(n).

Затем пройдите через коллекцию и удалите все предметы с помощью фитнеса меньше, чем p.fitness. У нас есть решение O(n).

Или вы можете создать кучу в O(n) с key=fitness и удалить k элементов из него в O(k * log(n)).