Список отсортированных массивов в Java
Я сбит с толку, что не могу найти быстрый ответ на это. По сути, я ищу структуру данных в Java, которая реализует java.util.List интерфейс, но который хранит своих членов в отсортированном порядке. Я знаю, что вы можете использовать нормальный ArrayList и использовать Collections.sort() на нем, но у меня есть сценарий, в котором я время от времени добавляю и часто извлекаю участников из своего списка, и я не хочу сортировать его каждый раз, когда извлекаю участника в случае добавления нового. Кто-нибудь может указать мне на такую вещь, которая существует в JDK или даже сторонних библиотеках?
РЕДАКТИРОВАТЬ: структура данных должна будет сохранить дубликаты.
РЕЗЮМЕ ОТВЕТА: Я нашел все это очень интересным и многому научился. Aioobe, в частности, заслуживает упоминания за его настойчивость в попытке выполнить мои требования выше (в основном, отсортированная реализация java.util.List, которая поддерживает дубликаты). Я принял его ответ как наиболее точный из того, что я просил, и больше всего думал о последствиях того, что я искал, даже если то, что я спрашивал, было не совсем тем, что мне нужно.
Проблема с тем, что я просил, заключается в самом интерфейсе List и концепции необязательных методов в интерфейсе. Процитирую Javadoc:
Пользователь этого интерфейса имеет точный контроль над тем, где в списке каждый элемент вставлен.
Вставка в отсортированный список не имеет точного контроля над точкой вставки. Затем вы должны подумать, как вы будете обрабатывать некоторые методы. принимать add например:
public boolean add (Object o)
Appends the specified element to the end of this list (optional operation).
Теперь вы оказались в неудобной ситуации: 1) разорвать контракт и внедрить отсортированную версию add
2) add добавить элемент в конец списка, нарушая ваш отсортированный порядок 3) Выход add (как его необязательно), бросая UnsupportedOperationException и реализации другого метода, который добавляет элементы в отсортированном порядке.
Вариант 3, вероятно, самый лучший, но я нахожу его неприятным, имея метод add, который вы не можете использовать, и другой метод 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
13 ответов
Минималистичное решение
Вот "минимальное" решение.
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]
Вы можете попробовать TreeMultiSet в Guava.
Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
System.out.println(ms);
Посмотрите на SortedList
Этот класс реализует отсортированный список. Он построен с помощью компаратора, который может сравнивать два объекта и сортировать объекты соответственно. Когда вы добавляете объект в список, он вставляется в правильное место. Объект, равный по данным компаратора, будет находиться в списке в том порядке, в котором они были добавлены в этот список. Добавляйте только те объекты, которые компаратор может сравнивать.
Когда список уже содержит объекты, которые равны по сравнению с компаратором, новый объект будет вставлен сразу после этих других объектов.
Списки обычно сохраняют порядок добавления элементов. Вам определенно нужен список или будет отсортированный набор (например, TreeSet<E>) будет хорошо для тебя? По сути, вам нужно сохранить дубликаты?
Подход 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
Это может быть слишком тяжело для вас, но 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);
У меня такая же проблема. Поэтому я взял исходный код 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 со значениями в качестве массивов. Я бы сделал это.
Я думаю, что выбор между SortedSets/Lists и "обычными" сортируемыми коллекциями зависит от того, нужна ли вам сортировка только для целей презентации или почти в любой точке во время выполнения. Использование отсортированной коллекции может быть намного дороже, потому что сортировка выполняется каждый раз, когда вы вставляете элемент.
Если вы не можете выбрать коллекцию в JDK, вы можете взглянуть на Коллекции Apache Commons
Поскольку предлагаемые в настоящее время реализации, которые реализуют отсортированный список, нарушая API-интерфейс Collection, имеют собственную реализацию дерева или чего-то подобного, мне было любопытно, как будет реализовываться реализация, основанная на TreeMap. (Особенно потому, что TreeSet также основан на TreeMap)
Если кому-то это тоже интересно, он или она могут свободно в этом разобраться:
Его часть базовой библиотеки, вы, конечно, можете добавить его через зависимость Maven. (Лицензия Apache)
В настоящее время реализация, кажется, довольно хорошо сравнивается на том же уровне, что и guava SortedMultiSet и TreeList библиотеки Apache Commons.
Но я был бы рад, если бы не только я проверил реализацию, чтобы убедиться, что я не пропустил что-то важное.
С наилучшими пожеланиями!
Следующий метод можно использовать для печати элементов объектов LinkedList String.
Метод принимает объект LinkedList в качестве входных данных и выводит каждый элемент списка, разделенный пробелом, на консоль. Чтобы сделать вывод более читабельным, метод также добавляет новую строку до и после списка.
public static void printList(LinkedList<String> list) {
System.out.println("\nList is: ");
for (String element : list) {
System.out.print(element + " ");
}
System.out.println();
}