Реализация списка, поддерживающая порядок
-
12-12-2019 - |
Вопрос
Существует ли существующий List
реализация на Java, которая поддерживает порядок на основе предоставленного Comparator
?
Что-то, что можно использовать следующим образом:
Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);
так что someT
вставляется так, что порядок в списке поддерживается в соответствии с cmp
(По предложению @andersoj я завершаю свой вопрос еще одной просьбой)
Также я хочу иметь возможность перемещаться по списку в отсортированном порядке, не удаляя элементы, т.е.:
T min = Const.SMALLEST_T;
for (T e: l) {
assertTrue(cmp.compare(min, e) >= 0);
min = e;
}
должно пройти.
Все предложения приветствуются (кроме предложения использовать Collections.sort
в неупорядоченном полном списке), хотя я бы предпочел что-нибудь в java.*
или в конце концов org.apache.*
поскольку в данный момент было бы сложно внедрять новые библиотеки.
Примечание:(ОБНОВЛЕНИЕ4) Я понял, что реализации такого списка будут иметь недостаточную производительность.Существует два общих подхода:
- Используйте связанную структуру (что-то вроде B-дерева или аналогичную).
- Использовать массив и вставку (с двоичным поиском)
Нет 1.имеет проблему с промахами кэша ЦП No 2.имеет проблему со сдвигом элементов в массиве.
ОБНОВЛЕНИЕ2:
TreeSet
не работает, поскольку использует предоставленный компаратор (MyComparator
) для проверки равенства и на основании этого предполагает, что элементы равны, и исключает их.Мне нужен этот компаратор только для упорядочения, а не для фильтрации «уникальность» (поскольку элементы по их естественному порядку не равны)
ОБНОВЛЕНИЕ3:
PriorityQueue
не работает как List
(как мне нужно), поскольку нет возможности пройти его в том порядке, в котором он «отсортирован», чтобы получить элементы в отсортированном порядке, вам нужно удалить их из коллекции.
ОБНОВЛЯТЬ:
Аналогичный вопрос:
Хороший отсортированный список для Java
Список отсортированных массивов в Java
Решение
Ответ на новое требование.Я вижу два потенциала:
Делайте то, для чего нужен JavaDoc
PriorityQueue
говорит:Этот класс и его итератор реализуют все необязательные методы интерфейсов Collection и Iterator.Итератор, предоставленный в методе
iterator()
не гарантируется проход элементов приоритетной очереди в каком-либо определенном порядке.Если вам нужен упорядоченный обход, рассмотрите возможность использованияArrays.sort(pq.toArray())
.Я подозреваю, что это даст наилучшую производительность с учетом ваших требований.Если это неприемлемо, вам нужно будет лучше объяснить, чего вы пытаетесь достичь.
Построить Список который просто сортируется при добавлении новых элементов.Это настоящая боль...если вы использовали связанную структуру, вы можете выполнить эффективную сортировку вставкой, но локальность плоха.Если вы использовали структуру на базе массива, сортировка вставкой — это боль, но обход лучше.Если итерация/обход происходят нечасто, вы можете оставить содержимое списка несортированным и сортировать только по требованию.
Рассмотрите возможность использования Приоритетная очередь как я предложил, и в случае, если вам нужно выполнить итерацию по порядку, напишите итератор-обертку:
class PqIter implements Iterator<T> { final PriorityQueue<T> pq; public PqIter(PriorityQueue <T> source) { pq = new PriorityQueue(source); } @Override public boolean hasNext() { return pq.peek() != null } @Override public T next() { return pq.poll(); } @Override public void remove() { throw new UnsupportedOperationException(""); } }
Используйте Гуаву
TreeMultiSet
.Я протестировал следующий код с помощьюInteger
и кажется, что поступает правильно.import com.google.common.collect.TreeMultiset; public class TreeMultiSetTest { public static void main(String[] args) { TreeMultiset<Integer> ts = TreeMultiset.create(); ts.add(1); ts.add(0); ts.add(2); ts.add(-1); ts.add(5); ts.add(2); for (Integer i : ts) { System.out.println(i); } } }
Ниже рассматривается проблема уникальности/фильтрации, с которой вы столкнулись при использовании SortedSet
.Я вижу, что вам тоже нужен итератор, так что это не сработает.
Если то, что вам действительно нужно, это упорядоченный похожий на список вещь, вы можете использовать PriorityQueue
.
Comparator<T> cmp = new MyComparator<T>();
PriorityQueue<T> pq = new PriorityQueue<T>(cmp);
pq.add(someT);
Обратите внимание на то, что в документации API говорится о временных свойствах различных операций:
Примечание по реализации:эта реализация обеспечивает О (журнал (п)) время для методов постановки в очередь и удаления из очереди (
offer
,poll
,remove()
иadd
); линейный время дляremove(Object)
иcontains(Object)
методы;и постоянный время для методов поиска (peek
,element
, иsize
).
Вы также должны знать, что итераторы, созданные PriorityQueue
не вести себя так, как можно было бы ожидать:
Тем
Iterator
предоставлено в методеiterator()
не гарантируется проход элементов приоритетной очереди в каком-либо определенном порядке.Если вам нужен упорядоченный обход, рассмотрите возможность использованияArrays.sort(pq.toArray())
.
Я только что заметил, что Guava предоставляет MinMaxPriorityQueue
.Эта реализация поддерживается массивом, а не связанной формой, представленной в JDK. PriorityQueue
, и, таким образом, вероятно, имеет другое поведение по времени.Если вы делаете что-то, чувствительное к производительности, возможно, вы захотите взглянуть.Хотя в примечаниях даны несколько разные (линейные и логарифмические) времена большого О, все эти времена также должны быть ограничены, что может быть полезно.
Это не List
реализация как таковая, которая поддерживает порядок, но вы, вероятно, ищете реализации SortedSet
.А TreeSet
является наиболее распространенным.Другая реализация, ConcurrentSkipListSet
предназначен для более конкретного использования.Обратите внимание, что SortedSet
обеспечивает упорядочивание, но не допускает дублирования записей, как это делает List
.
Ссылки:
- Сообщение блога
PriorityQueue
итератор не заказан - ТАК вопрос по PQ упорядоченный итератор
Другие советы
Вы, вероятно, должны использовать использование TreeSet :
Элементы упорядочены с использованием их естественного упорядочения или компаратором, приведенным при установленном времени создания, в зависимости от того, какой конструктор используется.
Пример:
.Comparator<T> cmp = new MyComparator<T>(); TreeSet<T> t = new TreeSet<T>(cmp); l.add(someT);
Обратите внимание, что это набор
SET , поэтому не допускаются дубликаты записей.Это может или не может работать для вашего конкретного использования.
У меня есть похожая проблема, и я думаю о том, чтобы использовать Treet.Чтобы избежать исключения «равных» элементов, я изменим компаратор, поэтому вместо того, чтобы возвращать 0, он вернет случайное число между (-1,1), либо вернутся всегда 1.
Если у вас нет контроля над компаратором или, если вы используете его для чего-то другого, отличного от установки этого решения, не будет работать для вас.