Я сбит с толку, что не могу найти на это быстрого ответа. По сути, я ищу структуру данных на 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
источник
Ответы:
Минималистичное решение
Вот «минимальное» решение.
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
:Те же рассуждения применимы к обеим версиям
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);
.... печатает:
источник
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. (Все эти операции являются необязательными согласно интерфейсу списка.)Используйте
java.util.PriorityQueue
.источник
Взгляните на SortedList
источник
addAll()
и думать, что все элементы будут отсортированы. Согласитесь также с UnsupportedOperationException.Вы можете попробовать TreeMultiSet от Guava .
Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100)); System.out.println(ms);
источник
A collection that supports order-independent equality, like Set, but may have duplicate elements
Подход 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 работает очень медленно при использовании больших списков. Использование того факта, что список отсортирован, позволяет нам находить точку вставки для новых значений с помощью двоичного поиска.
Я бы также использовал композицию вместо наследования, что-то вроде
источник
Списки обычно сохраняют порядок, в котором добавляются элементы. Вам определенно нужен список , или вам подойдет отсортированный набор (например
TreeSet<E>
)? В принципе, нужно ли сохранять дубликаты?источник
Это может быть немного слишком тяжелом для вас, но GlazedLists имеет SortedList , который идеально подходит для использования в качестве модели таблицы или JList
источник
Вы можете создать подкласс ArrayList и вызвать Collections.sort (this) после добавления любого элемента - для этого вам нужно будет переопределить две версии add и две версии addAll.
Производительность не будет такой хорошей, как у более умной реализации, которая вставляет элементы в нужное место, но она справится со своей задачей. Если добавление в список происходит редко, амортизируемая стоимость всех операций в списке должна быть низкой.
источник
Просто создайте новый класс следующим образом:
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);
источник
Я думаю, что выбор между SortedSets / Lists и «обычными» сортируемыми коллекциями зависит от того, нужна ли вам сортировка только для целей презентации или почти в каждой точке во время выполнения. Использование отсортированной коллекции может быть намного дороже, потому что сортировка выполняется каждый раз, когда вы вставляете элемент.
Если вы не можете выбрать коллекцию в JDK, вы можете взглянуть на Коллекции Apache Commons
источник
Поскольку в предлагаемых в настоящее время реализациях, которые реализуют отсортированный список, нарушая Collection API, есть собственная реализация дерева или что-то подобное, мне было любопытно, как будет работать реализация, основанная на TreeMap. (Особенно, поскольку TreeSet также основан на TreeMap)
Если кого-то это тоже интересует, он или она может свободно изучить это:
TreeList
Это часть основной библиотеки , вы, конечно, можете добавить ее через зависимость Maven. (Лицензия Apache)
В настоящее время реализация, кажется, довольно хорошо сравнивается на том же уровне, что и guava SortedMultiSet и TreeList библиотеки Apache Commons.
Но я был бы счастлив, если бы не только я протестировал реализацию, чтобы убедиться, что я не пропустил что-то важное.
С уважением!
источник
У меня такая же проблема. Итак, я взял исходный код 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 со значениями в виде массивов. Я бы сделал это.
источник