Внедрение списка, поддерживающее порядок - программирование
Подтвердить что ты не робот

Внедрение списка, поддерживающее порядок

Существует ли существующая реализация List в Java, которая поддерживает порядок на основе Comparator?

Что-то, что можно использовать следующим образом:

Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);

чтобы вставить someT так, чтобы порядок в списке поддерживался в соответствии с cmp

(В предложении @andersoj я завершаю свой вопрос еще одним запросом)

Также я хочу, чтобы иметь возможность перемещать список в отсортированном порядке без удаления элементов, i.e:

T min = Const.SMALLEST_T;
for (T e: l) {
  assertTrue(cmp.compare(min, e) >= 0);
  min = e;
}

должен пройти.

Все предложения приветствуются (за исключением того, что мне нужно использовать Collections.sort в неупорядоченном полном списке), хотя я бы предпочел что-то в java.* или в конечном итоге org.apache.*, так как в этот момент было бы сложно представить новые библиотеки.

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

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

Нет проблемы с ошибками кэша CPU Нет 2. имеет проблему с перемещением элементов в массиве.

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

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

UPDATE:

Аналогичный вопрос:
Хороший Сортированный список для Java
Отсортированный список массивов в Java

4b9b3361

Ответ 1

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

  • Сделайте то, что говорит 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(""); }
    }
    
  • Используйте Guava 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()).

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

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

работ:

Ответ 2

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

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

Пример:

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

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

Ответ 3

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

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