它是更好地使用自定义比较时使用TreeSet中或ArrayList的 [英] Is it better to use a TreeSet or ArrayList when using a custom comparator

问题描述

我实现了一个曲线图。
欲顶点的给定子集相对于它们度进行排序。
因此，我写了一个名为自定义比较 DegreeComparator 。

I have implemented a graph. I want to sort a given subset of vertices with respect to their degrees. Therefore, I've written a custom comparator named DegreeComparator.

private class DegreeComparator implements Comparator<Integer>
{
    @Override
    public int compare(Integer arg0, Integer arg1) 
    {
        if(adj[arg1].size() == adj[arg0].size()) return arg1 - arg0;
        else return adj[arg1].size() - adj[arg0].size());
    }

}

因此​​，其中下面的一个更有效？

So, which one of the below is more efficient?

是 TreeSet的

Using TreeSet

public Collection<Integer> sort(Collection<Integer> unsorted)
{
    Set<Integer> sorted = new TreeSet<Integer>(new DegreeComparator());
    sorted.addAll(unsorted);
    return sorted;
}

是的ArrayList

Using ArrayList

Collections.sort(unsorted, new DegreeComparator());

注意，第二个方法是不是一个函数，而是一个单行code。

Notice that the second approach is not a function, but a one-line code.

直观地说，我宁愿选择第二个。但我不知道这是否是更有效的。

Intuitively, I'd rather choose the second one. But I'm not sure if it is more efficient.

推荐答案

一个TreeSet的是一个Set。它删除重复（具有相同程度的元素）。因此，无论是不等价的。

A TreeSet is a Set. It removes duplicates (elements with the same degree). So both aren't equivalent.

无论如何，如果你想要自然的是一个排序列表，然后对列表进行排序。这将工作集合是否具有重复或没有，即使有相同的复杂性（为O（n *的log（n））用作填充TreeSet中，它可能是快（因为它只是在一个阵列移动元素，而不必创建大量树节点）。

Anyway, if what you want naturally is a sorted list, then sort the list. This will work whether the collection has duplicates or not, and even if it has the same complexity (O(n*log(n)) as populating a TreeSet, it is probably faster (because it just has to move elements in an array, instead of having to create lots of tree nodes).

这篇关于它是更好地使用自定义比较时使用TreeSet中或ArrayList的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！