一个很好的Java排序列表

Question

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

基本上,我正在寻找类似于.NET中的排序列表的东西,能够快速添加元素,快速删除元素,并且可以随机访问列表中的任何元素.

在某处实现了这种排序列表吗？谢谢.

编辑

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

Answer 1

您似乎希望列表结构具有非常快速的删除和按索引(而非按键)随机访问的时间.一个ArrayList给你后者和一个HashMap或TreeMap给你前者.

Apache Commons Collections中有一个结构可能是您正在寻找的结构,TreeList.JavaDoc指定它已针对列表中的任何索引进行快速插入和删除进行了优化.如果你也需要泛型,这对你没有帮助.

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查找和插入列表元素
• 可以选择使用自定义Comparator进行列表排序

一些说明:

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

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

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