Список отсортированных массивов в Java

85

Я сбит с толку, что не могу найти на это быстрого ответа. По сути, я ищу структуру данных на Java, которая реализует java.util.Listинтерфейс, но хранит свои элементы в отсортированном порядке. Я знаю, что вы можете использовать нормальный ArrayListи использовать Collections.sort()его, но у меня есть сценарий, в котором я иногда добавляю и часто извлекаю участников из своего списка, и я не хочу, чтобы ему приходилось сортировать его каждый раз, когда я извлекаю член в случае, если добавлен новый. Может ли кто-нибудь указать мне на такую ​​вещь, которая существует в JDK или даже сторонних библиотеках?

РЕДАКТИРОВАТЬ : структура данных должна будет сохранять дубликаты.

РЕЗЮМЕ ОТВЕТА : Я нашел все это очень интересным и многому научился. В частности, Aioobe заслуживает упоминания за его настойчивость в попытках достичь моих требований выше (в основном, отсортированная реализация java.util.List, которая поддерживает дубликаты). Я принял его ответ как наиболее точный из того, о чем я спрашивал, и как наводящий на большинство размышлений о последствиях того, что я искал, даже если то, что я спросил, было не совсем тем, что мне нужно.

Проблема с тем, о чем я просил, заключается в самом интерфейсе List и концепции дополнительных методов в интерфейсе. Процитируем javadoc:

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

Вставка в отсортированный список не дает точного контроля над точкой вставки. Затем вы должны подумать, как вы будете обрабатывать некоторые методы. Взять, addк примеру:

публичное логическое добавление (объект o)

 Appends the specified element to the end of this list (optional operation).

Теперь вы оказались в неудобной ситуации: 1) разорвать контракт и реализовать отсортированную версию добавления 2) разрешить addдобавить элемент в конец списка, нарушив ваш отсортированный порядок 3) оставив add(как необязательный), выбрасывая an UnsupportedOperationExceptionи реализует другой метод, который добавляет элементы в отсортированном порядке.

Вариант 3, вероятно, лучший, но я считаю неприятным наличие метода добавления, который вы не можете использовать, и другого метода sortedAdd, которого нет в интерфейсе.

Другие связанные решения (в произвольном порядке):

  • java.util.PriorityQueue, который, вероятно, ближе всего к тому, что мне нужно, чем то, что я просил. Очередь - не самое точное определение коллекции объектов в моем случае, но функционально она делает все, что мне нужно.
  • net.sourceforge.nite.util.SortedList . Однако эта реализация нарушает контракт интерфейса List, реализуя сортировку в add(Object obj)методе, и, как ни странно, не имеет никакого эффекта для метода add(int index, Object obj). По общему мнению, throw new UnsupportedOperationException()этот сценарий может быть лучшим выбором.
  • TreeMultiSet Guava Реализация набора, поддерживающая дубликаты
  • ca.odell.glazedlists.SortedList Этот класс содержит оговорку в своей документации javadoc:Warning: This class breaks the contract required by List
Крис Найт
источник
4
Если вы вставляете время от времени и часто читаете, почему бы просто не отсортировать его во время вставки?
serg 01

Ответы:

62

Минималистичное решение

Вот «минимальное» решение.

class SortedArrayList<T> extends ArrayList<T> {

    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        add(value);
        Comparable<T> cmp = (Comparable<T>) value;
        for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--)
            Collections.swap(this, i, i-1);
    }
}

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

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

Отмена List.add

Обратите внимание, что переопределение List.add(или List.addAllв этом отношении) для вставки элементов в отсортированном виде было бы прямым нарушением спецификации интерфейса . Что вы могли бы сделать, так это переопределить этот метод, чтобы создать файл UnsupportedOperationException.

Из документов List.add:

boolean add(E e)
    Добавляет указанный элемент в конец этого списка (необязательная операция).

Те же рассуждения применимы к обеим версиям add, обеим версиям addAllи set. (Все эти операции являются необязательными согласно интерфейсу списка.)


Некоторые тесты

SortedArrayList<String> test = new SortedArrayList<String>();

test.insertSorted("ddd");    System.out.println(test);
test.insertSorted("aaa");    System.out.println(test);
test.insertSorted("ccc");    System.out.println(test);
test.insertSorted("bbb");    System.out.println(test);
test.insertSorted("eee");    System.out.println(test);

.... печатает:

[ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]
aioobe
источник
Хорошее начало, но вызовы add или addall добавили бы участников в несортированном виде.
Крис Найт
Да. Все, что угодно, кроме добавления их в список, было бы прямым нарушением List-интерфейса. Смотрите мой обновленный ответ.
aioobe
@aioobe Хорошее замечание. Но разве неподдерживаемая операция метода интерфейса не является запахом кода? Правильный способ может заключаться в том, чтобы не расширять ArrayList, а реализовать List, но даже тогда, возможно, List просто не предназначен для этой цели. Из Javadoc for List: The user of this interface has precise control over where in the list each element is insertedэто не лучшее описание для вставки элементов в отсортированном виде, и вам все равно придется иметь дело с add(int index, Object obj)методом интерфейса. Эти проблемы, вероятно, объясняют, почему List не реализован в отсортированном виде.
Крис Найт
Что ж, операция не является обязательной по какой-то причине. Я не удивлюсь, если при работе .addс SortedArrayList получу UnsupportedExceptionOperation. Да, те же рассуждения применимы к обеим версиям add, обеим версиям addAll и set. (Все эти операции являются необязательными согласно интерфейсу списка.)
aioobe
Ах, я не понимал, что это дополнительные операции. Сюжет сгущается ...;)
Крис Найт
10

Используйте java.util.PriorityQueue.

Гадолин
источник
7
это не список, т.е. без произвольного доступа.
Тило
1
Это куча приоритетов на основе очередей, а не List.
zengr
3
Конечно, со списком, который поддерживает порядок сортировки, индексы постоянно меняются, поэтому произвольный доступ, вероятно, в любом случае не нужен.
Тило
5
@Qwerky, обратите внимание, что точный ответ - не всегда лучший ответ, или ответ, который на самом деле следует за OP.
aioobe
3
приоритетная очередь не предоставляет отсортированный порядок при итерации.
marcorossi 03
6

Взгляните на SortedList

Этот класс реализует отсортированный список. Он построен с помощью компаратора, который может сравнивать два объекта и соответственно сортировать объекты. Когда вы добавляете объект в список, он вставляется в правильное место. Объекты, которые равны согласно компаратору, будут в списке в том порядке, в котором они были добавлены в этот список. Добавляйте только те объекты, которые может сравнивать компаратор.


Когда список уже содержит объекты, которые равны в соответствии с компаратором, новый объект будет вставлен сразу после этих других объектов.

Джигар Джоши
источник
5
Выглядит хорошо, но также выглядит ошибочно: ни одна из версий addAll не переопределена, поэтому после их вызова список не будет отсортирован.
Том Андерсон
3
А метод добавления «не действует». Он должен скорее генерировать исключение UnsupportedOperationException, если его нельзя использовать.
Тило
@Tom Anderson @Thilo, согласен с вами обоими.
Джигар Джоши
1
Интересно, но я довольно настороженно отношусь к тому, что кто-то в будущем будет использовать addAll()и думать, что все элементы будут отсортированы. Согласитесь также с UnsupportedOperationException.
Крис Найт
1
Какова временная сложность добавления в этот список?
shrini1000 07
6

Вы можете попробовать TreeMultiSet от Guava .

 Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
 System.out.println(ms);
Эмиль
источник
+1. Это отличная библиотека. MultiSet isA collection that supports order-independent equality, like Set, but may have duplicate elements
Шервин Асгари
5

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

class SortedList<T> extends ArrayList<T> {

    public void insertSorted(T value) {
        int insertPoint = insertPoint(value);
        add(insertPoint, value);
    }

    /**
     * @return The insert point for a new value. If the value is found the insert point can be any
     * of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.).
     */
    private int insertPoint(T key) {
        int low = 0;
        int high = size() - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = (Comparable<T>) get(mid);
            int cmp = midVal.compareTo(key);

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

        return low;  // key not found
    }
}

Решение aioobe работает очень медленно при использовании больших списков. Использование того факта, что список отсортирован, позволяет нам находить точку вставки для новых значений с помощью двоичного поиска.

Я бы также использовал композицию вместо наследования, что-то вроде

SortedList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Эмануэль Моеклин
источник
4

Списки обычно сохраняют порядок, в котором добавляются элементы. Вам определенно нужен список , или вам подойдет отсортированный набор (например TreeSet<E>)? В принципе, нужно ли сохранять дубликаты?

Джон Скит
источник
2
Спасибо, Джон, но мне нужно сохранить дубликаты,
Крис Найт,
2

Это может быть немного слишком тяжелом для вас, но GlazedLists имеет SortedList , который идеально подходит для использования в качестве модели таблицы или JList

I82: много
источник
1

Вы можете создать подкласс ArrayList и вызвать Collections.sort (this) после добавления любого элемента - для этого вам нужно будет переопределить две версии add и две версии addAll.

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

Том Андерсон
источник
1

Просто создайте новый класс следующим образом:

public class SortedList<T> extends ArrayList<T> {

private final Comparator<? super T> comparator;

public SortedList() {
    super();
    this.comparator = null;
}

public SortedList(Comparator<T> comparator) {
    super();
    this.comparator = comparator;
}

@Override
public boolean add(T item) {
    int index = comparator == null ? Collections.binarySearch((List<? extends Comparable<? super T>>)this, item) :
            Collections.binarySearch(this, item, comparator);
    if (index < 0) {
        index = index * -1 - 2;
    }
    super.add(index+1, item);
    return true;
}

@Override
public void add(int index, T item) {
    throw new UnsupportedOperationException("'add' with an index is not supported in SortedArrayList");
}

@Override
public boolean addAll(Collection<? extends T> items) {
    boolean allAdded = true;
    for (T item : items) {
        allAdded = allAdded && add(item);
    }
    return allAdded;
}

@Override
public boolean addAll(int index, Collection<? extends T> items) {
    throw new UnsupportedOperationException("'addAll' with an index is not supported in SortedArrayList");
}

}

Проверить это можно так:

    List<Integer> list = new SortedArrayList<>((Integer i1, Integer i2) -> i1.compareTo(i2));
    for (Integer i : Arrays.asList(4, 7, 3, 8, 9, 25, 20, 23, 52, 3)) {
        list.add(i);
    }
    System.out.println(list);
user13750620
источник
0

Я думаю, что выбор между SortedSets / Lists и «обычными» сортируемыми коллекциями зависит от того, нужна ли вам сортировка только для целей презентации или почти в каждой точке во время выполнения. Использование отсортированной коллекции может быть намного дороже, потому что сортировка выполняется каждый раз, когда вы вставляете элемент.

Если вы не можете выбрать коллекцию в JDK, вы можете взглянуть на Коллекции Apache Commons

кодпорн
источник
0

Поскольку в предлагаемых в настоящее время реализациях, которые реализуют отсортированный список, нарушая Collection API, есть собственная реализация дерева или что-то подобное, мне было любопытно, как будет работать реализация, основанная на TreeMap. (Особенно, поскольку TreeSet также основан на TreeMap)

Если кого-то это тоже интересует, он или она может свободно изучить это:

TreeList

Это часть основной библиотеки , вы, конечно, можете добавить ее через зависимость Maven. (Лицензия Apache)

В настоящее время реализация, кажется, довольно хорошо сравнивается на том же уровне, что и guava SortedMultiSet и TreeList библиотеки Apache Commons.

Но я был бы счастлив, если бы не только я протестировал реализацию, чтобы убедиться, что я не пропустил что-то важное.

С уважением!

Omnaest
источник
0

У меня такая же проблема. Итак, я взял исходный код java.util.TreeMap и написал IndexedTreeMap . Он реализует мою собственную IndexedNavigableMap :

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

Реализация основана на обновлении весов узлов в красно-черном дереве при его изменении. Вес - это количество дочерних узлов под данным узлом плюс один сам. Например, когда дерево поворачивается влево:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight просто обновляет веса до корня:

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

И когда нам нужно найти элемент по индексу, вот реализация, которая использует веса:

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

Также очень удобно найти индекс ключа:

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    index += getWeight(e.left);

    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

Вы можете найти результат этой работы на http://code.google.com/p/indexed-tree-map/

TreeSet / TreeMap (а также их индексированные аналоги из проекта indexed-tree-map) не допускают дублирования ключей, вы можете использовать 1 ключ для массива значений. Если вам нужен SortedSet с дубликатами, используйте TreeMap со значениями в виде массивов. Я бы сделал это.

Виталий Сазанович
источник