通过将排序的集合添加到SortedSet来重新排序一个集合有多昂贵 [英] How expensive is it to resort a sorted collection by adding it to a SortedSet

问题描述

这更多是出于好奇，因为我从未注意到性能问题.假定设置的大小在1-1000之间.这是一种情况:

This is more of a curiosity, as I've never noticed a performance issue. Presume set size between 1-1000. Here's one case:

private static SortedSet<GrantedAuthority> sortAuthorities(
    final Collection<? extends GrantedAuthority> authorities ) {
    return authorities.stream()
        .filter( Objects::nonNull )
        .sorted( Comparator.nullsFirst( Comparator.comparing( GrantedAuthority::getAuthority ) ) )
        .collect( Collectors.toCollection( TreeSet::new ) );
}

，但是我遇到的更常见的情况是从已经排序的"SQL查询"中获取有序列表，然后将其放入SortedSet中.显然，如果我从未发现问题，这是过早的优化，我只是很好奇这会在微观层面造成什么样的开销(请注意:通常我为此使用TreeSet.)

but the more common case I run into would be getting an ordered list back from a "SQL query" that's already sorted, and then wanting to put it into SortedSet. Obviously this is premature optimization if I've never noticed a problem, I'm just curious as to what kind of overhead this causes on a micro level (note: usually I use a TreeSet for this).

推荐答案

将n个项目添加到TreeSet时，您不能假设时间复杂度要好于O(n * log ₂ n )，即使已订购商品.常量因子会带来更大的开销，因为集合需要分配n个树节点来容纳您的数据.

When you add n items to a TreeSet, you cannot assume the time complexity better than O(n*log₂n), even if the items are ordered. An even larger overhead comes from the constant factor, through, because the collection needs to allocate n tree nodes to accommodate your data.

如果您的收藏集已进行了预排序，则最好不要将其存储在普通列表中，前提是您无需修改​​结果.在排序列表os O(log ₂ n)上进行二进制搜索，而在读取时将其存储几乎没有开销.读TreeSet的唯一好处是O(log ₂ n)插入和删除的可能性.

If your collection comes pre-sorted, you will be better off storing it in a plain list, assuming that you do not need to modify the results. Binary search on a sorted list os O(log₂n), while there's virtually no overhead in storing it on read. The only benefit of reading into a TreeSet is the possibility of O(log₂n) insertions and deletions.

这篇关于通过将排序的集合添加到SortedSet来重新排序一个集合有多昂贵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！