Вопрос по collections, insertion-order, list, java – Реализация списка, поддерживающая порядок

16

Есть ли существующий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.* поскольку было бы трудно представить новые библиотеки в данный момент.

Note: (UPDATE4) Я понял, что реализации такого рода списка будут иметь недостаточную производительность. Там два общих подхода:

Use Linked structure (sort of) B-tree or similar Use array and insertion (with binary search)

№ 1. есть проблема с отсутствием кэша процессора № 2. есть проблемы со смещением элементов в массиве.

UPDATE2: TreeSet не работает, потому что использует предоставленный компаратор (MyComparator) проверить на равенство и исходя из этого предполагает, что элементы равны и исключают их. Мне нужен этот компаратор только для заказа, а не «уникальности» фильтрация (поскольку элементы по своему естественному порядку не равны)

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

ОБНОВИТЬ:

Подобный вопрос:
Хороший отсортированный список для Java
Список отсортированных массивов в Java

Нет, они не нарушаютSet или жеMap контракт - по крайней мере, не с компаратором, который согласуется с равными, что является абсолютно справедливым. Даже в этом случае их поведение является «более или менее»; аналогично их договорным обязательствам, тогда как описанный вами подходcompletely нарушать договор. Louis Wasserman
Такое поведение будет нарушатьList контракт, и, как правило, будет плохой идеей. (Гуава рассмотрел и отверг такие особенности.) Louis Wasserman
Какая частьList контракт будет нарушен? Op De Cirkel
Спецификация дляadd(E) говорит & quot; Добавляет указанный элемент в конец этого списка. & quot; Добавление его где-либо еще в списке нарушает договор. Louis Wasserman
TreeSet а такжеTreeMap нарушать договорSet а такжеMap соответственно, но они все еще там (вjava.*) Op De Cirkel

Ваш Ответ

3   ответа
9

Do what the JavaDoc for PriorityQueue says:

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

I suspect this will yield the best performance given your requirements. If this is not acceptable, you'll need to better explain what you're trying to accomplish.

Build a List that simply sorts itself upon addition of new elements. This is a real pain... if you used a linked structure, you can do an efficient insertion sort, but locality is bad. If you used an array-backed structure, insertion sort is a pain but traversal is better. If iteration/traversal is infrequent, you could hold the list contents unsorted and sort only on demand.

Consider using a PriorityQueue as I suggested, and in the event you need to iterate in order, write a wrapper iterator:

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(""); }
}

Use Guava's TreeMultiSet. I tested the following code with Integer and it seems to do the right thing.

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, Я вижу, что вам также нужен итератор, так что это не сработает.

Если вы действительно хотите заказатьlist-like вещь, вы можете использоватьPriorityQueue.

Comparator<T> cmp = new MyComparator<T>();
PriorityQueue<T> pq = new PriorityQueue<T>(cmp);
pq.add(someT);

Обратите внимание на то, что в документации API говорится о временных свойствах различных операций:

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

Вы также должны знать, что итераторы, созданныеPriorityQueue не ведите себя так, как можно ожидать:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

Я только что заметил, что Гуава обеспечиваетMinMaxPriorityQueue, Эта реализация поддерживается массивом, а не связанной формой, предоставленной в JDK.PriorityQueueи, таким образом, вероятно, имеет другое временное поведение. Если вы делаете что-то чувствительное к производительности, вы можете посмотреть. В то время как примечания дают немного различающиеся (линейные и логарифмические) времена большого-O, все эти времена также должны быть ограничены, что может быть полезно.

Это неList реализация сама по себе, которая поддерживает порядок, но то, что вы, вероятно, ищетеSortedSet,TreeSet является наиболее распространенным. Другая реализация, аConcurrentSkipListSet для более конкретного использования. Обратите внимание, чтоSortedSet обеспечивает порядок, но не позволяет дублировать записи, как это делаетList.

Refs:

Blog post PriorityQueue iterator is not ordered SO question on PQ ordered iterator
СогласноGuava documentation,TreeMultiList не гарантируется работа для случая использования, когдаcompareTo() не согласуется с равными, как в посте OP. Документация гласит: «Предупреждение: сравнение должно соответствовать равным, как объясненоComparable спецификация класса. В противном случае полученный мультимножество будет нарушатьCollection договор, который указан в условияхObject.equals(java.lang.Object). & Quot;
Хотя это не решает мою проблему. Это объясняет ситуацию и возможные варианты выбора. Op De Cirkel
17

TreeSet:

The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

Пример:

Comparator<T> cmp = new MyComparator<T>();
TreeSet<T> t = new TreeSet<T>(cmp);
l.add(someT);

Обратите внимание, что этоsetпоэтому повторяющиеся записи не допускаются. Это может или не может работать для вашего конкретного случая использования.

Теперь я могу дать +1 с чистой совестью :)
Обратите внимание, что существует большая разница междуList иSetОдин позволяет дублировать элементы, другой - нет.
Должна быть возможность обойти ограничение без дубликатов, вставив объекты-обертки (W), каждый из которых содержит указатель на некоторый объект T, затем каким-то образом убедитесь, что эти объекты W обрабатываются как разные, даже если они указывают на один и тот же T. Это может быть сделано путем определения лексикографического порядка в W 's. В частности, чтобы сравнить два W, сначала сравните соответствующие T, и только если они равны, сравните идентичность двух W. Хотя я не уверен, как это делается в Java; в C вы просто используете & lt; оператор на двух W указателей.
Хорошая точка зрения; Я обновил ответ, чтобы убедиться, что это понятно.
-1

и я думаю об использовании TreeSet. Чтобы избежать исключения "равно" элементы Я изменю компаратор, поэтому вместо возврата 0 он будет возвращать случайное число между (-1,1) или всегда будет возвращать 1.

Если у вас нет контроля над Компаратором или вы используете его для чего-то другого, чем вставка этого решения, вам не подойдет.

Похожие вопросы