一个很好的 Java 排序列表

A good Sorted List for Java

提问by Ph??ng Nguy?n

I'm looking for a good sorted list for java. Googling around give me some hints about using TreeSet/TreeMap. But these components is lack of one thing: random access to an element in the set. For example, I want to access nth element in the sorted set, but with TreeSet, I must iterate over other n-1 elements before I can get there. It would be a waste since I would have upto several thousands elements in my Set.

我正在寻找一个很好的 java 排序列表。谷歌搜索给我一些关于使用 TreeSet/TreeMap 的提示。但是这些组件缺少一件事：随机访问集合中的元素。例如，我想访问排序集中的第 n 个元素，但是使用 TreeSet，我必须遍历其他 n-1 个元素才能到达那里。这将是一种浪费，因为我的 Set 中将有多达数千个元素。

Basically, I'm looking for some thing similar to a sorted list in .NET, with ability to add element fast, remove element fast, and have random access to any element in the list.

基本上，我正在寻找一些类似于 .NET 中的排序列表的东西，能够快速添加元素、快速删除元素以及随机访问列表中的任何元素。

Has this kind of sorted list implemented somewhere? Thanks.

这种排序列表是否在某处实现？谢谢。

Edited

已编辑

My interest in SortedList grows out of this problems: I need to maintains a list of many thousands object (and can grow up to many hundred of thousands). These objects will be persisted to database. I want to randomly select few dozens of element from the whole list. So, I tried to maintain a separated on-memory list that contains the primary keys (Long numbers) of all objects. I need to add/remove keys from the list when object is added / removed from database. I'm using an ArrayList right now but I'm afraid ArrayList would not suit it when the number of records grows. (Imagine you have to iterate over several hundred thousands of elements every time an object is removed from database). Back to the time when I did .NET programming, then I would use a sorted List (List is a .NET class that once Sorted property set to true, will maintain order of its element, and provide binary search that help remove/insert element very quick). I'm hoping that I can find some thing similar from java BCL but unluckily, I didn't find a good match.

我对 SortedList 的兴趣源于这个问题：我需要维护一个包含数千个对象的列表（并且可以增长到数十万个）。这些对象将被持久化到数据库中。我想从整个列表中随机选择几十个元素。因此，我尝试维护一个单独的内存列表，其中包含所有对象的主键（长数字）。当对象从数据库中添加/删除时，我需要从列表中添加/删除键。我现在正在使用 ArrayList，但是当记录数量增加时，我担心 ArrayList 不适合它。（想象一下，每次从数据库中删除一个对象时，您都必须迭代数十万个元素）。回到我做 .NET 编程的时候，然后我会使用一个排序列表（List 是一个 .NET 类，一旦 Sorted 属性设置为 true，将保持其元素的顺序，并提供有助于快速删除/插入元素的二进制搜索）。我希望我能从 java BCL 中找到一些类似的东西，但不幸的是，我没有找到很好的匹配。

采纳答案by Kevin Brock

It seems that you want a list structure with very fast removal and random access by index(not by key) times. An ArrayListgives you the latter and a HashMapor TreeMapgive you the former.

似乎您想要一个具有非常快速删除和按索引（而不是按键）时间随机访问的列表结构。AnArrayList给你后者，a HashMaporTreeMap给你前者。

There is one structure in Apache Commons Collections that may be what you are looking for, the TreeList. The JavaDoc specifies that it is optimized for quick insertion and removal at any index in the list. If you also need generics though, this will not help you.

Apache Commons Collections 中有一种结构可能正是您要查找的，即TreeList。JavaDoc 指定它已针对在列表中的任何索引处快速插入和删除进行了优化。但是，如果您还需要泛型，这对您没有帮助。

回答by Kevin Day

GlazedListshas a very, very good sorted list implementation

GlazedLists有一个非常非常好的排序列表实现

回答by Dave DeLong

What about using a HashMap? Insertion, deletion, and retrieval are all O(1) operations. If you wanted to sort everything, you could grab a List of the values in the Map and run them through an O(n log n) sorting algorithm.

使用一个HashMap怎么样？插入、删除和检索都是 O(1) 操作。如果您想对所有内容进行排序，您可以获取 Map 中的值列表，并通过 O(n log n) 排序算法运行它们。

edit

编辑

A quick search has found LinkedHashMap, which maintains insertion order of your keys. It's not an exact solution, but it's pretty close.

快速搜索找到了LinkedHashMap，它维护您的键的插入顺序。这不是一个精确的解决方案，但它非常接近。

回答by Brendan Long

Depending on how you're using the list, it may be worth it to use a TreeSet and then use the toArray() method at the end. I had a case where I needed a sorted list, and I found that the TreeSet + toArray() was much faster than adding to an array and merge sorting at the end.

根据您使用列表的方式，使用 TreeSet 然后在最后使用 toArray() 方法可能是值得的。我有一个需要排序列表的情况，我发现 TreeSet + toArray() 比添加到数组并在最后合并排序要快得多。

回答by Stefan Kendall

Phuong:

芳：

Sorting 40,000 random numbers:

对 40,000 个随机数进行排序：

0.022 seconds

0.022 秒

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;


public class test
{
    public static void main(String[] args)
    {
        List<Integer> nums = new ArrayList<Integer>();
        Random rand = new Random();
        for( int i = 0; i < 40000; i++ )
        {
            nums.add( rand.nextInt(Integer.MAX_VALUE) );
        }

        long start = System.nanoTime();
        Collections.sort(nums);
        long end = System.nanoTime();

        System.out.println((end-start)/1e9);
    }
}   

Since you rarely need sorting, as per your problem statement, this is probably moreefficient than it needs to be.

由于您很少需要排序，根据您的问题陈述，这可能比它需要的更有效。

回答by Mark Rhodes

Generally you can't have constant time look up and log time deletions/insertions, but if you're happy with log time look ups then you can use a SortedList.

通常，您不能进行固定时间查找和记录时间删除/插入，但是如果您对记录时间查找感到满意，那么您可以使用 SortedList。

Not sure if you'll trust my coding but I recently wrote a SortedList implementation in Java, which you can download from http://www.scottlogic.co.uk/2010/12/sorted_lists_in_java/. This implementation allows you to look up the i-th element of the list in log time.

不确定您是否会相信我的编码，但我最近用 Java 编写了一个 SortedList 实现，您可以从http://www.scottlogic.co.uk/2010/12/sorted_lists_in_java/下载。此实现允许您在日志时间查找列表的第 i 个元素。

回答by Konrad Holl

This is the SortedList implementation I am using. Maybe this helps with your problem:

这是我正在使用的 SortedList 实现。也许这有助于解决您的问题：

import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
/**
 * This class is a List implementation which sorts the elements using the
 * comparator specified when constructing a new instance.
 * 
 * @param <T>
 */
public class SortedList<T> extends ArrayList<T> {
    /**
     * Needed for serialization.
     */
    private static final long serialVersionUID = 1L;
    /**
     * Comparator used to sort the list.
     */
    private Comparator<? super T> comparator = null;
    /**
     * Construct a new instance with the list elements sorted in their
     * {@link java.lang.Comparable} natural ordering.
     */
    public SortedList() {
    }
    /**
     * Construct a new instance using the given comparator.
     * 
     * @param comparator
     */
    public SortedList(Comparator<? super T> comparator) {
        this.comparator = comparator;
    }
    /**
     * Construct a new instance containing the elements of the specified
     * collection with the list elements sorted in their
     * {@link java.lang.Comparable} natural ordering.
     * 
     * @param collection
     */
    public SortedList(Collection<? extends T> collection) {
        addAll(collection);
    }
    /**
     * Construct a new instance containing the elements of the specified
     * collection with the list elements sorted using the given comparator.
     * 
     * @param collection
     * @param comparator
     */
    public SortedList(Collection<? extends T> collection, Comparator<? super T> comparator) {
        this(comparator);
        addAll(collection);
    }
    /**
     * Add a new entry to the list. The insertion point is calculated using the
     * comparator.
     * 
     * @param paramT
     * @return <code>true</code> if this collection changed as a result of the call.
     */
    @Override
    public boolean add(T paramT) {
        int initialSize = this.size();
        // Retrieves the position of an existing, equal element or the 
        // insertion position for new elements (negative).
        int insertionPoint = Collections.binarySearch(this, paramT, comparator);
        super.add((insertionPoint > -1) ? insertionPoint : (-insertionPoint) - 1, paramT);
        return (this.size() != initialSize);
    }
    /**
     * Adds all elements in the specified collection to the list. Each element
     * will be inserted at the correct position to keep the list sorted.
     * 
     * @param paramCollection
     * @return <code>true</code> if this collection changed as a result of the call.
     */
    @Override
    public boolean addAll(Collection<? extends T> paramCollection) {
        boolean result = false;
        if (paramCollection.size() > 4) {
            result = super.addAll(paramCollection);
            Collections.sort(this, comparator);
        }
        else {
            for (T paramT:paramCollection) {
                result |= add(paramT);
            }
        }
        return result;
    }
    /**
     * Check, if this list contains the given Element. This is faster than the
     * {@link #contains(Object)} method, since it is based on binary search.
     * 
     * @param paramT
     * @return <code>true</code>, if the element is contained in this list;
     * <code>false</code>, otherwise.
     */
    public boolean containsElement(T paramT) {
        return (Collections.binarySearch(this, paramT, comparator) > -1);
    }
    /**
     * @return The comparator used for sorting this list.
     */
    public Comparator<? super T> getComparator() {
        return comparator;
    }
    /**
     * Assign a new comparator and sort the list using this new comparator.
     * 
     * @param comparator
     */
    public void setComparator(Comparator<? super T> comparator) {
        this.comparator = comparator;
        Collections.sort(this, comparator);
    }
}

This solution is very flexible and uses existing Java functions:

此解决方案非常灵活，并使用现有的 Java 函数：

• Completely based on generics
• Uses java.util.Collections for finding and inserting list elements
• Option to use a custom Comparator for list sorting

• 完全基于泛型
• 使用 java.util.Collections 查找和插入列表元素
• 使用自定义比较器进行列表排序的选项

Some notes:

一些注意事项：

• This sorted list is not synchronizedsince it inherits from java.util.ArrayList. Use Collections.synchronizedListif you need this (refer to the Java documentation for java.util.ArrayListfor details).
• The initial solution was based on java.util.LinkedList. For better performance, specifically for finding the insertion point (Logan's comment) and quicker getoperations (https://dzone.com/articles/arraylist-vs-linkedlist-vs), this has been changed to java.util.ArrayList.

• 此排序列表不同步，因为它继承自java.util.ArrayList。Collections.synchronizedList如果需要，请使用（java.util.ArrayList有关详细信息，请参阅 Java 文档）。
• 最初的解决方案是基于java.util.LinkedList. 为了获得更好的性能，特别是为了找到插入点（Logan 的评论）和更快的获取操作（https://dzone.com/articles/arraylist-vs-linkedlist-vs），这已更改为java.util.ArrayList.

回答by thinker

SortedList decorator from Java Happy Libraries can be used to decorate TreeList from Apache Collections. That would produce a new list which performance is compareable to TreeSet. https://sourceforge.net/p/happy-guys/wiki/Sorted%20List/

Java Happy Libraries 中的 SortedList 装饰器可用于装饰 Apache Collections 中的 TreeList。这将产生一个新列表，其性能可与 TreeSet 进行比较。 https://sourceforge.net/p/happy-guys/wiki/Sorted%20List/

回答by EarlB

To test the efficiancy of earlier awnser by Konrad Holl, I did a quick comparison with what I thought would be the slow way of doing it:

为了测试 Konrad Holl 早期 awnser 的效率，我与我认为的慢速方法进行了快速比较：

package util.collections;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 *
 * @author Earl Bosch
 * @param <E> Comparable Element
 *
 */
public class SortedList<E extends Comparable> implements List<E> {

    /**
     * The list of elements
     */
    private final List<E> list = new ArrayList();

    public E first() {
        return list.get(0);
    }

    public E last() {
        return list.get(list.size() - 1);
    }

    public E mid() {
        return list.get(list.size() >>> 1);
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public boolean add(E e) {
        list.add(e);
        Collections.sort(list);
        return true;
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public boolean contains(Object obj) {
        return list.contains((E) obj);
    }

    @Override
    public Iterator<E> iterator() {
        return list.iterator();
    }

    @Override
    public Object[] toArray() {
        return list.toArray();
    }

    @Override
    public <T> T[] toArray(T[] arg0) {
        return list.toArray(arg0);
    }

    @Override
    public boolean remove(Object obj) {
        return list.remove((E) obj);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return list.containsAll(c);
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {

        list.addAll(c);
        Collections.sort(list);
        return true;
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return list.removeAll(c);
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return list.retainAll(c);
    }

    @Override
    public E get(int index) {
        return list.get(index);
    }

    @Override
    public E set(int index, E element) {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public void add(int index, E element) {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public E remove(int index) {
        return list.remove(index);
    }

    @Override
    public int indexOf(Object obj) {
        return list.indexOf((E) obj);
    }

    @Override
    public int lastIndexOf(Object obj) {
        return list.lastIndexOf((E) obj);
    }

    @Override
    public ListIterator<E> listIterator() {
        return list.listIterator();
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        return list.listIterator(index);
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        throw new UnsupportedOperationException("Not supported.");
    }

}

Turns out its about twice as fast! I think its because of SortedLinkList slow get - which make's it not a good choice for a list.

结果它大约快两倍！我认为这是因为 SortedLinkList 获取缓慢 - 这使得它不是列表的好选择。

Compared times for same random list:

相同随机列表的比较时间：

• SortedLinkList : 15731.460
• SortedList : 6895.494
• ca.odell.glazedlists.SortedList : 712.460
• org.apache.commons.collections4.TreeList : 3226.546

• 排序链接列表：15731.460
• 排序列表：6895.494
• ca.odell.glazedlists.SortedList : 712.460
• org.apache.commons.collections4.TreeList：3226.546

Seems glazedlists.SortedList is really fast...

似乎glazedlists.SortedList 真的很快......

回答by maaartinus

You need no sorted list. You need no sorting at all.

您不需要排序列表。你根本不需要排序。

I need to add/remove keys from the list when object is added / removed from database.

当对象从数据库中添加/删除时，我需要从列表中添加/删除键。

But not immediately, the removal can wait. Use an ArrayListcontaining the ID's all alive objects plus at most some bounded percentage of deleted objects. Use a separate HashSetto keep track of deleted objects.

但不是立即，删除可以等待。使用ArrayList包含 ID 的所有活动对象加上最多某些有限百分比的已删除对象。使用单独的HashSet来跟踪已删除的对象。

private List<ID> mostlyAliveIds = new ArrayList<>();
private Set<ID> deletedIds = new HashSet<>();

I want to randomly select few dozens of element from the whole list.

我想从整个列表中随机选择几十个元素。

ID selectOne(Random random) {
    checkState(deletedIds.size() < mostlyAliveIds.size());
    while (true) {
        int index = random.nextInt(mostlyAliveIds.size());
        ID id = mostlyAliveIds.get(index);
        if (!deletedIds.contains(ID)) return ID;
    }
}

Set<ID> selectSome(Random random, int count) {
    checkArgument(deletedIds.size() <= mostlyAliveIds.size() - count);
    Set<ID> result = new HashSet<>();
    while (result.size() < count) result.add(selectOne(random));
}

For maintaining the data, do something like

为了维护数据，请执行以下操作

void insert(ID id) {
    if (!deletedIds.remove(id)) mostlyAliveIds.add(ID);
} 

void delete(ID id) {
    if (!deletedIds.add(id)) {
         throw new ImpossibleException("Deleting a deleted element);
    }
    if (deletedIds.size() > 0.1 * mostlyAliveIds.size()) {
        mostlyAliveIds.removeAll(deletedIds);
        deletedIds.clear();
    }
}

The only tricky part is the insertwhich has to check if an already deleted ID was resurrected.

唯一棘手的部分是insert必须检查已删除的 ID 是否复活。

The deleteensures that no more than 10% of elements in mostlyAliveIdsare deleted IDs. When this happens, they get all removed in one sweep (I didn't check the JDK sources, but I hope, they do it right) and the show goes on.

在delete确保了在元件的不超过10％mostlyAliveIds被删除的ID。发生这种情况时，它们会一扫而空（我没有检查 JDK 源代码，但我希望它们做得对）并且节目继续进行。

With no more than 10% of dead IDs, the overhead of selectOneis no more than 10% on the average.

不超过 10% 的死 ID，selectOne平均开销不超过 10%。

I'm pretty sure that it's faster than any sorting as the amortized complexity is O(n).

我很确定它比任何排序都快，因为摊销复杂度是O(n)。