Сортировка списка Java: есть ли способ сохранить список, который автоматически сортируется автоматически, например TreeMap?

Ответ 1

Вы можете изменить поведение ArrayList

List<MyType> list = new ArrayList<MyType>() {
    public boolean add(MyType mt) {
         super.add(mt);
         Collections.sort(list, comparator);
         return true;
    }
}; 

Примечание: PriorityQueue НЕ является списком, если вам было все равно, какой тип коллекции он был, самым простым было бы использовать TreeSet, который точно так же, как TreeMap, но является коллекцией. Единственное преимущество PriorityQueue состоит в том, чтобы разрешить дубликаты.

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

EDIT: многое зависит от того, что вам нужно для "списка". Я предлагаю вам написать оболочку List для ArrayList, LinkedList, PriorityQueue, TreeSet или одного из других отсортированных коллекций и реализовать методы, которые будут фактически использоваться. Таким образом, вы хорошо понимаете требования к коллекции, и можете убедиться, что она работает правильно для вас.

EDIT (2): Поскольку интерес к использованию binarySearch был так интересен.;)

List<MyType> list = new ArrayList<MyType>() {
    public boolean add(MyType mt) {
        int index = Collections.binarySearch(this, mt);
        if (index < 0) index = ~index;
        super.add(index, mt);
        return true;
    }
};

Ответ 2

Все предлагают PriorityQueue. Однако важно понимать, что если вы итерации над содержимым PriorityQueue, элементы не будут отсортированы в порядке сортировки. Вы гарантированно получите минимальный элемент из методов peek(), poll() и т.д.

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

Ответ 3

Комментарий

Вероятно, есть веская причина, что в JDK нет реализации SortedList. Я лично не могу придумать причину, чтобы иметь один автосортинг в JDK.

Это пахнет преждевременной оптимизацией. Если список не читается так часто, как он вставлен, то вы часто тратите циклы на сортировку без каких-либо причин. Сортировка прямо перед чтением была бы гораздо более реактивной и имела бы boolean где-то, указывающую, что список сортируется или не нужно сортировать перед чтением, было бы еще лучше.

Дело в том, что при перемещении списка с циклом Iterator или for each вы действительно заботитесь о порядке, поэтому вызов Collections.sort() перед тем, как любой итерационный код, вероятно, будет более результативным, чем попытка сохранить список отсортированным время при каждой вставке.

Существуют двусмысленности с List из-за дубликатов, как вы производите упорядочение дубликатов детерминистически? Существует SortedSet, и это имеет смысл из-за уникальности. Но сортировка List может иметь больше осложнений от побочных эффектов дубликатов и других ограничений, таких как создание каждого объекта Comparable или, как я показываю в своем коде, чтобы иметь Comparator, который может выполнять работу вместо этого.

Сортировка по .add()

Если у вас есть особая ситуация, когда будет полезно использовать автоматическую сортировку List, то одна вещь, которую вы можете сделать, - это подкласс класса a List и over-ride .add(), чтобы сделать Collections.sort(this, comparator), что вы переходите в пользовательский конструктор. Я использовал LinkedList вместо ArrayList по какой-либо причине, ArrayList - это упорядоченный порядок упорядочения List для начала. Он также имеет возможность .add() с индексом, который довольно бесполезен, если вы хотите постоянно сортировать List, который должен быть обработан каким-то образом, что, вероятно, будет менее идеальным. Согласно Джавадоку,

void    add(int index, Object element)

Вставляет указанный элемент в указанная позиция в этом списке (необязательная операция).

Так что это просто выбрасывание UnSupportedOperationException было бы приемлемым, или вы могли бы просто игнорировать index и делегировать на .add(Object element);, если вы документируете его в JavaDoc для этого метода.

Обычно, когда вы хотите много вложений/абстракций и сортировки, вы должны использовать LinkedList из-за более высоких характеристик производительности, учитывая использование "Список".

Вот краткий пример:

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

public class SortedList<E> extends LinkedList<E>
{
    private Comparator<E> comparator;

    public SortedList(final Comparator<E> comparator)
    {
        this.comparator = comparator;
    }

    /**
    * this ignores the index and delegates to .add() 
    * so it will be sorted into the correct place immediately.
    */
    @Override
    public void add(int index, Object element)
    {
        this.add(element);     
    }

    @Override
    public boolean add(final E e)
    {
        final boolean result = super.add(e);
        Collections.sort(this, this.comparator);
        return result;
    }
}

Наиболее эффективное решение:

В качестве альтернативы вы можете сортировать только при получении Iterator, и это было бы более ориентированным на производительность, если отсортированный порядок был действительно очень важен при повторении с помощью List. Это будет охватывать вариант использования клиентского кода, которому не нужно звонить, Collections.sort() перед каждой итерацией и инкапсулировать это поведение в класс.

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;

public class SortedList<E> extends LinkedList<E>
{
    private Comparator<E> comparator;

    public SortedList(final Comparator<E> comparator)
    {
        this.comparator = comparator;
    }

    @Override
    public Iterator<E> iterator()
    {
        Collections.sort(this, this.comparator);
        return super.iterator();
    }
}

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

Решение Guava:

Если вы используете Guava, и вы должны быть, вы можете просто использовать

Ordering.immutableSortedCopy() только тогда, когда вам нужно выполнить итерацию и сделать с ней.

Ответ 4

Возможно, что-то вроде TreeSet (или TreeMultiset, если вам нужны дубликаты) с более эффективным случайным доступом, но я сомневаюсь, что он был реализован на Java. Создание каждого node дерева запоминает, что размер его левого поддерева позволяет получить доступ к элементу по индексу во времени O(log(size)), что неплохо.

Чтобы реализовать его, вам нужно будет переписать хорошую часть базового TreeMap.

Ответ 5

Я бы использовал Guava TreeMultiset предполагая, что вы хотите List, потому что у вас могут быть повторяющиеся элементы. Он сделает все, что вы пожелаете. Единственное, что у него не будет, это доступ на основе индексов, что не имеет особого смысла, учитывая, что вы все равно не помещаете элементы по указанным вами индексам. Другая вещь, о которой нужно помнить, заключается в том, что она фактически не будет хранить дубликаты объектов equal... просто счет их общего количества.

Ответ 6

Commons-коллекции TreeBag

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

Поскольку вы, скорее всего, обеспокоены порядком итерации, я считаю, что вы можете переопределить метод iterator():

public class OrderedIterationList<E> extends ArrayList<E> {
    @Override
    public Iterator<E> iterator() {
        Object[] array = this.toArray(); // O(1)
        Arrays.sort(array);
        return Arrays.asList(array).iterator(); // asList - O(1)
    }
}

Вы можете улучшить это, сохранив моментальный снимок сортированной коллекции и используя modCount, чтобы проверить, не изменяется ли коллекция.

В зависимости от прецедентов это может быть менее или более эффективным, чем предложение Питера. Например, если вы добавляете несколько элементов и итерации. (без добавления элементов между итерациями), тогда это может быть более эффективным.

Ответ 7

Единственный способ иметь любую отсортированную структуру с временем, меньшим, чем O (n) для добавления /indexOf/remove/get, - это использовать дерево. В этом случае операции обычно имеют O (log2n), а ход - как O (1).

O (n) - только связанный список.

Изменить: вставка в связанный список w/двоичный поиск. Для операций с вставками, не использующих двоичную структуру, а не небольшие размеры, это должно быть оптимальным.

@Peter: Существует алгоритм w/O (log2n), который сравнивает (которые медленны), чтобы вставить, и O (n) перемещается. Если вам нужно переопределить LinkedList, пусть будет так. Но это настолько аккуратно, насколько это возможно. Я считаю, что алгоритм настолько чист, насколько это возможно, чтобы быть понятным, его можно немного оптимизировать.

package t1;

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;

public class SortedList {


    private static <T> int binarySearch(ListIterator<? extends Comparable<? super T>> i, T key){
        int low = 0;
        int high= i.previousIndex();
        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = get(i, mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid;
        }
        return -(low + 1);  // key not found
    }

    private static <T> T get(ListIterator<? extends T> i, int index) {
        T obj = null;
        int pos = i.nextIndex();
        if (pos <= index) {
            do {
                obj = i.next();
            } while (pos++ < index);
        } else {
            do {
                obj = i.previous();
            } while (--pos > index);
        }
        return obj;
    }
    private static void move(ListIterator<?> i, int index) {        
        int pos = i.nextIndex();
        if (pos==index)
            return;

        if (pos < index) {
            do {
                i.next();
            } while (++pos < index);
        } 
        else {
            do {
                i.previous();
            } while (--pos > index);
        }
    }
    @SuppressWarnings("unchecked")
    static  <T> int insert(List<? extends Comparable<? super T>> list, T key){
        ListIterator<? extends Comparable<? super T>> i= list.listIterator(list.size());
        int idx = binarySearch(i, key); 
        if (idx<0){
            idx=~idx;
        }
        move(i, idx);
        ((ListIterator<T>)i).add(key);
        return i.nextIndex()-1;
    }

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        LinkedList<Integer> unsorted = new LinkedList<Integer>();
        Random r =new Random(11);
        for (int i=0;i<33;i++){
            Integer n = r.nextInt(17);
            insert(list, n);
            unsorted.add(n);            
        }

        System.out.println("  sorted: "+list);
        System.out.println("unsorted: "+unsorted);
    }

Ответ 8

Очевидным решением является создание собственного класса, который реализует интерфейс java.util.List и принимает Comparator в качестве аргумента конструктору. Вы использовали бы компаратор в правильных местах, т.е. Метод add мог бы перебирать существующие элементы и вставлять новый элемент в нужное место. Вы запретили бы призывы к методам типа add(int index, Object obj) и т.д.

Фактически, кто-то должен был создать это уже... быстрый поиск Google показывает хотя бы один пример:

http://www.ltg.ed.ac.uk/NITE/nxt/apidoc/net/sourceforge/nite/util/SortedList.html

Ответ 9

Основное различие между SortedSet и List:

• SortedSet сохраняет его в правильном порядке, но вы не можете получить доступ к определенному элементу по индексу.
• Список позволяет индексировать доступ и произвольный порядок элементов. Он также позволяет изменять любой элемент (по индексу или итератору) на другой элемент без изменения местоположения.

Кажется, вы хотите сгладить как автоматическую сортировку, так и доступность (разумный быстрый) доступа к индексу. В зависимости от размера данных и того, как часто происходит индексация чтения или добавления новых элементов, это мои идеи:

• завернутый ArrayList, где метод add использовал ListIterator для поиска пятна вставки, а затем вставлял туда элемент. Это O (n) для вставок, O (1) для индексированного доступа.
• завернутый LinkedList, где метод add использовал ListIterator для поиска пятна вставки, а затем вставлял туда элемент. (Это все еще O (n) для вставок (иногда с меньшим коэффициентом ArrayList, иногда даже больше), а также с индексированным доступом.)
• модифицированное двоичное дерево, отслеживающее размеры обеих половин на каждом уровне, что позволяет индексировать доступ. (Это будет O (log n) для каждого доступа, но для этого требуется дополнительное программирование, поскольку оно еще не включено в Java SE. Или вы найдете библиотеку, которая может это сделать.)

В любом случае интерфейсы и контракты SortedSet и List на самом деле несовместимы, поэтому вы хотите, чтобы часть списка была доступна только для чтения (или только для чтения и удаления), не позволяя устанавливать и добавлять и наличие дополнительного объекта (возможно, реализация интерфейса Collection) для добавления объектов.

Ответ 10

Рассмотрим indexed-tree-map, который я создал, столкнувшись с аналогичной проблемой, вы сможете получить доступ к элементам по индексу и получить индекс элементов в то время как сохраняя порядок сортировки. Дубликаты могут быть помещены в массивы как значения под одним и тем же ключом.

Ответ 11

Лучший способ сделать это - переопределить реализацию добавления списка. Я собираюсь использовать LinkedList, чтобы продемонстрировать это, поскольку это позволяет эффективно вставлять.

public boolean add(Integer e)
{
    int i = 0;
    for (Iterator<Integer> it = this.iterator(); it.hasNext();)
    {
        int current = it.next();
        if(current > e)
        {
            super.add(i, e);
            return true;
        }
        i++;
    }
    return super.add(e);
}

Вышеприведенный код создает отсортированный список целых чисел, который всегда сортируется. Его можно легко модифицировать для работы с любым другим типом данных. Однако здесь вам не придется использовать функцию add(index, value), так как это, очевидно, нарушит сортировку.

Хотя люди, выше предлагавшие использовать Arrays.sort(), я бы избегал этого, поскольку это может быть значительно менее эффективный подход, тем более, что метод sort должен вызываться с каждым добавлением в список.

Ответ 12

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

private void add(Integer value) {
    ListIterator<Integer> listIterator = list.listIterator();

    Integer next = null;

    while (listIterator.hasNext()) {
        next = listIterator.next();

        if (next.compareTo(value) > 0) {                
            break;
        }
    }

    if (next == null || next.compareTo(value) < 0) {
        listIterator.add(value);
    } else {
        listIterator.set(value);
        listIterator.add(next);
    }
}

Ответ 13

Я верю, что Приоритетная очередь выполнит эту работу.

Предостережение (с той же страницы документа):

Этот класс и его итератор реализуют все необязательные методы Collection и интерфейсы итератора. Iterator, предоставленный в методе iterator() не гарантируется пересечь элементы приоритета очереди в любом конкретном порядке. если ты требуется упорядоченный обход, рассмотрите возможность использования Arrays.sort(pq.toArray()).