java - 从大数组中采样数据

Question

基本上我有一个非常大的对象数组，我需要删除 10% 的最不合适的对象。

每个对象都有一个与之关联的适应度变量（双精度）。我没有一个数字来确定一个对象是否合适，我只想要一堆中最不合适的。

检索（采样）最不适合的对象的最佳方法是什么？

一种方法是随机选择 20%，对数据进行排序，然后删除 10%。但我认为这不是一个非常聪明的方法。

另一种方法是始终保持数组排序，然后删除前 10%。但我认为这不是很好，因为在插入/更新时您必须始终对数组进行排序，这是一个很大的开销..

Answer 1

设 k 为yourCollection.length() * 0.1且n = yourCollection.length()。

找到第 k 个最小的元素（QuickSelect 或 5 的中位数），其中关键是您的适应度。让我们称之为p。这可以在O(n).

然后遍历集合，移除所有fitness小于p.fitness的item。我们有一个O(n)解决方案。

O(n)或者，您可以在其中创建一个堆key=fitness并从中删除k元素O(k * log(n))。