Реализация списка, поддерживающая порядок

Есть ли существующий 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) Я понял, что реализации этого вида списка будут иметь недостаточную производительность. Там два общих подхода:

  1. Использовать связную структуру (своего рода) B-дерево или подобное
  2. Использовать массив и вставку (с бинарным поиском)

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

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

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

ОБНОВИТЬ:

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

Источник

3 ответа

Решение

Ответ на новое требование. Я вижу два потенциала:

  • Сделайте то, для чего JavaDoc PriorityQueue говорит:

    Этот класс и его итератор реализуют все необязательные методы интерфейсов Collection и Iterator. Итератор, предоставленный в методе iterator() не гарантируется прохождение элементов очереди с приоритетами в каком-либо конкретном порядке. Если вам нужен упорядоченный обход, подумайте об использовании Arrays.sort(pq.toArray()),

    Я подозреваю, что это даст лучшую производительность, учитывая ваши требования. Если это неприемлемо, вам нужно лучше объяснить, чего вы пытаетесь достичь.

  • Создайте список, который просто сортирует себя при добавлении новых элементов. Это настоящая боль... если вы использовали связанную структуру, вы можете сделать эффективную сортировку вставки, но локальность плохая. Если вы использовали структуру на основе массива, сортировка вставкой - это боль, но обход лучше. Если итерация / обход нечасты, вы можете оставить содержимое списка несортированным и сортировать только по требованию.

  • Подумайте об использовании PriorityQueue, как я предлагал, и, если вам нужно выполнить итерацию по порядку, напишите итератор-обертку:

    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 говорится о временных свойствах различных операций:

Замечание по реализации: эта реализация обеспечивает время O(log(n)) для методов создания и удаления (offer, poll, remove() а также add); линейное время для remove(Object) а также contains(Object) методы; и постоянное время для методов поиска (peek, element, а также size).

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

Iterator предусмотрено в методе iterator() не гарантируется прохождение элементов очереди с приоритетами в каком-либо конкретном порядке. Если вам нужен упорядоченный обход, подумайте об использовании Arrays.sort(pq.toArray()),

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

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

Refs:

Источник

Вы, вероятно, должны использовать TreeSet:

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

Пример:

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

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

Источник

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

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

Источник
Другие вопросы по тегам