Is it better to use a TreeSet or ArrayList when us

问题:

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?

Using TreeSet

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

Using ArrayList

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

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.

回答1:

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

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

回答2:

Java API contains numerous Collection and Map implementations so it might be confusing to figure out which one to use. Here is a quick flowchart that might help with choosing from the most common implementations

回答3:

If you only sort once, then the ArrayList is an obvious winner. The TreeSet is better if you add or remove items often as sorting a list again and again would be slow.

Note also that all tree structures need more memory and memory access indirection which makes them slower.

---

If case of medium sized lists, which change rather frequently by a single element, the fastest solution might be using ArrayList and inserting into the proper position (obviously assuming the arrays get sorted initially).

You'd need to determine the insert position via Arrays.binarySearch and insert or remove. Actually, I would't do it, unless the performance were really critical and a benchmark would show it helps. It gets slow when the list get really big and the gain is limited as Java uses TimSort, which is optimized for such a case.

---

As pointed in a comment, assuring that the Comparator returns different values is sometimes non-trivial. Fortunately, there's Guava's Ordering#arbitrary, which solves the problem if you don't need to be compatible with equals. In case you do, a similar method can be written (I'm sure I could find it somewhere if requested).