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

StackOverflow https://stackoverflow.com//questions/10675446

Вопрос

Существует ли существующий 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.имеет проблему с промахами кэша ЦП 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.

Ссылки:

Другие советы

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top