Хороший отсортированный список для Java
Я ищу хороший отсортированный список для Java. Погуглите, дайте мне несколько советов по использованию TreeSet/TreeMap. Но в этих компонентах отсутствует одно: произвольный доступ к элементу в наборе. Например, я хочу получить доступ к n-му элементу в отсортированном наборе, но с TreeSet я должен перебрать другие n-1 элементы, прежде чем смогу туда добраться. Это было бы пустой тратой, поскольку в моем наборе было бы до нескольких тысяч элементов.
По сути, я ищу что-то похожее на отсортированный список в.NET, с возможностью быстрого добавления элемента, быстрого удаления элемента и произвольного доступа к любому элементу в списке.
Этот сортированный список реализован где-то? Благодарю.
отредактированный
Мой интерес к SortedList растет из-за этой проблемы: мне нужно вести список из многих тысяч объектов (и может расти до многих сотен тысяч). Эти объекты будут сохранены в базе данных. Я хочу случайным образом выбрать несколько десятков элементов из всего списка. Итак, я попытался сохранить отдельный список в памяти, который содержит первичные ключи (длинные числа) всех объектов. Мне нужно добавить / удалить ключи из списка, когда объект добавлен / удален из базы данных. Я сейчас использую ArrayList, но боюсь, что ArrayList не подойдет, когда число записей возрастет. (Представьте, что вам нужно повторять несколько сотен тысяч элементов каждый раз, когда объект удаляется из базы данных). Назад к тому времени, когда я занимался программированием на.NET, тогда я использовал бы отсортированный список (List - это класс.NET, который после того, как свойство Sorted установило значение true, будет поддерживать порядок своего элемента и обеспечивать двоичный поиск, который поможет удалить / вставить элемент очень быстрый). Я надеюсь, что смогу найти что-то похожее из java BCL, но, к сожалению, я не нашел хорошего соответствия.
9 ответов
Кажется, вам нужна структура списка с очень быстрым удалением и произвольным доступом по индексу (а не по ключу). ArrayList дает вам последнее и HashMap или же TreeMap дать тебе первое.
Существует одна структура в коллекциях Apache Commons, которая может быть тем, что вы ищете, TreeList. JavaDoc указывает, что он оптимизирован для быстрой вставки и удаления по любому индексу в списке. Если вам также нужны дженерики, это вам не поможет.
Это реализация 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, Для повышения производительности, в частности, для поиска точки вставки (комментарий Логана) и ускорения операций get ( https://dzone.com/articles/arraylist-vs-linkedlist-vs), это значение было изменено наjava.util.ArrayList,
Фыонг:
Сортировка 40000 случайных чисел:
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);
}
}
Так как вам редко требуется сортировка, согласно вашей формулировке проблемы, она, вероятно, более эффективна, чем должна быть.
В зависимости от того, как вы используете список, может быть, стоит использовать TreeSet, а затем использовать метод toArray() в конце. У меня был случай, когда мне был нужен отсортированный список, и я обнаружил, что TreeSet + toArray() намного быстрее, чем добавление в массив и сортировка слиянием в конце.
Декоратор SortedList из Java Happy Libraries можно использовать для украшения TreeList из коллекций Apache. Это привело бы к созданию нового списка, производительность которого сопоставима с TreeSet. https://sourceforge.net/p/happy-guys/wiki/Sorted%20List/
GlazedLists имеет очень, очень хорошую реализацию отсортированного списка
Как правило, вы не можете иметь постоянное время поиска и записи времени удаления / вставки, но если вы довольны просмотром времени журнала, вы можете использовать SortedList.
Не уверен, что вы будете доверять моему кодированию, но я недавно написал реализацию SortedList на Java, которую вы можете скачать с http://www.scottlogic.co.uk/2010/12/sorted_lists_in_java/. Эта реализация позволяет вам искать i-й элемент списка во время регистрации.
Чтобы проверить эффективность более ранней версии Конрада Холла, я провел быстрое сравнение с тем, что, по моему мнению, было бы медленным способом сделать это:
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 действительно быстро...
Как насчет использования HashMap? Вставка, удаление и извлечение - все операции O(1). Если вы хотите отсортировать все, вы можете получить список значений на карте и запустить их с помощью алгоритма сортировки O(n log n).
редактировать
Быстрый поиск нашел LinkedHashMap, который поддерживает порядок вставки ваших ключей. Это не точное решение, но оно довольно близко.
Вам не нужен отсортированный список. Вам вообще не нужна сортировка.
Мне нужно добавить / удалить ключи из списка, когда объект добавляется / удаляется из базы данных.
Но не сразу, удаление может подождать. Используйте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 который должен проверить, был ли воскрешен уже удаленный идентификатор.
В delete гарантирует, что не более 10% элементов в mostlyAliveIds- удаленные идентификаторы. Когда это происходит, все они удаляются одним движением (я не проверял исходники JDK, но надеюсь, что они все делают правильно), и шоу продолжается.
При не более 10% мертвых идентификаторов накладные расходы selectOne в среднем не более 10%.
Я почти уверен, что это быстрее, чем любая сортировка, так как амортизированная сложность O(n).