java - 通过将排序后的集合添加到 SortedSet 来重新排序其成本有多高

Question

这更多的是出于好奇，因为我从未注意到性能问题。假定设置大小介于 1-1000 之间。这是一个案例:

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 )。

Answer 1

当您向 TreeSet 添加 n 个项目时，即使项目是有序的，您也不能假设时间复杂度优于 O(n*log₂n)。更大的开销来自常数因子，因为集合需要分配 n 个树节点来容纳您的数据。

如果您的集合已预先排序，假设您不需要修改结果，则最好将其存储在普通列表中。对排序列表进行二分搜索的时间复杂度为 O(log₂n)，而在读取时存储它实际上没有任何开销。读入 TreeSet 的唯一好处是可以进行 O(log₂n) 次插入和删除。