一份适用于Java的良好排序列表

Question

我正在寻找一种适用于Java的好的排序列表。浏览网络时，我发现了使用TreeSet/TreeMap的一些提示。但这些组件缺少一件事：对集合中的元素进行随机访问。

例如，我想要访问排序集合中的第n个元素，但使用TreeSet时，我必须在到达那里之前迭代其他n-1个元素。这将是一种浪费，因为我的集合可能有多达数千个元素。

基本上，我正在寻找类似于.NET中的排序列表，具有快速添加和删除元素的能力，并且可以随机访问列表中的任何元素。

是否有实现这种排序列表的地方？

编辑：

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

- Phương Nguyễn

---

TreeSet提供的是对数级别的查找（log(n)），而非线性的查找。 - Stefan Kendall

TreeSet提供了一个log(n)的contains测试（其中n是集合大小），但没有简便地访问第i个元素（其中i是任意索引）的方法。 - Christian Semrau

不，除非性能要求需要，否则没有理由使用更快的解决方案。如果一个解决方案很直观，就使用它。此外，如果你在接口而不是实现上工作，你可以随时切换实现以获得性能优势。现在已经不是1985年了；排序40,000个元素不再是性能负担。 - Stefan Kendall

我不确定.NET是否有这个功能。List没有Sort或Sorted属性。它确实有一个Sort方法。但是这个方法的行为与您在此处要求的不同（这与Java的Collections.sort方法没有区别）。即使在.NET中，保持排序列表也不能提高删除时间。 - Kevin Brock

你所接受的答案与排序列表无关。你真的应该更新你的问题以反映这一点。当我阅读TreeList文档并发现TreeList没有排序时，这让我感到困惑。 - Petriborg

Answer 1

看起来你需要一个列表结构，要求能够快速删除和通过索引（而不是关键字）进行随机访问。 ArrayList 能够实现后者，而 HashMap 或 TreeMap 则能够实现前者。

在 Apache Commons Collections 中有一个可能符合你需求的数据结构，它叫做 TreeList。JavaDoc 明确说明它被优化用于快速在列表中的任何位置插入或删除元素。如果你还需要泛型支持，那么这个结构就无法帮助你了。

- Kevin Brock

---

对于一个实现来说，如果它能够比Java API中的集合更加高效，那么就应该给予加分。 - Stefan Kendall

我认为链表不适合这里，因为它必须迭代才能到达具有特定索引的元素。但是添加/删除速度更快。 - Kanagavelu Sugumar

@ Sugumar TreeList既不是LinkedList，也不具有类似于链表的行为（请参阅提供两者之间性能比较的链接），因此我不理解您的评论。尽管如此，您说得对，对于问题所要求的内容，LinkedList并不合适。 - Kevin Brock

TreeList 与 LinkedList 相似，元素分散且使用更多指针，因为它似乎在内部使用 AVL 节点作为实现，请参见：http://grepcode.com/file/repo1.maven.org/maven2/org.apache.openjpa/openjpa-all/2.0.0/org/apache/commons/collections/list/TreeList.java。你可以看到，一些操作并不是非常优化的。所以 https://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/ 在这里也适用。这就是为什么你可能只应该使用 ArrayList 中的所有内容。 - Mladen Adamovic

Answer 2

这是我正在使用的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);
    }
}

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

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

一些注意事项：

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

- Konrad Holl

---

为什么要扩展LinkedList？由于这不是随机访问集合，因此二分查找的时间复杂度将为O(n)。 - Anatoliy

我猜addAll方法可以稍微改进一下 - 现在它的复杂度是O(N^2)，但是如果你能够批量无序地插入所有元素，然后再通过Collections.sort()进行排序，你就可以获得更好的复杂度，比如O(N logN + 2N)。顺便说一句 - 我觉得LinkedList比ArrayList更好，因为它的增长成本较低。 - Anatoliy

@Anatoliy 很久没有回复你了 - 我喜欢你的评论。我修改了addAll方法，像你建议的那样使用super.addAll。我添加了一个if语句，用于选择哪个方法更快 - addAll还是多个add调用。不过，4只是一个猜测，没有进行测试。 - Konrad Holl

Collectinos.binarySearch() 在链表上的时间复杂度为O(n)，因此您的添加操作并不比循环查找插入点更有效。相同的批评也适用于 contains 方法。通过将 LinkedList 替换为 ArrayList，这样做可以更快地实现。 - Logan Pickup

使用 ArrayList 的事件，恐怕不是很快。关于 addAll，我只会调用 super 然后使用 Collection#sort，因为它使用 TimSort，可以识别部分排序的集合。更糟糕的是：您正在扩展 ArrayList 并违反其约定（例如，add 被定义为添加到列表末尾）。而 ArrayList 违反了您的契约，因为有 add(int index, E element)，这会破坏排序。 - maaartinus

Answer 3

Phuong:

排序 40,000 个随机数：

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);
    }
}   

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

- Stefan Kendall

---

嗨Stefan： 感谢你的基准测试。但实际上，我真正想要的是快速删除的排序列表。我甚至不介意对列表进行排序，因为我无论如何都是随机选择其中的元素。我对排序列表感兴趣是因为排序列表在删除/插入元素时性能非常好。现在我正在处理几千个数据，但我希望我的数据能增长到数十万个。如果没有真正的排序列表，那么我认为我无法很好地处理它。 - Phương Nguyễn

@PhươngNguyễn 我认为LinkedList在删除/插入方面的性能会比SortedList好。 - Kanagavelu Sugumar

Answer 4

根据使用列表的方式，值得使用TreeSet，然后在最后使用toArray()方法。我曾经遇到过需要排序列表的情况，发现TreeSet + toArray()比在最后添加到数组并进行合并排序要快得多。

- Brendan Long

---

@Long：谢谢。你的解决方案非常好。只是当变更集很大时，toArray()方法会被调用多次。例如，如果我的集合从4000增长到4100，那么我需要调用100次toArray()方法，每次迭代超过4000个项目，导致额外的40万次迭代。我正在寻找一种能够消除这些额外迭代的解决方案。但是，就像Stefan Kendall试图传达的那样，这可能是过早优化。 - Phương Nguyễn

你说得没错，每次添加东西都不想这样做。我的意思是，如果你知道你总是会批量添加，那么TreeSet + toArray()可能适合你。 - Brendan Long

Answer 5

Java Happy Libraries中的SortedList修饰器可以用来修饰Apache Collections中的TreeList。这将产生一个性能与TreeSet相当的新列表。 https://sourceforge.net/p/happy-guys/wiki/Sorted%20List/

- thinker

---

这个组合太棒了！ - KIC

Answer 6

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

- Kevin Day

---

SortedList 是 log(n) 的查找速度，就像 TreeSet。 - Stefan Kendall

与TreeSet不同，SortedList允许对任何给定索引进行随机访问，因此似乎更合适。我不知道有任何排序列表结构允许O(log(n))插入和O(1)索引访问。 - Christian Semrau

嗯，看起来像是一个桌面GUI组件。有没有关于这个的精简库？ - Phương Nguyễn

GlazedLists绝对不是GUI组件。试试看吧。至于精简库（大概是只有排序功能的东西？）并没有。这种东西需要付出大量的工作，而且仅为了处理一种类型的列表并不划算。整个GL方法非常优雅。 - Kevin Day

哈哈 - 现在我看一下TreeList（来自Commons）的javadocs，看起来他们已经完成了工作并将其保留在单个类中。GL仍然是实时和声明性列表的绝佳选择 - 我强烈推荐使用它。 - Kevin Day

Answer 7

关于使用 HashMap 怎么样？插入、删除和检索都是 O(1) 操作。如果您想对所有内容进行排序，可以获取 Map 中的值列表，并通过 O(n log n) 的排序算法运行它们。 编辑 快速搜索发现 LinkedHashMap，它维护键的插入顺序。虽然不是完美解决方案，但相当接近。

- Dave DeLong

---

嗯，我没看到如何使用LinkedHashMap进行随机访问。 - Phương Nguyễn

Answer 8

通常情况下，你不能同时实现常数时间的查找和对数时间的删除/插入操作，但如果你可以接受对数时间的查找，那么你可以使用 SortedList。

不确定你是否信任我的编码能力，但我最近在 Java 中编写了一个 SortedList 实现，你可以从 http://www.scottlogic.co.uk/2010/12/sorted_lists_in_java/ 下载。这个实现允许你在对数时间内查找列表中的第 i 个元素。

- Mark Rhodes

---

此实现现已稳定并得到改进。 - Mark Rhodes

Answer 9

为了测试Konrad Holl之前的答案的效率，我进行了快速比较，与我认为的缓慢方法进行对比：

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.");
    }

}

结果显示它大约快了两倍！我认为这是由于SortedLinkList的获取速度慢，这使得它不适合用作列表。

对相同随机列表进行比较所需时间：

- SortedLinkList：15731.460 - SortedList：6895.494 - ca.odell.glazedlists.SortedList：712.460 - org.apache.commons.collections4.TreeList：3226.546

看起来glazedlists.SortedList真的很快...

- EarlB

---

它比Konrad Holl的答案更快，因为另一个答案使用LinkedList作为其基础列表，并在其上执行几个非常慢的操作（特别是binarySearch，在链表上速度较慢，除非比link遍历要费时得多）。 - Logan Pickup

Answer 10

你不需要排序过的列表。你根本不需要排序。

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

但不是立即进行，删除可以等待。使用一个包含所有活动对象ID以及最多一定比例的已删除对象的ArrayList。使用单独的HashSet来跟踪已删除的对象。

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

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

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));
}

为了维护数据，可以做如下操作

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();
    }
}

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

delete确保mostlyAliveIds中被删除的ID不超过10％。当发生这种情况时，它们会在一次扫描中全部删除（我没有检查JDK源代码，但我希望他们做得对），然后继续进行。

如果死亡ID不超过10％，那么selectOne的开销平均不超过10％。

我相信它比任何排序都要快，因为摊销复杂度为O(n)。

- maaartinus