Хороший отсортированный список для Java

Question

Я ищу хороший отсортированный список для Java. Погуглите, дайте мне несколько советов по использованию TreeSet / TreeMap. Но в этих компонентах отсутствует одно: произвольный доступ к элементу в наборе. Например, я хочу получить доступ к n-му элементу в отсортированном наборе, но с TreeSet я должен перебрать другие n-1 элементы, прежде чем смогу туда добраться. Это было бы пустой тратой, поскольку в моем наборе было бы до нескольких тысяч элементов.

По сути, я ищу что-то похожее на отсортированный список в .NET, с возможностью быстрого добавления элемента, быстрого удаления элемента и произвольного доступа к любому элементу в списке.

Этот сортированный список реализован где-то? Спасибо.

Отредактированный

Мой интерес к SortedList связан с этими проблемами: Мне нужно вести список из многих тысяч объектов (и может вырасти до многих сотен тысяч). Эти объекты будут сохранены в базе данных. Я хочу случайным образом выбрать несколько десятков элементов из всего списка. Итак, я попытался сохранить отдельный список в памяти, который содержит первичные ключи (длинные числа) всех объектов. Мне нужно добавить / удалить ключи из списка, когда объект добавлен / удален из базы данных. Я сейчас использую ArrayList, но боюсь, что ArrayList не подойдет, когда число записей возрастет. (Представьте, что вам нужно повторять несколько сотен тысяч элементов каждый раз, когда объект удаляется из базы данных). Назад к тому времени, когда я занимался программированием на .NET, тогда я использовал бы отсортированный список (List - это класс .NET, который после того, как свойство Sorted установило значение true, будет поддерживать порядок своего элемента и обеспечивать бинарный поиск, который поможет удалить / вставить элемент очень быстрый). Я надеюсь, что смогу найти что-то похожее из java BCL, но, к сожалению, я не нашел хорошего соответствия.

Answer 1

Похоже, вам нужна структура списка с очень быстрым удалением и произвольным доступом по индексу (не по ключу) раз. ArrayList дает вам последнее, а HashMap или TreeMap дает вам первое.

Существует одна структура в коллекциях Apache Commons, которая может быть тем, что вы ищете, 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 для поиска и вставки элементов списка
• Возможность использовать собственный компаратор для сортировки списка

Некоторые заметки:

• Этот отсортированный список не синхронизирован , поскольку он наследуется от java.util.ArrayList. Используйте Collections.synchronizedList, если вам это нужно (подробности см. В документации по Java для java.util.ArrayList).
• Первоначальное решение основывалось на java.util.LinkedList. Для повышения производительности, особенно для поиска точки вставки (комментарий Логана) и более быстрых операций get (https://dzone.com/articles/arraylist-vs-linkedlist-vs), это было изменено на java.util.ArrayList.

Answer 3

Фыонг:

Сортировка 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);
    }
}   

Так как вам редко требуется сортировка, согласно вашей формулировке проблемы, это, вероятно, больше эффективнее, чем нужно.

Answer 4

Декоратор SortedList из Java Happy Libraries можно использовать для украшения TreeList из коллекций Apache. Это привело бы к созданию нового списка, производительность которого сопоставима с TreeSet. https://sourceforge.net/p/happy-guys/wiki/Sorted%20List/

Answer 5

В зависимости от того, как вы используете список, может стоить использовать TreeSet, а затем использовать метод toArray () в конце. У меня был случай, когда мне был нужен отсортированный список, и я обнаружил, что TreeSet + toArray () намного быстрее, чем добавление в массив и сортировка слиянием в конце.

Answer 6

Чтобы проверить эффективность более раннего 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.");
    }

}

Оказывается, это примерно в два раза быстрее! Я думаю, что это из-за медленного получения SortedLinkList - что делает его плохим выбором для списка.

Сравненное время для того же случайного списка:

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

Кажется, glazedlists.SortedList действительно быстро ...

Answer 7

Как правило, вы не можете осуществлять поиск по постоянному времени и регистрировать время удаления / вставки, но если вас устраивает поиск по времени журнала, вы можете использовать SortedList.

Не уверен, что вы будете доверять моему кодированию, но я недавно написал реализацию SortedList на Java, которую вы можете загрузить с http://www.scottlogic.co.uk/2010/12/sorted_lists_in_java/. Эта реализация позволяет вам искать i-й элемент списка в журнале время.

Answer 8

Как насчет использования HashMap? Вставка, удаление и извлечение - все операции O (1). Если вы хотите отсортировать все, вы можете получить список значений на карте и запустить их с помощью алгоритма сортировки O (n log n).

редактировать

Быстрый поиск нашел LinkedHashMap , который поддерживает порядок вставки ваших ключей. Это не точное решение, но оно довольно близко.

Answer 9

GlazedLists имеет очень, очень хорошую реализацию отсортированного списка