Java的一个很好的sorting列表
我正在寻找一个很好的javasorting列表。 Googling around给我一些关于使用TreeSet / TreeMap的提示。 但是这些组件缺less一件事：随机访问集合中的元素。 例如，我想访问有序集合中的第n个元素，但是使用TreeSet，我必须迭代其他n-1个元素才能到达那里。 这将是一个浪费，因为我会在我的设置达到几千元。
基本上，我正在寻找类似于.NET中的sorting列表的东西，能够快速添加元素，快速删除元素，并随机访问列表中的任何元素。
这种sorting列表是否在某处执行？ 谢谢。
编辑
我对SortedList的兴趣源于这个问题：我需要维护一个数千个对象的列表（并且可以长到几十万）。 这些对象将被保存到数据库中。 我想从整个列表中随机抽取几十个元素。 所以，我试图维护一个单独的内存列表，其中包含所有对象的主键（长数字）。 当从数据库添加/删除对象时，我需要从列表中添加/删除键。 我现在正在使用ArrayList，但是恐怕ArrayList在logging数量增长时不适合它。 （想象一下，每次从数据库中删除一个对象时，必须遍历数十万个元素）。 回到我编写.NET程序的时候，我会使用一个有序列表（List是一个.NET类，一旦Sorted属性设置为true，将维护其元素的顺序，并提供二进制search，帮助删除/插入元素很快）。 我希望能从java BCLfind类似的东西，但不幸的是，我没有find一个好的匹配。
看来你需要一个非常快速的删除和索引 （而不是按键）时间的随机访问列表结构。 一个ArrayList给你后者，一个HashMap或者TreeMap给你前者。
Apache Commons Collections中有一个结构可能就是你正在寻找的TreeList 。 JavaDoc指定它是为在列表中的任何索引处快速插入和删除而优化的。 如果你还需要generics，这不会帮助你。
这是我正在使用的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); } }
该解决scheme非常灵活，并使用现有的Javafunction：
- 完全基于generics
- 使用java.util.Collections查找和插入列表元素
- select使用自定义比较器进行列表sorting
一些说明：
- 这个sorting列表是不同步的，因为它从
java.util.ArrayListinheritance。 如果需要，可以使用Collections.synchronizedList（有关详细信息，请参阅java.util.ArrayList的Java文档）。 - 最初的解决scheme是基于
java.util.LinkedList。 为了获得更好的性能，特别是为了find插入点（Logan的注释）和更快的获取操作（ https://dzone.com/articles/arraylist-vs-linkedlist-vs ），这已经改为java.util.ArrayList。
PHUONG：
sorting40,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); } }
既然你很less需要sorting，根据你的问题陈述，这可能比它需要更有效率。
根据你如何使用列表，可能值得使用TreeSet，最后使用toArray（）方法。 我有一个情况，我需要一个sorting列表，我发现TreeSet + toArray（）比添加到数组和最后合并sorting要快得多。
Java Happy Libraries中的SortedList装饰器可用于装饰Apache集合中的TreeList。 这将产生一个新的列表，其性能可以与TreeSet进行比较。 https://sourceforge.net/p/happy-guys/wiki/Sorted%20List/
GlazedLists有非常非常好的sorting列表实现
怎么使用HashMap ？ 插入，删除和检索都是O（1）操作。 如果你想对所有东西进行sorting，你可以在Map中获取一个值列表，并通过O（n log n）sortingalgorithm运行它们。
编辑
快速search发现LinkedHashMap ，它维护您的密钥的插入顺序。 这不是一个确切的解决scheme，但它非常接近。
一般来说，你不能有恒定的时间查找和logging时间删除/插入，但如果你对日志时间查找感到满意，那么你可以使用SortedList。
不知道你是否会相信我的代码，但我最近写了一个Java的SortedList实现，你可以从http://www.scottlogic.co.uk/2010/12/sorted_lists_in_java/下载。; 这个实现允许你在日志时间里查找列表的第i个元素。
为了testing康拉德·霍尔早期的维修人员的效率，我做了一个快速的比较，我认为这是一个很慢的方法：
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速度慢 – 这使得它不是一个好的select。
相同的随机列表比较时间：
- SortedLinkList：15731.460
- SortedList：6895.494
- ca.odell.glazedlists.SortedList：712.460
- org.apache.commons.collections4.TreeList：3226.546
似乎glazedlists.SortedList真的很快…
