获取集合中N个最小的[可比较]项目 [英] Get the N smallest [Comparable] items in a set
问题描述
我有一个未分类的对象集合[可比较]，是否有可能获得列表集合的子列表而无需调用sort？
我正在考虑使用有限容量进行SortedList的可能性，但这看起来不是正确的选择。
我可以很容易地写出来，但我想知道是否还有其他办法。
我无法修改现有集合的结构。
由于您不想调用 sort（），您似乎正在尝试避免 O（n log（n））运行时成本。 实际上是 O（n）时间内的一种方式 - 您可以使用选择算法。
在Guava库中有一些方法可以做到这一点（谷歌的核心Java库）;查看订购并查看：
-
public< E extends T>列表与LT E - 代替; Ordering.leastOf（Iterable iterable，int k） -
public< E extends T> ;列表与LT E - 代替; Ordering.greatestOf（Iterable iterable，int k）
这些是 k 最小值的列表。如果您不想使用整个Guava库，那么文档链接到源代码，我认为将方法移植到项目中应该很简单。
如果你不想偏离标准库太远，你总是可以使用像 TreeSet 这样的有序集，尽管这可以获得对数插入/删除时间而不是基于散列的 Set 的 O（1）性能良好，最终为 O（n log（n）） 到底。其他人提到使用堆。除非你使用 O（n log（n））运行时间。 29＃Comparison_of_theoretic_bounds_for_variantsrel =nofollow>发烧友堆变种。在GraphMaker中有一个斐波纳契堆实现如果你正在寻找其中的一个。
其中哪些有意义取决于你的项目，但我认为这涵盖了大多数选项。 / p>
I have an unsorted Collection of objects [that are comparable], is it possible to get a sub list of the collection of the list without having to call sort?
I was looking at the possibility of doing a SortedList with a limited capacity, but that didn't look like the right option.
I could easily write this, but I was wondering if there was another way.
I am not able to modify the existing collection's structure.
Since you don't want to call sort(), it seems like you are trying to avoid an O(n log(n)) runtime cost. There is actually a way to do that in O(n) time -- you can use a selection algorithm.
There are methods to do this in the Guava libraries (Google's core Java libraries); look in Ordering and check out:
public <E extends T> List<E> Ordering.leastOf(Iterable iterable, int k)public <E extends T> List<E> Ordering.greatestOf(Iterable iterable, int k)
These are implementations of quickselect, and since they're written generically, you could just call them on your Set and get a list of the k smallest things. If you don't want to use the entire Guava libraries, the docs link to the source code, and I think it should be straightforward to port the methods to your project.
If you don't want to deviate too far from the standard libraries, you can always use a sorted set like TreeSet, though this gets you logarithmic insert/remove time instead of the nice O(1) performance of the hash-based Set, and it ends up being O(n log(n)) in the end. Others have mentioned using heaps. This will also get you O(n log(n)) running time, unless you use some of the fancier heap variants. There's a fibonacci heap implementation in GraphMaker if you're looking for one of those.
Which of these makes sense really depends on your project, but I think that covers most of the options.
这篇关于获取集合中N个最小的[可比较]项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
