java - 从大型数组中采样数据

Question

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

每个对象都有一个与其关联的适应度变量( double 型)。我没有一个数字来确定一个对象是否适合，我只想要一组中最不适合的。

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

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

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

Answer 1

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

找到第 k 个最小元素(快速选择或 5 的中位数)，其中关键是您的适应度。我们称之为p。这可以在 O(n) 内完成。

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

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