Ответ 1

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

В коллекциях Apache Commons есть одна структура, которая может быть тем, что вы ищете, TreeList. JavaDoc указывает, что он оптимизирован для быстрой вставки и удаления по любому индексу в списке. Если вам также нужны дженерики, это не поможет вам.

Ответ 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.

Ответ 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);
    }
}   

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

изменить

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

Ответ 8

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

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

Ответ 9

Чтобы проверить эффективность ранее созданного Конрада Холла, я сделал быстрое сравнение с тем, что, как я думал, было бы медленным способом сделать это:

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 slow get - что делает его не лучшим выбором для списка.

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

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

Кажется, что глазурованные списки. SortedList очень быстро...